31
$\begingroup$

Assuming that P != NP, I believe it has been shown that there are problems which are not in P and not NP-Complete. Graph Isomorphism is conjectured to be such a problem.

Is there any evidence of more such 'layers' in NP? i.e. A hierachy of more than three classes starting at P and culminating in NP, such that each is a proper superset of the other?

Is it possible that the hierarchy is infinite?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Hierarchies not Heirarchies! $\endgroup$
    – txwikinger
    Commented Aug 16, 2010 at 22:33
  • $\begingroup$ @txwikinger. Fixed :-) $\endgroup$
    – Aryabhata
    Commented Aug 16, 2010 at 22:36
  • $\begingroup$ related: 1 $\endgroup$
    – Kaveh
    Commented Aug 8, 2011 at 22:13

2 Answers 2

Reset to default
31
$\begingroup$

Yes! In fact, there is provably an infinite hierarchy of increasingly harder problems between P and NP-complete under the assumption that P!=NP. This is a direct corollary of the proof of Ladner's Theorem (which established the non-emptiness of NP\P)

Formally, we know that for every set S not in P, there exists S' not in P such that S' is Karp-reducible to S but S is not Cook-reducible to S'. Therefore, if P != NP, then there exists an infinite sequence of sets S1, S2... in NP\P such that Si+1 is Karp-reducible to Si but Si is not Cook-reducible to Si+1.

Admittedly, the overwhelming majority of such problems are highly unnatural in nature.

Improve this answer
$\endgroup$
1
  • 11
    $\begingroup$ In fact, Ladner's Theorem shows that for any two sets S and T, if S Karp-reduces to T but T does not Karp-reduce to S, then there is a set S' such that S' lies properly between S and T (in the partial order under Karp reductions). $\endgroup$
    – Joshua Grochow
    Commented Aug 16, 2010 at 22:46
12
$\begingroup$

There is a notion of "limited nondeterminism" which limits the non-deterministic bits required by Turing machine to arrive at a solution. The class NP requires for example O(n) bits. By limiting the non-deterministic bits to polylog defines a infinite hierarchy of complexity classes called \beta P hierarchy all with complete problems of their own.

See, for example, the following article for details: Goldsmith, Levy, Mundhenk, "Limited nondeterminism", SIGACT News, vol 27(2), pages 20-29, 1996.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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