the great open problems
For all the theorems this subject has proved, its most famous questions remain stubbornly open — and not for lack of trying by brilliant people over decades. The honest map of the theory of computation has large regions marked 'we strongly believe X, but we cannot prove it'. Knowing where these frontiers are is not a failure to teach; it is the most truthful and exciting part of the whole story.
The crown jewel is P versus NP: is every problem whose solution can be quickly checked also one whose solution can be quickly found? Almost everyone believes P is not equal to NP (that checking is genuinely easier than solving), but no proof exists either way, and it carries a million-dollar prize. It is far from alone. NL versus P asks whether log-space computation is strictly weaker than polynomial time (believed yes, unproven). BPP versus P asks whether randomness adds power (believed no — P = BPP — via the derandomization program, unproven). The true power of quantum computing is open: we do not know exactly how BQP relates to classical classes, only that quantum computers are not believed to crack all of NP. Even P versus PSPACE, intuitively obvious that polynomial time is weaker than polynomial space, is unproven.
Why have these resisted proof for so long? Part of the answer is itself a theorem: results like relativization, natural proofs, and algebrization are 'barrier' theorems showing that whole familiar families of proof techniques are provably too weak to settle P vs NP — so a successful proof must use genuinely new ideas we do not yet have. The few separations we DO know come from a small set of powerful tools: the time and space hierarchy theorems prove that strictly more time or space buys strictly more power (so P is genuinely smaller than EXPTIME, a proven separation), and diagonalization gives us undecidability. The gap between the little we can prove and the lot we firmly believe is the living edge of the field, and an honest teacher names it plainly.
Contrast what is known with what is believed. PROVEN by the time hierarchy theorem: P is strictly smaller than EXPTIME — there really are problems solvable in exponential time but not polynomial time. OPEN, despite universal belief: whether P is strictly smaller than NP. We can separate classes that are far apart on the resource scale, but the classes packed close together (P, NP, PSPACE) stubbornly resist separation.
P vs NP and its kin are believed, not proved; only widely-separated classes (P vs EXPTIME) are provably distinct.
Most inclusions between complexity classes (P vs NP, NL vs P, BPP vs P, P vs PSPACE) are CONJECTURED, not proved. Only a few separations are actually known — chiefly the hierarchy theorems, which give P strictly inside EXPTIME. Beware sources that state these open questions as settled facts.