04
PSPACE and Beyond
Chapter 4 • Advanced
120 min
PSPACE and Beyond
Complexity Classes
P
Problems solvable in polynomial time.
NP
Problems verifiable in polynomial time.
PSPACE
Problems solvable in polynomial space.
EXPTIME
Problems solvable in exponential time.
Relationships
P ⊆ NP ⊆ PSPACE ⊆ EXPTIME
PSPACE-Complete Problems
Quantified Boolean Formula (QBF)
Given formula with quantifiers (∀, ∃), is it true?
Geography
Game on directed graph.
Planning
AI planning problems.
Practice Problems
- Identify complexity class
- PSPACE-complete problems
- Complexity hierarchy