31
$\begingroup$

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?

$\endgroup$

migrated from cstheory.stackexchange.com May 12 '12 at 20:07

This question came from our site for theoretical computer scientists and researchers in related fields.

24
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It's been a few years, but I was under the impression that NP-Hard problems fit the OP's description, where do they fit in? $\endgroup$ – Kevin May 13 '12 at 2:36
  • 2
    $\begingroup$ @Kevin: No, NP-hard means that a problem is at least as hard as the hardest problems in NP. $\endgroup$ – Huck Bennett May 13 '12 at 2:55
  • $\begingroup$ What about problems with psuedo-polynomial run-time? $\endgroup$ – Joe May 15 '12 at 18:31
  • $\begingroup$ @Joe, I am not sure what you mean, if you have a question post it as a new question. $\endgroup$ – Kaveh May 15 '12 at 18:56
  • 1
    $\begingroup$ Oh, of course assuming P!=NP. Such a problem would be Graph Isomorphism, right? $\endgroup$ – levi Jul 7 '15 at 20:43
11
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ A really recent result by Babai (see jeremykun.com/2015/11/12/…) gives a quasipolynomial algorithm for graph isomorphism, basically removing it from NPI, if the result holds. Interestingly, it was the problem which was not known to be in BQP $\endgroup$ – Frédéric Grosshans Nov 16 '15 at 9:53
  • 1
    $\begingroup$ @FrédéricGrosshans having a quasipolynomial time algorithm does not remove you from NPI (in fact, it wouldn't even remove you from NPC unless you make stronger assumptions than just P != NP). Babai's result (if correct, which it probably is) only provides circumstantial evidence that GraphIso might be in P, because in the past when quasipolynomial algorithms for difficult problems were found, they eventually led to polynomial algorithms. $\endgroup$ – Artem Kaznatcheev Nov 18 '15 at 2:43
  • 1
    $\begingroup$ @FrédéricGrosshans Babai retracted the claim of quasipolynomial runtime. Apparently there was an error in the analysis. $\endgroup$ – Raphael Jan 4 '17 at 21:45
  • $\begingroup$ @Raphael per my prior comment, I don't think that Babai relaxing the quasipolynomial to subexponential is not particularly relevant to the discussion at hand. $\endgroup$ – Artem Kaznatcheev Jan 5 '17 at 20:15
  • $\begingroup$ Since that comment is still here, I did not want it to stand uncorrected. (Basically, I tracked down all occurrences of "Babai" on the site and posted the same comment.) Feel free to flag all comments to feel are obsolete as such. $\endgroup$ – Raphael Jan 6 '17 at 13:44
7
$\begingroup$

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 PNP. 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!

$\endgroup$
  • $\begingroup$ please explain: No problems in NP are known to not be in P? Aren't all P already in NP? $\endgroup$ – Shimano Oct 16 '12 at 5:52
  • 1
    $\begingroup$ @Shimano- These are two different concepts: All problems in P are known to be in NP. However, we don't know if any problems in NP are not in P. That is, we know that P is a subset of NP, but we don't know if NP is a subset of P. Does that clarify things? $\endgroup$ – templatetypedef Oct 16 '12 at 5:53
  • $\begingroup$ Things are getting clearer now. Thanks so much for your quick replies. One more clarification needed. You said:"The reason for this is that any problem in NP has a polynomial-time reduction to each NP-complete problem." This proves all problems in NP are automatically NP-complete? I am a little confused again $\endgroup$ – Shimano Oct 16 '12 at 5:56
  • $\begingroup$ @Shimano- Not quite. The direction of the reduction is important. A problem is NP-complete if all problems in NP reduce to that problem. You can also show a problem is NP-hard by reducing a known NP-complete problem to that problem. However, showing that a problem in NP reduces to a known NP-complete problem doesn't show anything new, since by definition all NP problems reduce to all NP-complete problems. $\endgroup$ – templatetypedef Oct 16 '12 at 6:02
  • 1
    $\begingroup$ @Shimano- Ladner's theorem says that if P != NP, then there must be NP-intermediate problems, so if there are no NP-intermediate problems, then P = NP. And yes - if we can find a problem in NP that's not in P, regardless of whether it's in BQP, then P != NP. $\endgroup$ – templatetypedef Oct 16 '12 at 7:17
5
$\begingroup$

There are some problems which are NP, but no one knows they are NP-Complete or $P$, like graph isomorphism1. 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).


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

$\endgroup$

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.