¿Es posible que Co-NP= P pero NP!= P

Question

Supongamos que existe un algoritmo que toma como ingresa una fórmula SAT insatisfiable, y nunca deja de verificarla en el tiempo polinomial.Sin embargo, cuando la entrada es una fórmula satisfactoria, no funciona (digamos problemas de tiempo y memoria, el algoritmo se pierde en el razonamiento).

luego co-np= p porque podemos verificar instancias insatisfactorias en el tiempo polinomial.El certificado de insatisfacción es la propia fórmula.

¿Pero entonces es posible que P!= NP?

Answer 1

Si co- $ \ mathsf {np}=mathsf {p} $ luego $ \ mathsf {np}=texto {co -} \ mathsf {p}=mathsf {p} $ .

Answer 2

La respuesta es no, y la razón es que $ \ mathrm {p} $ está trivialmente cerrado bajo complemento.Simplemente por definición de $ \ mathrm {co} $ , se deduce que $ \ mathrm {CONP}=MATHRM {P} $ es equivalente a $ \ mathrm {np}=mathrm {copo} $ , y luego usamos ese $ \ mathrm {copo}=mathrm {p} $ para concluir que $ \ mathrm {CONP}=MATHRM {P} $ {phies $ \ mathrm {np}=mathrm {p} $ .

Answer 3

Sea x cualquier problema en NP, lo que significa que hay una prueba simple siempre que la respuesta es sí.Ahora toma el problema x ': "¿X tiene la respuesta no?Eso está en CO-NP, por lo que sería en P, por lo tanto, X Isin P.