Complexity Classes

Why we need a class (not just a runtime)

When you analyze an algorithm, you can say it runs in $O(n^2)$ time, or $O(n\log n)$ time, etc. That’s useful—but it’s attached to a particular algorithm. Complexity theory asks a different question:

Is the problem itself efficiently solvable?

A complexity class is a set of problems grouped by the resources needed by the best possible algorithms (time, space, randomness, etc.). In this lesson we focus on time and on four names you’ll see constantly:

• •P (polynomial-time solvable)
• •NP (polynomial-time verifiable)
• •NP-hard (at least as hard as NP)
• •NP-complete (the “hardest” problems inside NP)

Decision problems: the standard “unit”

Complexity classes are usually defined for decision problems: the answer is YES or NO.

Examples:

• •PATH: Given a graph $G$ and two vertices $s,t$, is there a path from $s$ to $t$?
• •PRIME: Given an integer $n$, is $n$ prime?
• •SAT: Given a propositional formula $\varphi$, is there an assignment that makes it true?

Why decision problems?

1. 1)They simplify definitions and reductions.
2. 2)Many optimization problems can be converted to decision versions (e.g., “Is there a tour of length ≤ K?”).

Input size: what does “polynomial” mean?

To talk about time, we need a notion of input length, typically denoted $|x|$.

• •For a graph with $n$ vertices and $m$ edges, an adjacency-list encoding has size $\Theta(n+m)$ (up to log factors depending on how vertices are labeled).
• •For an integer $N$, the input size is the number of bits, $|N| = \lfloor \log_2 N \rfloor + 1$.

This matters: an algorithm that is polynomial in the value of $N$ may be exponential in the bit-length of $N$.

Tractability (computational feasibility)

In practice, “efficient” is nuanced. But complexity theory uses a robust proxy:

Polynomial time is considered tractable.

Why? Because polynomials compose well, are stable under reasonable machine models, and scale far better than exponentials.

A mental comparison (not a proof): if $n = 10^6$, then $n^2 = 10^{12}$ might be heavy but imaginable; $2^n$ is completely impossible.

Visualization: the containment map we’ll keep returning to

Below is the conceptual picture we’re building toward (interactive in the tech tree canvas):

1. 1)A big region for “all decision problems.”
2. 2)A subset NP.
3. 3)Inside NP, a subset P (we know $P \subseteq NP$).
4. 4)A subset NP-complete inside NP.
5. 5)A region NP-hard that contains NP-complete and can extend outside NP.

We do not know whether $P = NP$.

This diagram isn’t decoration—it encodes the definitions. In later sections, we’ll use it as a correctness checklist when doing reductions.

Class P: polynomial-time solvable

Definition (P). A decision problem $L$ is in P if there exists a deterministic algorithm that decides $L$ in time polynomial in the input size.

Formally: $L \in P$ if there exists an algorithm $A$ and a polynomial $p(\cdot)$ such that for every input $x$, $A(x)$ halts in at most $p(|x|)$ steps and outputs YES iff $x \in L$.

Intuition: problems in P are the ones we can solve efficiently.

Examples commonly in P:

• •Graph reachability (PATH) via BFS/DFS
• •Minimum spanning tree (as an optimization problem) and its decision variant
• •Maximum flow (and decision variants)
• •Primality testing (PRIME)

NP: polynomial-time verifiable

Definition (NP) via certificates. A decision problem $L$ is in NP if there exists:

• •a polynomial-time verifier $V(x, c)$, and
• •a polynomial bound on certificate size $|c| \le p(|x|)$,

such that:

• •If $x \in L$ (YES instance), then there exists a certificate $c$ making $V(x,c) = \text{YES}$.
• •If $x \notin L$ (NO instance), then for all certificates $c$, $V(x,c) = \text{NO}$.

In logic form:

with $V$ running in polytime and $|c|$ polynomially bounded.

Intuition: NP problems are those where a proposed solution can be checked quickly.

Examples:

• •SAT: certificate = a truth assignment; verifier evaluates the formula.
• •Hamiltonian Cycle (HC): certificate = a cycle listing vertices; verifier checks it is a cycle and uses edges in the graph.
• •Clique: certificate = set of $k$ vertices; verifier checks all pairs are edges.

Why “verifiable” is the right lens

It’s tempting to say NP means “hard.” That’s not the definition.

NP contains problems that might be easy or hard; it’s about the existence of short proofs of “YES.”

• •If a problem is in P, it’s automatically in NP:
• •To verify, just ignore the certificate and solve the problem yourself in polynomial time.

So we know:

Whether the containment is strict is the famous open question.

Equivalent viewpoint: nondeterminism

Another equivalent definition: NP is the class of problems solvable by a nondeterministic Turing machine in polynomial time.

Interpretation:

