Является ли с оракулом доступ к N P больше, чем просто N P ? Как я понимаю, N P N P - это просто машина Тьюринга, которая может выполнять запросы к другой машине N P, если таковая, кроме N P, может имитировать N P N P ? Что-то не так с этим аргументом?
10
Ответы:
Чтобы переформулировать мои комментарии в качестве ответа и немного расширить:
Мы не знаем, является ли NP NP = NP - общеизвестно открытой проблемой в теории сложности, хотя, как и в случае P и NP, мы подозреваем, что они не равны. Одна из причин , почему мы не знаем , как имитировать NP оракула с NP машины является то , что мы не знаем , как NP машина не может обнаружить «нет» экземпляров проблем , представленных к оракулу.
Класс NP NP также известен как и является одним из классов на втором уровне полиномиальной иерархии . Другие классы на втором уровне Δ P 2Σп2
(Все эти классы были бы одинаковыми, если бы мы использовалиоракулаcoNP; единственное различие, по сути, заключается в логическом отрицании вывода.) Классы третьего и более высоких уровней иерархии определяются путем предоставления им еще большего числаоракуловNP:
Δ P k + 1
источник
источник