Y a-t-il des références couvrant cela?
25
Y a-t-il des références couvrant cela?
En plus d'impliquer NP = co-NP, cela impliquerait également que BQP contenait NP.
Cela semblerait également impliquer que des instances dures de problèmes NP-complets étaient faciles à générer.
Étant donné que la factorisation entière est connue à la fois dans NP et co-NP , une preuve qu'elle est NP- complète impliquerait NP = co-NP , ce qui est considéré comme hautement improbable.
Il y a une discussion intéressante à ce vieux poste de Lance Fortnow .