É possível que co-np= p mas np!= P

Question

Suponha que existe um algoritmo que leve como insuficiente uma fórmula de SAT insatisfável e nunca deixe de verificar isso no tempo polinomial.No entanto, quando a entrada é uma fórmula satisfatória, não funciona (digamos problemas de tempo e memória, o algoritmo se perde no raciocínio).

Então co-np= p porque podemos verificar casos insatisfáveis no tempo polinomial.O certificado de insatisfação é a própria fórmula.

Mas é ainda possível que P!= NP?

Answer 1

Se co- $ \ mathsf {np}=mathsf {p} $ então $ \ mathsf {np}=text {co -} \ mathsf {p}=mathsf {p} $ .

Answer 2

A resposta é não, e a razão é que $ \ mathrm {p} $ é trivialmente fechado sob complemento.Apenas por definição de $ \ mathrm {CO} $ , segue-se que $ \ mathrm {conp}=mathrm {p} $ é equivalente a $ \ mathrm {np}=mathrm {policial} $ e, em seguida, usamos esse recipiente de matemática $ \ mathrm {cop}=mathrm {p} $ para concluir que $ \ mathrm {conp}=mathrm {p} $ iff $ \ mathrm {np}=mathrm {p} $ .

Answer 3

Deixe X qualquer problema no NP, o que significa que há uma prova simples sempre que a resposta é sim.Agora pegue o problema x ': "X tem a resposta não".Isso é em co-np, então seria em p, portanto X ISIN P.