NP C PSPACE?

V-man

subj

dimaxd

Что-что?

Runa

из теории сложности это
если не ошибаюсь, то утверждение о вложении неверно

V-man

почему?

miron374

Это вложение есть просто по определению: проверку принадлежности слова языку из NP можно проделать, перебрав все сертификаты (их длины ограничены полиномом от длины входа). Для этого достаточно полиномиальной зоны, поэтому такой алгоритм будет из класса PSPACE.
Или вопрос был про то, строгое ли это включение?

V-man

спасибо, что-то я сам не догадался
Оставить комментарий
Имя или ник:
Комментарий: