Возможно ли, что CO-NP= P, но NP!= P

Question

Предположим, существует алгоритм, который принимает в качестве ввода неудовлетворенную формулу SAT, и никогда не проверяет ее в полиноме.Однако, когда ввод является удовлетворенной формулой, она не работает (давайте скажем проблемы с временем и памятью, алгоритм теряется в рассуждении).

Тогда CO-NP= P, потому что мы можем проверить неудовлетворительные экземпляры в многочленом времени.Свидетельство о ненадежности - сама формула.

Но тогда все еще возможно, что p!= np?

Answer 1

Если co- $ \ mathsf {np}=mathsf {p} $ Тогда $ \ mathsf {np}=Text {Co -} \ mathsf {p}=mathsf {p} $ .

Answer 2

Ответ отсутствует, и причина в том, что $ \ mathrm {p} $ тривиально закрывается под дополнением.Просто по определению $ \ mathrm {co} $ , следует, что $ \ mathrm {conp}=mathrm {p} $ эквивалентно $ \ mathrm {np}=mathrm {cop} $ , а затем мы используем это $ \ mathrm {conp}=mathrm {p} $ iff $ \ mathrm {np}=mathrm {p} $ .

Answer 3

Пусть X будет любые проблемы в NP, что означает, что есть простое доказательство всякий раз, когда ответ - да.Теперь возьмите проблему X ': «У него нет ответа нет».Это в CO-NP, поэтому он будет в P, поэтому X Исин П.