Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
Hierarchies not Heirarchies! –  txwikinger Aug 16 '10 at 22:33
    
@txwikinger. Fixed :-) –  Aryabhata Aug 16 '10 at 22:36
    
related: 1 –  Kaveh Aug 8 '11 at 22:13

2 Answers 2

up vote 26 down vote accepted

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.

share|improve this answer
10  
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). –  Joshua Grochow Aug 16 '10 at 22:46

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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