Are there any references covering this?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
0
As well as implying NP=co-NP, it would also imply that BQP contained NP.
It would also seem to imply that hard instances of NP-complete problems were easy to generate.
$\begingroup$
$\endgroup$
0
Since integer factorization is known to be in both NP and co-NP, a proof that it is NP-complete would imply NP = co-NP, which is considered highly unlikely.
There is an interesting discussion at this old post by Lance Fortnow.
answered Aug 17, 2010 at 16:35