<p>As well as implying NP=co-NP, it would also imply that BQP contained NP.</p>

<p>It would also seem to imply that hard instances of NP-complete problems were easy to generate.</p>

CC BY-SA 2.5
2010-08-17T16:39:09.330Z
2010-08-17T16:39:09.330Z
Joe Fitzsimons
<p>Since integer factorization is known to be in both <strong>NP</strong> and <strong>co-NP</strong>, a proof that it is <strong>NP</strong>-complete would imply <strong>NP</strong> = <strong>co-NP</strong>, which is considered highly unlikely.</p>

<p>There is an interesting discussion at this <a href="http://blog.computationalcomplexity.org/2002/09/complexity-class-of-week-factoring.html">old post by Lance Fortnow</a>.</p>

CC BY-SA 2.5
2010-08-17T16:35:24.667Z
2010-08-17T16:35:24.667Z
Daniel Apon
<p>Are there any references covering this?</p>

<cc.complexity-theory><reference-request><np-hardness><factoring>
What would be the consequences of factoring being NP-complete?
txwikinger
# What would be the consequences of factoring being NP-complete?

(Asked by: username_0 on 2010-08-17)

Are there any references covering this?

**Tags:** cc.complexity-theory, reference-request, np-hardness, factoring

---

## 2 answers

### Answer by username_1 on 2010-08-17. Score: 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.


---

### Answer by username_2 on 2010-08-17. Score: 23

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](http://blog.computationalcomplexity.org/2002/09/complexity-class-of-week-factoring.html).


---

