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?

  • $\begingroup$ Relevant $\endgroup$
    – MJD
    Oct 25 '13 at 1:00

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.

  • $\begingroup$ +1 and a fist-shake because these are the two examples I clicked through intending to answer with. :-) $\endgroup$ Oct 24 '13 at 23:49
  • $\begingroup$ @StevenStadnicki you see, those are really the most well-known ones :D $\endgroup$
    – ftfish
    Oct 24 '13 at 23:52

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: enter image description here


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.