# Hierarchies in NP (under the assumption that P != NP)

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?

• 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

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.

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