Course contentsShow
← Computer Science
Lesson 1897 of 2,87243. Complexity TheoryFree lesson

Complexity Class Hierarchy

Visualizing the known relationships: P ⊆ NP ⊆ PSPACE ⊆ EXP and what separations have been proven.

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.