Computational Complexity Classes - Complete Guide

Fundamental Complexity Classes

P (Polynomial Time)

Problems that can be solved in polynomial time by a deterministic Turing machine. These are considered "tractable" or efficiently solvable.

Examples: Sorting, shortest path, linear programming

NP (Nondeterministic Polynomial Time)

Problems whose solutions can be verified in polynomial time. If someone gives you a proposed solution, you can check whether it's correct efficiently.

Contains P, but may be larger. P vs NP is the million-dollar question.

NP-Hard

Problems that are at least as hard as the hardest problems in NP. An NP-hard problem doesn't have to be in NP itself. If you could solve any NP-hard problem efficiently, you could solve all problems in NP efficiently.

Key: Every NP-complete problem is NP-hard, but not all NP-hard problems are NP-complete.

NP-Complete

Problems that are both in NP and NP-hard. These are the hardest problems in NP. They serve as the "gatekeepers" - if any NP-complete problem is in P, then P = NP.

Examples: Boolean satisfiability (SAT), traveling salesman, graph coloring

Important Broader Classes

EXPTIME (Exponential Time)

Problems that can be solved in exponential time (O(2^p(n)) for some polynomial p). This class is provably larger than P.

We know P ≠ EXPTIME - there are definitely problems harder than P.

PSPACE

Problems that can be solved with a polynomial amount of memory/space, regardless of time. PSPACE contains all of NP, and is contained in EXPTIME.

Many two-player games (like generalized chess) are PSPACE-complete.

co-NP

The class of problems where the "no" answer can be verified in polynomial time. For example, "is this boolean formula unsatisfiable?" - if it's unsatisfiable, there's a short proof.

We don't know if NP = co-NP, though most believe they're different.

Practical Classification Concepts

Tractable

Problems that are feasible to solve in practice for reasonable input sizes. Formally, this generally means problems in P.

In practice: problems we can solve for real-world inputs.

Intractable

Problems that are not feasible to solve exactly for large inputs. This includes NP-complete, NP-hard, and exponential-time problems.

In practice: we often use approximations or heuristics.

Unsolvable

Problems that cannot be solved by any algorithm, regardless of time or memory constraints.

Examples: Halting problem, determining if two programs are equivalent.

Known Relationships

P ⊆ NP ⊆ PSPACE ⊆ EXPTIME

P ≠ EXPTIME (this is proven - there's definitely a hierarchy)

NP-hard contains all of NP and possibly harder problems

Unsolvable problems exist outside this entire hierarchy

Visual Hierarchy

EXPTIME (definitely harder than P)

PSPACE (polynomial space, possibly more than NP)

NP (easy to verify)

P (easy to solve)

NP-hard overlaps with all of these and extends beyond