The standard way to show that a problem **is** NP-complete is to show that another problem known to be NP-complete reduces to it. That much is clear. Given a problem in NP, what's known about how to show that it is **not** NP-complete? 


(My real question is likely to be inappropriate for this site for one or more reasons; I'm curious about what a proof that factoring isn't NP-complete would look like.)



What techniques exist to show that a problem is not NP-complete?
There are much stronger versions of the P vs. NP conjecture that complexity theorists often take as axioms, and that imply that many problems are not NP-complete. The most standard class of assumptions is the conjecture that the NP hierarchy does not collapse. You can define NP as the analysis of polynomially bounded solitaire games with complete information. For instance, generalized Sudoku is such a game and it is known to be NP-complete. The nth level of the polynomial hierachy $\Sigma^n P$ and $\Pi^n P$ can be similarly defined by games with $n$ half moves. For instance, suppose that in generalized Sudoku, there is an initial board, and I can first try to make you lose by filling in some of the squares, with restrictions. (Like say only the "red" squares, and only with certain numbers.) After that you can move. Then whether I can win is a natural problem in $\Sigma^2 P$.


In particular, the assertion that the polynomial hierarchy PH does not collapse implies that NP does not equal co-NP. If a problem is both in NP and co-NP, it cannot be NP-complete without collapse. (Proof: If solitaire were equivalent to co-solitaire, than a game with two half moves would also be equivalent to solitaire.) A good near example is the graph isomorphism problem, which is in NP and co-AM. AM is like NP but with randomness; it is the model in which Arthur gets an adaptive proof in response to a randomized question and becomes statistically convinced. AM is not quite NP, but it is conjectured to be the same. So if you put two standard conjectures together, graph isomorphism is not NP-complete either. **Edit:** Ryan and Harrison both point out that [Boppana, Håstad, and Zachos](http://portal.acm.org/citation.cfm?id=31202) proved that if NP is contained in co-AM, then PH is contained in $\Sigma^2 P$. I.e., the hierarchy would collapse at the second level whether or not AM = NP. In particular this applies to graph isomorphism.


Problems in BQP, such as factoring, are strongly suspected not to be NP-complete either, but it is an open problem to show that that would imply that the polynomial hierarchy collapses. However, decision-based problems from factoring, such as whether a number is square-free, are known to be in both NP and co-NP. This was known earlier, but it follows particularly quickly from the fact that primality is in P, since that certifies a factorization. **Addendum:** Certification of factorization is equivalent to [certification of primality](http://en.wikipedia.org/wiki/Primality_certificate), which as David pointed was first proved by Vaughan Pratt.


