31

Are there any references covering this?

vy32
  • 103
  • 4
txwikinger
  • 803
  • 1
  • 11
  • 18

2 Answers2

30

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.

Joe Fitzsimons
  • 13,675
  • 47
  • 91
22

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.

Daniel Apon
  • 6,001
  • 1
  • 37
  • 53