the polynomial hierarchy
NP captures problems with one layer of 'there exists' (does a witness exist?), and co-NP captures one layer of 'for all' (does every candidate pass?). The polynomial hierarchy is what you get by stacking these quantifiers in alternating layers: there exists ... for all ... there exists ..., each layer flipping the quantifier. It is the fine structure of difficulty just above NP and co-NP, a tower of classes each a little stronger than the last, sitting between NP and PSPACE.
Formally the hierarchy has levels named Sigma_k and Pi_k (Sigma is the Greek capital S, Pi the Greek capital P). Sigma_1 is NP (one block of there-exists), Pi_1 is co-NP (one block of for-all). Sigma_2 problems are verifiable by 'there exists u, for all v, predicate(x,u,v)' with u and v polynomially short and the predicate poly-time checkable; Pi_2 swaps the leading quantifier to 'for all u, there exists v ...'. In general Sigma_k allows k alternating quantifier blocks starting with there-exists, and Pi_k starts with for-all. The whole hierarchy PH is the union of all these levels. An equivalent and elegant view uses oracle machines: Sigma_(k+1) is NP with an oracle for a Sigma_k-complete problem, climbing one rung by gaining the power to consult the level below for free.
PH is a refined map of the territory between NP and PSPACE: NP and co-NP both sit at level 1, and the whole hierarchy is contained in PSPACE (cap the alternations and you stay polynomial-space; remove the cap and you get all of PSPACE via TQBF). The defining belief is that the hierarchy is strict and infinite: each level is conjectured to be strictly larger than the one below, so it does not collapse. But, true to form, this is OPEN. A celebrated conditional fact ties it to P versus NP: if P equals NP, the entire hierarchy collapses down to P, and more generally if any two adjacent levels coincide, everything above them collapses to that level. Caveat: a collapse of PH is considered very unlikely, and is one of the standard reasons researchers believe P is not NP.
A Sigma_2 problem: given a boolean formula, is there a SMALLEST equivalent one of size <= k? This is naturally 'there exists a formula psi of size <= k, such that for all assignments, psi and phi agree'. The leading there-exists then for-all is two alternations, placing it at level 2 of the hierarchy, plausibly above NP.
The polynomial hierarchy stacks alternating exists/for-all quantifiers; level 1 is NP and co-NP, all of it inside PSPACE.
The hierarchy is BELIEVED infinite and strict, but that is OPEN. A key conditional fact: if P = NP (or if any two adjacent levels coincide), the whole hierarchy collapses. Such a collapse is thought very unlikely.