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.

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.