$NP$ problems not known to be in $P$ and not known to be $NP$-complete

Question

I've read that solving Pell's equation is neither known to be in $P$ nor known to be $NP$-complete. What are other natural and important examples of such problems?

Answer 1

They are called NP-intermediate problems (under the assumption of $P\neq NP$, otherwise the definition makes no sense).

By now, some natural/real-world problems are suspected to be in this class, yet no one has been able to prove that, since that would be a proof of $P\neq NP$.

1. Graph isomorphism problem, that is, to determine whether two graphs are isomorphic.
2. Integer factorization and the related problem of computing discrete logarithm

are among the most well-known ones.

Answer 2

Some problem in the BQP class like integer factorization are suspected to be outside P, and the relation between BQP and NP is not known.

From Wikipedia, the suspected relationship of BQP to other problem spaces:

Answer 3

I like the PPAD ("Polynomial Parity Arguments on Directed graphs") complexity class, because the class of PPAD-complete problems includes things like finding Nash equilibria and Brouwer fixpoints, as well as their combinatorial analogs like Sperner' lemma. Here's a quote from Wikipedia to put things in context:

PPAD is a class of problems that are believed to be hard, but obtaining PPAD-completeness is a weaker evidence of intractability than that of obtaining NP-completeness. It could still be the case that PPAD is the same class as P, and still have that P≠NP, though it seems unlikely.

---

The same question has been asked before on TCS, and the answers there are superior to anything I could come up with. However, I couldn't resist the temptation to add the reference to PPAD as an answer.