Are there any references covering this?
Tell me more
×
Theoretical Computer Science Stack Exchange is a question and answer site for
theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
|
|
||||
|
|
|
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. |
|||
|
|
|
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. |
|||
|
|
