Complexity Class Hierarchy
You'll learn how major complexity classes relate to each other and which separations computer scientists have actually proven.
Understanding the Hierarchy
Now that you've met P, NP, PSPACE, and EXP individually, let's see how they fit together. Think of these classes as nested boxes, where each box contains all the problems solvable within certain resource limits.
The established containment relationships are:
P ⊆ NP ⊆ PSPACE ⊆ EXP
This reads: "Every problem in P is also in NP, every problem in NP is also in PSPACE, and every problem in PSPACE is also in EXP."
What We Know vs. What We Suspect
Here's where it gets interesting—and frustrating! We strongly suspect all these containments are strict (meaning P ≠ NP, NP ≠ PSPACE, etc.), but we haven't proven most of them.
What's Actually Proven:
- P ⊆ PSPACE (proven to be strict by Savitch's Theorem and other results)
- P ⊆ EXP (strictly, proven via time hierarchy theorem)
What Remains Open:
- P vs. NP — the million-dollar question!
- NP vs. PSPACE
- PSPACE vs. EXP
Think of it like knowing Earth is smaller than Jupiter, which is smaller than the Sun, but not being able to prove whether a basketball is smaller than a beach ball—that's how perplexing these open questions are!
Why This Matters
This hierarchy helps us classify computational difficulty. When you prove a problem is in P, you've placed it in the "efficiently solvable" box. When it's NP-complete, you know it sits at NP's boundary, likely requiring exponential time in the worst case.
Key Takeaway: The complexity class hierarchy shows P ⊆ NP ⊆ PSPACE ⊆ EXP, but only some separations (P ≠ PSPACE, P ≠ EXP) have been proven—the P vs. NP question remains open.