Exatamente um de NP e co-NP pode ser igual a P?

8

Talvez esteja faltando algo óbvio, mas será que P = co-NP NP ou vice-versa? Meu sentimento é que deve haver algum teorema que descarta essa possibilidade.

aelguindy
fonte

Respostas:

14

Não, porque está fechado para complementar isso, e sabemos até que .PP=NPNP=co-NP

Vamos supor que e digitar , portanto, . Assumimos que e, portanto, existe um TM st . Se pegarmos o "complemento" de M , que é uma máquina M ' que é idêntica a M, exceto que seus estados de aceitação e rejeição são revertidos, obtemos que L (M') = (L ^ c) ^ c = L , e portanto, L está em \ mathsf {NP} .P=NPeuco-NPeucNPP=NPMeu(M)=eucMMMeu(M)=(euc)c=eueuNP

Isso mostra que, assumindo que , obtemos e, portanto, .P=NP(P=)NP=co-NPP=co-NP

Boris Trayvas
fonte
9

P está fechado no complemento (por exemplo, ¹); portanto, se (ou ), entãoP=co-PP=co-NPP=NPco-NP=NP


  1. Dada uma linguagem , podemos construir uma TM determinística 'que decide em tempo polinomial simplesmente pegando a TM que decide e ...euPeu¯eu
Vor
fonte