Complexity Beyond NP: Space, Randomness and the Hierarchy
NP is one class among many. Alternating quantifiers give the polynomial hierarchy, bounded space gives classes with surprising collapses, and allowing randomness gives classes widely believed to add nothing. Most of the relations between them are conjectures with consequences.
What a learner can do afterwards
- Place a stated problem in the right level by counting its quantifier alternations
- Say what would follow if the hierarchy collapsed
- State what is believed about randomised polynomial time and why the belief is not a proof
1 · Read
NP is one class among many. The polynomial hierarchy stacks problems by quantifier alternations: a single there-exists over an efficiently checkable claim is NP, the first level. Each switch between for-all and there-exists climbs one level higher.
Read the quantifiers left to right. For every network there is a routing: for-all then there-exists, one alternation, so the problem sits at the second level, above NP. There is a schedule such that for every failure there is a backup: three quantifier blocks, two alternations, third level.
A collapse would drop higher problems down: if the hierarchy collapsed to some level, every problem above it would become solvable there, erasing much of what separates the hard from the harder. No collapse has been proved, and none has been ruled out.
Randomness gets its own class: bounded-error probabilistic polynomial time, fast with randomness and usually right. It is widely believed to equal deterministic polynomial time, so randomness adds nothing. Belief is not proof: turning that into a theorem needs a derandomization nobody has found.
Alternations set the level; collapse would flatten it; randomness is believed free but unproved.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.