Конспект установочных лекций по комплексному курсу Информатика, Теория информации

       

I&supl


По теореме Савича справедливо

NPSPACE(n^) Í DSPACE(n2^).

Это дает следующее высказывание об отношении между pspace и NPSPACE-

Теорема (равенство pspace и NPSPACE)’

Известна справедливость высказывания NSPACE(log n) Í p Í NP Í pspace Открытым остается вопрос о равенстве Р и NP: верно ли, что Р == NP ?

Этот вопрос - одна из больших, пока еще не решенных проблем теории сложности: до сих пор не удалось доказать ни Р = NP, ни Р ¹ NP.

Концепция недетерминированных Т-машин является формулировкой в теории автоматов одного из классов алгоритмов, которые работают с методами поиска. Любой недетерминированный алгоритм можно считать спецификацией задачи поиска.



Содержание раздела