• •The machine “guesses” a certificate $c$ (nondeterministically).
• •It then verifies deterministically in polynomial time.

This equivalence is conceptually helpful, but in reductions we usually work with the certificate viewpoint.

A key mental move: decision vs search

Many NP problems are naturally search problems (“find an assignment,” “find a tour”). Complexity classes are defined for decision versions.

For SAT:

• •Decision: “Does a satisfying assignment exist?”
• •Search: “Find a satisfying assignment.”

In many settings (including SAT under standard assumptions), decision and search are polynomial-time interreducible, but that’s an extra theorem. For this node, focus on decision formulations.

Visualization: clickable certificate checker

In the canvas, imagine SAT as a card with:

• •Input: formula $\varphi$
• •Certificate: assignment a (vector of bits)
• •Verifier: evaluate $\varphi(**a**)$ in $O(|\varphi|)$

The point is to make NP feel mechanical: you can literally plug in a candidate and check it.

Why reductions are the engine of NP-completeness

Suppose you’re given a new problem $B$ and you suspect it’s hard. Proving “no polynomial algorithm exists” is beyond current techniques for most natural problems.

Instead, complexity theory uses a powerful relative statement:

If $B$ were easy, then a known-hard problem $A$ would also be easy.

That implication is established by a polynomial-time reduction.

Polynomial-time many-one reduction (Karp reduction)

We write:

to mean: there exists a polynomial-time computable function $f$ that maps instances $x$ of $A$ to instances $f(x)$ of $B$ such that:

This “iff” is the invariant you must protect.

Reduction pipeline visualization (the one you should picture)

A reduction is not magic. It’s a program with a contract:

• •Input: instance $x$ of $A$
• •Transform: compute $y = f(x)$ in polytime
• •Output: instance $y$ of $B$
• •Correctness invariant: YES in $A$ iff YES in $B$

In the canvas, this should be a clickable pipeline:

with a live displayed invariant: “YES($x$) ⇔ YES($f(x)$).”

How reductions transfer algorithms (easy direction)

If $A \le_p B$ and $B \in P$, then $A \in P$.

Reason: to decide $A$ on input $x$:

1. 1)Compute $y = f(x)$ in polynomial time.
2. 2)Run the polytime decider for $B$ on $y$.

Polynomial + polynomial = polynomial.

This is why we say:

• •If $A \le_p B$, then $B$ is at least as hard as $A$.

NP-hard and NP-complete

Now we can define hardness precisely.

Definition (NP-hard). A problem $H$ is NP-hard if for every problem $A \in NP$, we have $A \le_p H$.

Interpretation: $H$ is at least as hard as every NP problem.

Definition (NP-complete). A problem $C$ is NP-complete if:

1. 1)$C \in NP$, and
2. 2)$C$ is NP-hard.

Interpretation: NP-complete problems are the “hardest problems in NP.”

The containment picture (explicitly tied to definitions)

• •P sits inside NP because solving implies verifying.
• •NP-complete sits inside NP by definition.
• •NP-hard contains all NP-complete problems, but may include problems outside NP (e.g., certain optimization problems or even undecidable problems).

A concrete reminder:

• •The optimization version of TSP (“find the shortest tour”) is NP-hard, but it is not a decision problem in NP as stated.
• •The decision version (“Is there a tour of length ≤ K?”) is in NP and is NP-complete.

The standard NP-completeness proof recipe

To prove a new decision problem $B$ is NP-complete:

1. 1)Membership: show $B \in NP$ by describing a polynomial-size certificate and a polynomial-time verifier.
2. 2)Hardness: pick a known NP-complete problem $A$ and show $A \le_p B$.

Notice the direction: reduce from a known-hard problem to your target problem.

A common mistake is to reverse it. If you show $B \le_p A$, that only says $B$ is no harder than $A$.

What if P = NP?

If $P = NP$, then every NP problem (including NP-complete ones) has a polynomial-time algorithm. The reduction machinery still works, but the interpretation of “hard” changes.

If $P \ne NP$, then NP-complete problems are not in P.

We don’t know which world we live in.

Why this matters in practice

Once you can classify problems as P, NP, NP-complete, or NP-hard, you gain a practical workflow:

• •If a problem is in P, invest in better implementations, constants, and data structures.
• •If a problem is NP-complete/NP-hard, stop hoping for a generic fast exact algorithm and pivot to:
• •approximation algorithms,
• •heuristics,
• •fixed-parameter tractability (FPT),
• •special-case structure (planarity, bounded treewidth, etc.),
• •or problem relaxations.

Complexity classes become a decision-making tool.

A complete end-to-end reduction: 3SAT ≤ₚ CLIQUE

We’ll do a full reduction with the reduction pipeline mindset.

Step 0: define the two problems

3SAT

