Skip to content
Tutorials Center
My learning

Topics

Lesson 49 of 59 ยท Complexity

The Complexity Hierarchy and the P versus NP Question

See how complexity classes nest, why more time buys more power (the hierarchy theorems), what P versus NP would change, and run a diagonalization demo and a feasibility table.

You now know five or six complexity classes. The natural question is how they fit together, and whether giving a machine more resources really lets it solve more problems. For time and space the answer is yes, and the argument is a beautiful return of the diagonalization you met in the undecidability chapter. After that we look at the most important open problem in the field, P versus NP, and what is known and unknown about it.

Nested classes

Here is the map of everything so far. Arrows mean "is contained in".

flowchart TD
    L["L"] --> NL["NL"]
    NL --> P["P"]
    P --> NP["NP"]
    P --> CONP["coNP"]
    NP --> PS["PSPACE"]
    CONP --> PS
    PS --> EXP["EXPTIME"]
    EXP --> NEXP["NEXPTIME"]
    NEXP --> R["Decidable"]
    PH["Polynomial hierarchy PH"] -.-> PS
    NP --> PH
    CONP --> PH

NP and coNP both sit inside the polynomial hierarchy, which sits inside PSPACE. Only a few of these inclusions are known to be strict.

Resources define the classes

Time P, NP, EXPTIME
Space L, NL, PSPACE
Randomness BPP, RP
Alternation PH, PSPACE

Each resource gives a family of classes.

1 / 3

The hierarchy theorems

Does more time give more power? Obviously a machine allowed n^3 steps can do at least what one allowed n^2 steps can. The time hierarchy theorem says that it can do strictly more, as long as the extra time is a little more than constant-factor larger:

TEXT
If f(n) log f(n) = o(g(n)), then DTIME(f(n)) โŠŠ DTIME(g(n)).

Concrete consequences: DTIME(n) โŠŠ DTIME(n^2) โŠŠ DTIME(n^3), so there is a never-ending ladder inside P, and P โŠŠ EXPTIME. The space hierarchy theorem is the same for memory: SPACE(s(n)) โŠŠ SPACE(s'(n)) when s(n) = o(s'(n)), which gives L โŠŠ PSPACE and NL โŠŠ PSPACE.

The diagonal argument, in miniature

The proof is diagonalization with a stopwatch. Enumerate all machines M0, M1, M2, .... Build a machine D that, on input i, simulates Mi on input i for at most g(i) steps and then does the opposite: if Mi accepts within the budget, D rejects; otherwise D accepts. D itself runs in about g(n) time (simulation costs a small overhead, which is why the bound has a log factor). D differs from every machine that finishes within its budget, so D's language is not in the smaller class but is in the larger one.

Python A toy diagonalization with a step budget

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

D disagrees with every machine that halts inside the budget (the differs column). The slow machine m_slow exceeds the budget, so D does not contradict it: that is precisely why a bigger budget gives a bigger class.

How different are polynomial and exponential?

The theory draws its line at polynomial time because growth rates diverge dramatically. Suppose each step takes one nanosecond (10^9 steps per second). How large an input can you handle in one hour?

Python Largest input size solvable in an hour

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Doubling the speed of your computer adds only one to the feasible n for 2^n, while it multiplies the feasible n for n^2 by about 1.4. A polynomial algorithm benefits from faster hardware; an exponential one barely notices it.

P versus NP

P versus NP asks: is every problem whose solutions can be verified quickly also solvable quickly? Formally, is P = NP? Cook and Levin showed SAT is NP-complete, so the question is equivalent to "does SAT have a polynomial-time algorithm?". The Clay Mathematics Institute lists it among its seven Millennium Prize Problems with a one-million-dollar prize.

Most researchers believe P โ‰  NP, for reasons like these:

  • Decades of effort by experts to find fast algorithms for NP-complete problems have failed.
  • Many different NP-complete problems from different fields would all fall at once if one did.
  • If P = NP, finding proofs would be as easy as checking them, which seems too good to be true.

Why is it so hard to settle? Three famous barriers explain why standard techniques cannot work: relativization (diagonalization alone cannot separate P and NP, since there are oracles making them equal and others making them different), natural proofs (a broad class of circuit-lower-bound arguments would break strong cryptography), and algebrization (a refinement of relativization).

What if P = NP?

Practically everything in optimization and scheduling would become easy, automated theorem proving would be feasible, and most modern cryptography (which relies on one-way functions) would collapse. What if P โ‰  NP? Then NP-complete problems have no efficient exact algorithms in the worst case, and that gives us a mathematical reason to rely on approximations and heuristics, the subject of the last lesson of this chapter.

NP-intermediate problems

Assuming P โ‰  NP, Ladner's theorem says NP is not just P plus the NP-complete problems: there are problems in NP that are neither in P nor NP-complete. Natural candidates include graph isomorphism (recently shown to be solvable in quasi-polynomial time) and integer factorization. Factoring is in NP and coNP, so it is unlikely to be NP-complete (that would collapse NP and coNP).

Beyond the main chain

  • BPP (bounded-error probabilistic polynomial time): decidable by randomized algorithms that are correct with probability at least 2/3. Most believe BPP = P.
  • PH (polynomial hierarchy): problems with a constant number of alternating โˆƒ/โˆ€ quantifiers; contains NP and coNP and lies inside PSPACE.
  • #P: counting problems, such as counting the satisfying assignments of a formula.
  • BQP: polynomial time on a quantum computer; contains factoring, and is suspected not to contain NP-complete problems.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does the time hierarchy theorem imply?

    With a little more time than a constant factor, a machine can decide strictly more languages, which yields a ladder inside P and P strictly inside EXPTIME.
  2. 2. How does the diagonal machine D in the hierarchy proof behave on input i?

    D simulates the i-th machine on i for a limited number of steps and flips its answer, so D differs from every machine that finishes within the budget.
  3. 3. Which pair of classes is known to be different?

    The time hierarchy theorem proves P is strictly inside EXPTIME. The other pairs are open questions.
  4. 4. Ladner's theorem says that if P โ‰  NP then

    NP then has an in-between zone. Graph isomorphism and factoring are suspected members.
  5. 5. If P = NP were proved, which consequence is most likely?

    One-way functions cannot exist if P = NP, since inverting them would be an NP problem solvable quickly. The halting problem would stay undecidable.

Summary

  • The classes nest as L โІ NL โІ P โІ NP โІ PSPACE โІ EXPTIME, with NP and coNP inside the polynomial hierarchy.
  • Hierarchy theorems (diagonalization with a time or space budget) prove that more resources give more power: P โŠŠ EXPTIME, L โŠŠ PSPACE.
  • Exponential growth defeats faster hardware; polynomial growth rewards it.
  • P versus NP is open; relativization, natural proofs and algebrization explain why it is so hard.
  • Between P and NP-complete there may be NP-intermediate problems such as factoring.

Next: Coping with NP-Hard Problems