Are there are problems in NP that have been shown to be not NP-complete but it is still not known if they are in P or not?

Question

I am not talking about NP-indeterminate class because those problems have to be shown to not exist either in P or NP-complete class and existence of such problems proves P!=NP. I am interested to know if we are half-way there i.e. problems that have been proven to be not NP-complete but are in NP but we don't know if they are in P as well.

What about such problems whose deterministic polynomial solution was found only recently? Was primality testing such a problem?

I would appreciate if the answers are given for someone like me who only has a high level understanding of computational complexity theory.

• amit: Integer Factorization is suspected to be not NP-Hard (and not P as well) - but not proof yet.

Answer 1

Any problem that is provably not $\mathsf{NP}$ complete (w.r.t. polynomial time reductions) would mean that the class of problems reducible to it are distinct from $\mathsf{NP}$. In other words if you show some problem is in $\mathsf{NP}$ but is not $\mathsf{NP}$ complete would imply that $\mathsf{P}$ is not equal to $\mathsf{NP}$.

In short, there is no problem in $\mathsf{NP}$ that we know it is not $\mathsf{NP}$-complete.

---

Regarding primality and AKS algorithm for it:

Note that the according to the current state of knowledge, it is possible that primality is NP-complete. Existence of a deterministic polynomial time algorithm for a problem does not rule out the possibility of the problem being $\mathsf{NP}$-complete.

You are probably interested in the list of problems that are conjectured to be between $\mathsf{P}$ and $\mathsf{NP}$ (known as $\mathsf{NP}$-intermediate) in which case you can check the answers to Problems Between P and NPC.

• argentage: This is not right since integer factorization is in NP but is suspected to be outside of NP complete.
• Kaveh: @airza, what I have written is correct. Suspected is not equal to proven. The OP is asking if there is any problem that is proven not to be NP-complete and there is no such problem and will not be as long as we have not proven P is not equal to NP.
• Shimano: @ Kaveh Thanks for the answer. Could you please explain yourself here: "Existence of a deterministic polynomial time algorithm for a problem does not rule out the possibility of the problem being NP-complete". I thought that if a deterministic polynomial time algorithm exists for a problem then it is in P.
• Kaveh: Yes, that's correct, but it's mot known that P and NP-complete are disjoint sets. For example, if P=NP then all (non-trivial) problems in P are NP-complete.