Конспект установочных лекций по комплексному курсу Информатика, Теория информации
I&supl
По теореме Савича справедливо
NPSPACE(n^) Í DSPACE(n2^).
Это дает следующее высказывание об отношении между pspace и NPSPACE-
Теорема (равенство pspace и NPSPACE)’
Известна справедливость высказывания NSPACE(log n) Í p Í NP Í pspace Открытым остается вопрос о равенстве Р и NP: верно ли, что Р == NP ?
Этот вопрос - одна из больших, пока еще не решенных проблем теории сложности: до сих пор не удалось доказать ни Р = NP, ни Р ¹ NP.
Концепция недетерминированных Т-машин является формулировкой в теории автоматов одного из классов алгоритмов, которые работают с методами поиска. Любой недетерминированный алгоритм можно считать спецификацией задачи поиска.
