Добрый день!
В большинстве курсов по сложности вычислений и вообще теории алгоритмической сложности у нас в стране изучаются такие классы как P, NP, PSPACE, DLOG, EXPTIME, вероятностные классы и некоторые другие, рассматриваются некоторые иерархии. Все это есть и в большом количестве литературы. В зарубежной литературе по сложности вычислений, по булевым функциям и схемной сложности, по алгоритмам можно встретить классы NC, AC, LOGCFL, и кучу других, множество соотношений между ними. Можно даже просто взять википедию и увидеть, что в русской версии подобные классы не освещены, зато в английской - полно.
В связи с этим у меня вопрос - есть ли какие-нибудь книжки на русском языке, в которых рассматриваются подобные вопросы, классы типа
таких и связи между ними, так что бы увидеть всю картину в целом и отношение всего этого дела к классическим проблемам?
Извиняюсь, если обидел какую-нибудь книжку своим незнанием о ней
20.04.2013, 21:59 