Reductions, NP-Completeness & NP-Hardness

A reduction is a compiler between decision problems. It converts every instance of problem $A$ into an instance of problem $B$ while preserving the yes/no answer. If the compiler is efficient, an efficient solver for $B$ would yield one for $A$. NP-completeness organizes thousands of apparently different problems around this transferable difficulty—but it supplies conditional evidence, not an unconditional exponential lower bound.

Start with languages and encodings #

A decision problem is represented by a language $A\subseteq\Sigma^*$: strings in $A$ are yes-instances. Graphs, formulas, and schedules therefore need explicit encodings. Polynomial time is measured in the encoded length $|x|$, so a numeric parameter written in binary has length $\Theta(\log n)$, while unary representation has length $\Theta(n)$. Changing encoding can change whether an algorithm is polynomial; reasonable encodings are polynomially interconvertible, but binary and unary encodings are deliberately not equivalent in that sense.

Recall the class boundary:

• $P$: a deterministic algorithm decides membership in polynomial time.
• $NP$: yes-instances have polynomial-size certificates verifiable in deterministic polynomial time; equivalently, a nondeterministic Turing machine decides the language in polynomial time.
• $coNP$: complements of languages in $NP$.

$NP$ means nondeterministic polynomial time, not "non-polynomial." We know $P\subseteq NP\cap coNP$; whether $P=NP$ remains open.

Polynomial-time many-one reduction #

For languages $A$ and $B$,

$$A\le_m^p B$$

means that a polynomial-time computable function $f$ exists such that, for every input $x$,

$$x\in A\quad\Longleftrightarrow\quad f(x)\in B.$$

The biconditional is essential: yes-instances map to yes-instances and no-instances to no-instances. The solver composition is

flowchart TD
    X["Instance x of A"] -->|"polynomial f"| FX["Instance f(x) of B"]
    FX --> SB["Hypothetical solver for B"]
    SB --> ANS["Same yes/no answer for A"]

Therefore, if $A\le_m^pB$ and $B\in P$, then $A\in P$. Read the arrow as $A$ is no harder than $B$ or $B$ is at least as hard as $A$.

Many-one reductions are reflexive and transitive. If $A\le_m^pB$ via $f$ and $B\le_m^pC$ via $g$, then $x\mapsto g(f(x))$ is polynomial because the length of $f(x)$ is polynomially bounded and polynomial compositions remain polynomial.

NP-hard versus NP-complete #

NP-hard problems need not be decision problems and need not belong to $NP$; optimization versions are often called NP-hard by reduction from their decision versions. Some undecidable problems are NP-hard as well. NP-complete is the narrower intersection: the hardest decision languages inside $NP$ under the specified reduction.

The phrase "under the specified reduction" matters. A polynomial-time Turing reduction may ask an oracle several adaptive questions; a many-one reduction produces one instance and preserves its answer directly. Cook's original terminology used an oracle-style reduction, while the modern default definition of NP-completeness uses polynomial-time many-one reductions. Never merge results across these notions without naming the reduction type.

Cook–Levin: bounded computation becomes a formula #

The Cook–Levin theorem establishes that Boolean satisfiability is NP-complete. Membership is immediate: a truth assignment is a polynomial-size certificate, and evaluating a formula is polynomial.

For hardness, take any $A\in NP$. A nondeterministic machine $M$ decides $A$ in time $p(n)$. A complete accepting run on input $x$ can be drawn as a tableau:

• each row is one machine configuration;
• the first row encodes the initial configuration on $x$;
• adjacent rows must obey one transition of $M$;
• some row is accepting;
• the tableau has polynomially many cells because the time and visited tape region are polynomially bounded.

Introduce Boolean variables describing the symbol, state, and head position in every cell. Add local clauses asserting:

1. exactly one compatible symbol/state choice per location;
2. the correct initial row;
3. at least one accepting state;
4. every small window between adjacent rows is a legal transition.

The resulting formula $F_{M,x}$ has polynomial size, is constructible in polynomial time, and is satisfiable exactly when $M$ has an accepting computation on $x$. The key idea is local checkability: a globally valid computation history is determined by polynomially many constant-size consistency constraints.

