30

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?

Aryabhata
  • 1,855
  • 3
  • 21
  • 29

2 Answers2

30

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.

Daniel Apon
  • 6,001
  • 1
  • 37
  • 53
  • 11
    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
11

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.

Imran Rauf
  • 343
  • 1
  • 7