Complexity Beyond NP: Space, Randomness and the Hierarchy
Polynomially bounded quantifier blocks give membership bounds in the polynomial hierarchy. Their first quantifier distinguishes Sigma from Pi classes. PSPACE bounds memory. BPP uses polynomial time with bounded error on every input. Whether P = BPP and whether the hierarchy collapses remain open.
What a learner can do afterwards
- Give a polynomial-hierarchy membership bound from polynomially bounded quantifier blocks and a polynomial-time predicate
- Say what would follow if the hierarchy collapsed
- State the conjecture P = BPP, define BPP's bounded error, and distinguish the conjecture from a proof
1 · Read
NP can be written as: there exists a polynomial-length certificate for which a deterministic polynomial-time predicate accepts. This is Sigma_1^P. Starting instead with for every gives Pi_1^P, also called coNP. Here quantified strings have polynomial length bounds in the original input. Their domains are nonempty, and the number of quantifier blocks is fixed.
Merge consecutive quantifiers of the same kind into one block. With k alternating blocks and a polynomial-time predicate, an existential first block gives membership in Sigma_k^P; a universal first block gives membership in Pi_k^P. There are k - 1 switches. This is a membership bound, not a smallest-class proof. Unused quantifiers can describe a problem already in P.
The condition "for every network there exists a routing passing a polynomial-time check" gives a Pi_2^P bound. The condition "there exists a schedule such that for every failure there exists a backup" gives a Sigma_3^P bound. These statements require polynomial-length network, routing, schedule, failure and backup objects. Neither representation proves that the problem is outside a lower level.
PH is the union of all fixed levels. A collapse to Sigma_2^P would mean PH = Sigma_2^P: every PH problem would belong to that class, including problems described with more blocks. One problem having a lower-class algorithm does not establish a collapse. We have no proof that all successive PH levels are distinct, and no proof that PH collapses to a fixed level.
PSPACE contains decision problems solvable using polynomial working memory on a deterministic machine. It does not require polynomial running time. Known containments include P inside NP, NP inside PH, and PH inside PSPACE. These containments do not prove that each inclusion is strict.
BPP contains decision problems with randomized polynomial-time algorithms whose error probability is at most 1/3 on every input. Independent repetition can reduce that error. P is contained in BPP. The conjecture P = BPP says every BPP problem also has a deterministic polynomial-time algorithm. This equality has not been proved. Derandomizing particular algorithms does not prove the general equality.
Bounded quantifier blocks give Sigma/Pi membership bounds, not exact levels. PSPACE bounds memory. BPP permits bounded error. PH collapse and P = BPP remain open.
Original lesson, questions and flashcards written for this learning dataset.
2 · Watch
به انگلیسیTake it off screen
Where it sits
Learn first
Optional connections
This opens up
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.