¿Hay alguna referencia que cubra esto?
25
¿Hay alguna referencia que cubra esto?
Además de implicar NP = co-NP, también implicaría que BQP contenía NP.
También parece implicar que las instancias difíciles de problemas NP-completos fueron fáciles de generar.
Dado que se sabe que la factorización de enteros está tanto en NP como en co-NP , una prueba de que es NP- completo implicaría NP = co-NP , lo que se considera altamente improbable.
Hay una discusión interesante en este viejo post de Lance Fortnow .