È possibile che Co-NP= P ma NP!= P

Question

Supponiamo che esista un algoritmo che prende come input una formula sat insoddisfacente e non riesce mai a verificarlo in tempo polinomiale.Tuttavia, quando l'input è una formula soddisfatta, non funziona (diciamo tempo e problemi di memoria, l'algoritmo si perde nel ragionamento).

Allora Co-NP= P perché possiamo verificare istanze insoddisfacute in tempo polinomiale.Il certificato di insoddisfazione è la formula stessa.

Ma allora è ancora possibile che p!= np?

Answer 1

Se CLASSE CO- $ \ mathsf {np}=mathsf {p} $ quindi $-\ mathsf {np}=text {co -} \ mathsf {p}=mathsf {p} $ .

Answer 2

La risposta è no, e il motivo è che $ \ mathrm {p} $ è banalmente chiuso con il complemento.Solo per definizione di $ \ mathrm {co} $ , ne consegue che $ \ mathrm {conp}=mathrm {p} $ equivalente a $ \ mathrm {np}=mathrm {polip} $ , quindi usiamo quel $ \ MathRM {COP}=MATHRM {P} $ per concludere che $ \ MathRM {CONP}=MathRM {P} $ IFF $ \ mathrm {np}=mathrm {p} $ .

Answer 3

Lascia che X sia qualsiasi problema in NP, il che significa che c'è una prova semplice ogni volta che la risposta è sì.Ora prendi il problema x ': "X ha la risposta no".Questo è in Co-NP, quindi sarebbe in P, quindi x Isin P.