Are there NP problems, not in P and not NP Complete?

Question

Are there any known problems in $\mathsf{NP}$ (and not in $\mathsf{P}$) that aren't $\mathsf{NP}$ Complete? My understanding is that there are no currently known problems where this is the case, but it hasn't been ruled out as a possibility.

If there is a problem that is $\mathsf{NP}$ (and not $\mathsf{P}$) but not $\mathsf{NP\text{-}complete}$, would this be a result of no existing isomorphism between instances of that problem and the $\mathsf{NP\text{-}complete}$ set? If this case, how would we know that the $\mathsf{NP}$ problem isn't 'harder' than what we currently identify as the $\mathsf{NP\text{-}complete}$ set?

Answer 1

Are there any known problems in NP (and not in P) that aren't NP Complete? My understanding is that there are no currently known problems where this is the case, but it hasn't been ruled out as a possibility.

No, this is unknown (with the exception of the trivial languages $\emptyset$ and $\Sigma^*$, these two are not complete because of the definition of many-one reductions, typically these two are ignored when considering many-one reductions). Existence of an $\mathsf{NP}$ problem which is not complete for $\mathsf{NP}$ w.r.t. many-one polynomial time reductions would imply that $\mathsf{P}\neq\mathsf{NP}$ which is not known (although widely believed). If the two classes are different then we know that there are problems in $\mathsf{NP}$ which are not complete for it, take any problem in $\mathsf{P}$.

If there is a problem that is NP (and not P) but not NP Complete, would this be a result of no existing isomorphism between instances of that problem and the NP Complete set?

If the two complexity classes are different then by Ladner's theorem there are problems which are $\mathsf{NP}$-intermediate, i.e. they are between $\mathsf{P}$ and $\mathsf{NP\text{-}complete}$.

If this case, how would we know that the NP problem isn't 'harder' than what we currently identify as the NP Complete set?

They are still polynomial time reducible to $\mathsf{NP\text{-}complete}$ problems so they cannot be harder than $\mathsf{NP\text{-}complete}$ problems.

Answer 2

As @Kaveh stated, this question is only interesting if we assume $P \neq NP$; the rest of my answer takes this as an assumption, and mostly provides links to further wet your appetite. Under that assumption, by Ladner's theorem we know that there are problems that are neither in $P$ nor $NPC$; these problems are called $NP$-intermediate or $NPI$. Interestingly enough, Ladner's theorem can be generalized to many other complexity classes to produce similar intermediate problems. Further, the theorem also implies, that there is an infinite hierarchy of intermediate problems that are not poly-time reducible to each other in $NPI$.

Unfortunately, even with the assumption $P \neq NP$ it is very difficult to find natural problems that would be provably $NPI$ (of course you have the artificial problems coming from the proof of Ladner's theorem). Thus, even assuming $P \neq NP$ at this time we can only believe some problems to be $NPI$ but not prove it. We come to such beliefs when we have reasonable evidence to believe that an $NP$ problem is not in $NPC$ and/or not in $P$; or just when it has been studied for a long time and avoided fitting into either class. There is a pretty comprehensive list of such problems in this answer. It includes such all-time favorites as factoring, discrete log, and graph-isomorphism.

Interestingly, some of these problems (notable: factoring and discrete log) have polynomial time solutions on quantum computers (i.e. they are in $BQP$). Some other problems (such as graph-isomorphism) are not known to be in $BQP$, and there is ongoing research to resolve the question. On the other hand, it is suspected that $NPC \not\subseteq BQP$, thus people don't believe we will have an efficient quantum algorithm for SAT (although we can get a quadratic speed up); it is an interesting question to worry about what sort of structure $NPI$ problems need in order to be in $BQP$.

Answer 3

No NP-complete problems are known to be in P. If there is a polynomial-time algorithm for any NP-complete problem, then P = NP, because any problem in NP has a polynomial-time reduction to each NP-complete problem. (That's actually how "NP-complete" is defined.) And obviously, if every NP-complete problem lies outside of P, this means that P ≠ NP. We're not really sure why it's hard to show it one way or the other; if we knew the answer to that question, we'd probably know a lot more about P and NP. We have a few proof techniques that we know don't work (relativization and natural proofs, for example), but don't have a principled explanation as to why this problem is hard.

If there are problems in NP which are not in P, then there is actually an infinite hierarchy of problems in NP between those in P and those which are NP complete: this is a result called Ladner's theorem.

Hope this helps!

Answer 4

There are some problems which are NP, but no one knows they are NP-Complete or $P$, like graph isomorphism¹. But as I know there isn't special complexity class for such a problems, may be I'm wrong, though.

May be it's $P$, e.g before AKS algorithm no one knows primality testing is $P$ or NPC.

Also there are some problems which are NPC but not in strong sense or weakly NP-Complete, like 2-Partition problem, means, if the input numbers are in polynomial order of input size, this problems can be solved in $P$ (or there is a pseudo polynomial time algorithm for them).

---

¹ Similar problem: sub graph isomorphism is NP-Complete in strong sense.