¿Cómo probar P= NP si el problema π ε np-complete y el problema complementa πc ε np?
-
29-09-2020 - |
Pregunta
¿Cómo probar si P= NP si el problema π ε np-complete y el problema complementa πc ε np? O P= NP Si el NPC se interseca con CO-NPC
Solución
PROBANDO $ NP= CO-NP $ no significa necesariamente que $ p= np $ .Aunque, al otro lado, es correcto: Supongamos $ p= np $ , luego $ co-np= co-p= p= p= np $ .
Otros consejos
No encontrará nada útil con nuestro conocimiento actual.Sin embargo, un cambio a $ \ pi ^ c \ in \ mbox {p} $ te obtendrá $ \ mbox {p}=mbox {np} $ .
Licenciado bajo: CC-BY-SA con atribución
No afiliado a cs.stackexchange