Почему этот аргумент в пользу неверен?

11

Я знаю, что это глупо, но мне удалось запутаться, и мне нужна помощь, чтобы решить эту проблему

Предположим, что , тогда ясно, что для каждого оракула имеем что противоречит тому, что существует некоторый оракул для которого , следовательно,P=NPAPA=NPAAPANPAPNP

Что не так? Спасибо!

Ariel
источник

Ответы:

13

Конечно, вы просто должны быть осторожны, думая о том, что значит иметь оракула.

Проблема возникает из раздражающего злоупотребления обозначения мы используем в CS: В заявлении , относится к набору языков. Но в заявлении , относится к классу машин Тьюринга (determinstic полиномиальных по ТМС). Вы должны думать об этих двух с , как из совершенно разных типов.P=NPPPA=NPAPP

Таким образом, даже если два набора языков и одинаковы, детерминированные многопользовательские TM по-прежнему не работают так же, как недетерминированные. В частности, при наличии оракула недетерминированный ТМ может «задавать много вопросов одновременно», чего не может делать обычная ТМ. Таким образом, даже если они выбирают один и тот же набор языков, когда ни одному типу машины не оказывается дополнительная помощь, оракул может помочь одному типу машины больше, чем другому.PNP

усул
источник