Was sind die Konsequenzen, wenn Factoring NP-vollständig ist?

Gibt es Referenzen dazu?

Dies impliziert nicht nur NP = co-NP, sondern auch, dass BQP NP enthält.

Es scheint auch zu implizieren, dass schwierige Fälle von NP-vollständigen Problemen leicht zu erzeugen waren.

Da bekannt ist, dass die ganzzahlige Faktorisierung sowohl in NP als auch in co-NP vorliegt, würde ein Beweis, dass es NP- vollständig ist, NP = co-NP implizieren , was als sehr unwahrscheinlich angesehen wird.

In diesem alten Beitrag von Lance Fortnow gibt es eine interessante Diskussion .