<p>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.</p>

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

CC BY-SA 2.5
2010-08-17T02:32:57.740Z
2010-08-17T02:32:57.740Z
Imran Rauf
<p>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)</p>

<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 S<sub>1</sub>, S<sub>2</sub>... in NP\P such that S<sub>i+1</sub> is Karp-reducible to S<sub>i</sub> but S<sub>i</sub> is not Cook-reducible to S<sub>i+1</sub>.</p>

<p>Admittedly, the overwhelming majority of such problems are highly unnatural in nature.</p>

CC BY-SA 2.5
2010-08-16T22:46:53.533Z
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
CC BY-SA 2.5
2010-08-16T22:28:55.187Z
2010-08-16T22:28:55.187Z
Daniel Apon
<p>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.</p>

<p>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? </p>

<p>Is it possible that the hierarchy is infinite?</p>

CC BY-SA 3.0
2011-08-08T22:13:49.287Z
related: [1](http://cstheory.stackexchange.com/q/799/186)
Kaveh
CC BY-SA 2.5
2010-08-16T22:33:59.780Z
Hierarchies not Heirarchies!
txwikinger
CC BY-SA 2.5
2010-08-16T22:36:55.937Z
@txwikinger. Fixed :-)
Aryabhata
<cc.complexity-theory>
Hierarchies in NP (under the assumption that P != NP)
Aryabhata
# Hierarchies in NP (under the assumption that P != NP)

(Asked by: username_0 on 2010-08-16)

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?

**Tags:** cc.complexity-theory
> **Comments:**
> **username_2**: Hierarchies not Heirarchies!  
> **username_0**: @txwikinger. Fixed :-)  
> **username_1**: related: [1](http://cstheory.stackexchange.com/q/799/186)  

---

## 2 answers

### Answer by username_4 on 2010-08-16. Score: 31 | Accepted answer

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.

> **Comments:**
> **username_5**: 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).  

---

### Answer by username_3 on 2010-08-17. Score: 12

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.


---