Cook's 1971 paper framed the result using tautology and its contemporary reduction terminology; the standard Cook–Levin presentation is the equivalent SAT/CNF many-one formulation.

Worked reduction: 3-SAT to CLIQUE #

Let a 3-CNF formula have clauses $C_1,\ldots,C_k$. Build a graph:

1. Create one vertex for each literal occurrence in each clause.
2. Connect two vertices when they come from different clauses and their literals are not contradictory.
3. Ask whether the graph contains a clique of size $k$.

Why it works:

• If the formula is satisfiable, choose one true literal from every clause. No two chosen literals contradict, so all chosen vertices are adjacent and form a $k$-clique.
• If a $k$-clique exists, it contains at most one vertex per clause because vertices within a clause are not connected. With $k$ clauses it therefore chooses exactly one mutually compatible literal from each. Assign those literals true and extend consistently to the other variables; every clause is satisfied.

For

$$(x\lor\neg y\lor z)\land(\neg x\lor y\lor z)\land(x\lor y\lor\neg z),$$

the occurrences $x$ from clause 1, $y$ from clause 2, and $x$ from clause 3 form a 3-clique. They are pairwise compatible and give a satisfying partial assignment $x=y=\text{true}$.

The construction has $3k$ vertices and at most $O(k^2)$ candidate edges, so it is polynomial. Both the size analysis and the reverse implication belong in the proof; a persuasive picture alone is not a reduction.

The reusable proof template #

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

1. Specify an encoding and the exact decision question. Optimization and search variants are not interchangeable with the language.
2. Show $B\in NP$. Give a certificate, bound its length polynomially, and describe a polynomial-time verifier.
3. Choose known NP-complete $A$. Select a source problem whose structure matches $B$.
4. Construct $f(x)$. State every generated object and prove its encoded size and construction time are polynomial.
5. Prove both directions. Show $x\in A\Rightarrow f(x)\in B$ and $f(x)\in B\Rightarrow x\in A$.
6. Conclude NP-hardness, then combine with membership. Do not call $B$ NP-complete after proving only one half.

For reductions involving a numeric threshold, also ensure the threshold itself has polynomial encoded length. Creating an object whose value is exponential can be fine if represented compactly; explicitly writing exponentially many objects is not.

Weak and strong NP-completeness #

An algorithm running in time polynomial in numeric values such as capacity $W$, but not in their bit length $\log W$, is pseudopolynomial. This distinction motivates:

• weakly NP-complete: hardness may rely on exponentially large numeric values under binary encoding, and a pseudopolynomial algorithm may exist;
• strongly NP-complete: the problem remains NP-complete even when relevant numbers are polynomially bounded (or unary-encoded under the standard formulation).

This terminology is about how numerical magnitude participates in hardness. It does not mean that a weakly NP-complete problem is known to have a polynomial-time algorithm.

What an NP-completeness result licenses #

If any NP-complete language is in $P$, then every language in $NP$ is in $P$, so $P=NP$. Conversely, if $P\ne NP$, no NP-complete language is in $P$.

It does not establish:

• that the problem requires exponential time—no such general lower bound follows;
• that every instance is difficult—special cases, parameters, and distributions may be tractable;
• that approximation or heuristics are useless—the reduction concerns exact worst-case decision;
• that $NP$ is the complement of $P$—the complement class is $coNP$;
• that a fast verifier can certify no-instances—$NP$ only promises certificates for yes-instances;
• that an observed exponential algorithm is optimal.

Auditing a claimed reduction #

Ask these questions in order:

1. What are the source and target languages, including encodings?
2. Which reduction notion is used—many-one, Turing, randomized, parameterized?
3. Is the direction correct for the desired claim?
4. Is the transformation total and polynomial in input length?
5. Does the biconditional hold, including edge cases and malformed inputs?
6. Is membership in $NP$ separately established before saying NP-complete?
7. Does the conclusion remain conditional on $P\ne NP$, rather than pretending that separation is already known?

This checklist catches most flawed arguments: reversed arrows, one-way constructions, exponential output, optimization/decision drift, and the unjustified leap from "hard in practice" to NP-hard.