• •Input: a 3-CNF formula $\varphi$ with clauses $C_1,\dots,C_m$, each clause has exactly 3 literals.
• •Question: does there exist an assignment that satisfies all clauses?

CLIQUE

• •Input: an undirected graph $G=(V,E)$ and integer $k$.
• •Question: does $G$ have a clique of size at least $k$?

A set $S \subseteq V$ is a clique if for all distinct $u,v \in S$, $(u,v) \in E$.

Step 1: the high-level idea (why this reduction should exist)

A satisfying assignment for 3SAT picks, for each clause, at least one literal that is made true. That resembles selecting one “compatible” choice per clause.

A clique enforces pairwise compatibility: every chosen literal must be consistent with every other chosen literal.

So we’ll build a graph where:

• •vertices correspond to literals inside clauses, and
• •edges connect literals from different clauses unless they conflict.

Then a clique of size $m$ corresponds to picking one non-conflicting literal from each clause—exactly what we need for satisfiability.

Step 2: define the reduction function f

Input: $\varphi$ with clauses $C_1,\dots,C_m$.

Construct a graph $G$ as follows:

• •For each clause $C_i$ and each literal ℓ in $C_i$, create a vertex labeled $(i,\ell)$.
• •So there are $3m$ vertices.
• •Add an edge between two vertices $(i,\ell)$ and $(j,\ell')$ if:

1. 1)$i \ne j$ (different clauses), and
2. 2)ℓ and ℓ′ are not contradictory (i.e., it is not the case that ℓ is $x$ and ℓ′ is $\neg x$ for the same variable $x$).

Set $k = m$.

Output: $(G,k)$.

This is clearly polynomial-time to build: $O(m^2)$ literal-pair checks, each check constant-time with a suitable encoding.

Step 3: prove the correctness invariant (YES iff YES)

We must prove:

We’ll do both directions carefully.

##### (⇒) If ϕ is satisfiable, then G has a clique of size m

Assume $\varphi$ is satisfiable. Then there exists an assignment that makes every clause true.

For each clause $C_i$, pick one literal ℓᵢ in $C_i$ that is true under this assignment.

Now consider the set of vertices:

We claim $S$ is a clique of size $m$.

Take any two distinct vertices $(i,\ell_i)$ and $(j,\ell_j)$ with $i\ne j$.

• •They are from different clauses, so condition (1) for an edge is satisfied.
• •Can they be contradictory? If ℓᵢ is $x$ and ℓⱼ is $\neg x$, then $x$ would have to be simultaneously true and false under the assignment—impossible.

So ℓᵢ and ℓⱼ are not contradictory, therefore condition (2) holds and the edge exists.

Thus every pair in $S$ is connected: $S$ is a clique. And $|S| = m$, so $G$ has a clique of size $k=m$.

##### (⇐) If G has a clique of size m, then ϕ is satisfiable

Assume $G$ has a clique $S$ with $|S|=m$.

Key observation: edges only connect vertices from different clauses. That means:

• •In any clique, you can include at most one vertex from a given clause, because two vertices from the same clause have $i=j$ and thus no edge.

Since $S$ has size $m$ and there are $m$ clauses, $S$ must contain exactly one vertex from each clause.

So we can write:

Because $S$ is a clique, every pair is connected by an edge, so no two literals among $\ell_1,\dots,\ell_m$ are contradictory.

Now we build an assignment:

• •For each variable $x$:
• •if any chosen literal equals $x$, set $x=\text{true}$
• •else if any chosen literal equals $\neg x$, set $x=\text{false}$
• •otherwise set $x$ arbitrarily.

This assignment is well-defined: we never choose both $x$ and $\neg x$ among the $\ell_i$ because that would create a contradiction, and contradictory literals are not connected by an edge—so they cannot both appear in the clique.

Finally, does this assignment satisfy $\varphi$?

• •In each clause $C_i$, the clique selected a literal $\ell_i$ from that clause.
• •Our assignment sets $\ell_i$ to true (by construction).
• •Therefore each clause has at least one true literal, hence all clauses are satisfied.

So $\varphi$ is satisfiable.

We have proven the invariant, so 3SAT ≤ₚ CLIQUE.

Connecting back to NP-completeness and the diagram

• •CLIQUE is in NP: certificate = set of $k$ vertices; verifier checks all pairs are edges.
• •Since 3SAT is NP-complete and 3SAT ≤ₚ CLIQUE, CLIQUE is NP-hard.
• •Combining NP-hardness with membership gives: CLIQUE is NP-complete.

In the containment visualization:

• •3SAT sits in NP-complete.
• •The arrow (reduction pipeline) points to CLIQUE, pulling CLIQUE into NP-hard.
• •The certificate checker puts CLIQUE into NP.
• •So CLIQUE lands inside NP-complete.

This is what “reduction machinery” looks like when you run it end-to-end.