Polynomial reductions, NP-completeness, and honest limits

Prerequisites: P, NP, certificate verification, graphs, and logical formulas.

Learning objectives

• State and prove both directions of a polynomial reduction.
• Separate NP-hardness from NP-completeness.
• Interpret worst-case hardness without rejecting useful restricted solutions.

A reduction transfers algorithms

A polynomial-time many-one reduction from decision problem A to B computes an instance f(x) in polynomial time such that x is a yes instance of A exactly when f(x) is a yes instance of B. If B has a polynomial-time solver, compose it with f to solve A in polynomial time. Both the time to produce f(x) and the size of the produced instance must respect the polynomial bound.

A problem is NP-hard when every problem in NP reduces to it under the chosen reduction notion. It is NP-complete when it is both NP-hard and in NP. Hardness alone does not prove membership in NP, and a polynomial verifier alone does not prove hardness. A complete argument needs the two obligations separately.

Work through a concrete construction

Consider a Boolean formula in conjunctive normal form with three literals per clause. Construct a graph with one vertex for each literal occurrence. Connect two vertices exactly when they come from different clauses and their literals are not contradictory. Ask whether the graph has a clique whose size equals the number of clauses. A clique is a set of vertices with all pairs adjacent.

If the formula is satisfiable, select one true literal occurrence from each clause. No selected pair contradicts, so the selected vertices form the required clique. Conversely, a clique of that size must select one occurrence from each clause because vertices from the same clause are not connected. Its selected literals are mutually consistent, so assign them true and extend the assignment arbitrarily to remaining variables. Every clause has a selected true literal, satisfying the formula.

The graph has three times as many vertices as clauses and at most quadratically many edges. Building it is polynomial. This establishes the needed transformation from 3-SAT to clique; using the known NP-completeness of 3-SAT supplies the hardness premise. Checking a proposed clique is also polynomial, establishing clique's NP membership.

Hardness is a precise worst-case statement

NP-completeness does not prove exponential time is necessary unless additional unresolved assumptions are settled. It also does not say every instance is difficult. Restricted graph families, small parameters, approximation algorithms, and heuristics can be useful. Their guarantees differ: an approximation bound concerns solution quality, while a heuristic may have no such bound. Report the problem variant, input range, algorithmic guarantee, and observed performance separately. A successful benchmark cannot erase a worst-case theorem, and a worst-case theorem cannot predict the runtime of every practical instance.

Practice problem

Construct the literal-occurrence graph for the formula (x OR y OR z) AND (NOT x OR y OR NOT z). Label vertices by both clause and literal. Exhibit a clique of size two and a corresponding satisfying assignment. Explain why no edges are added within a clause and why contradictory literals across clauses must not be adjacent. Then list the separate proof obligations required to claim a new problem is NP-complete, including which direction a known hard problem must reduce.

Worked solution

Create six vertices, three for each clause. Add cross-clause edges except between x and NOT x, or z and NOT z; the two y occurrences are compatible and therefore adjacent. Selecting the y occurrence from each clause gives a size-two clique and is satisfied by y=true, with x and z arbitrary. Omitting within-clause edges forces a clique of the target size to cover distinct clauses. Omitting contradictory pairs ensures its selected literals can be simultaneously true. To prove a new problem B NP-complete, first give a polynomial certificate verifier for B. Then reduce a known NP-hard problem A into B, proving the transformation is polynomial and preserves yes and no instances through an if-and-only-if argument. A reduction in the reverse direction does not establish the required hardness.

Check your understanding

What additional fact is needed after proving a problem NP-hard to call it NP-complete?

• It belongs to NP.
• It has no useful heuristic.
• Every instance takes exponential time.

Explanation

NP-completeness combines NP-hardness with polynomially verifiable yes certificates.

What does NP-completeness currently justify about exact polynomial-time algorithms?

• They have been proved impossible.
• One would imply P=NP, which remains unresolved.
• They exist for every NP-complete problem.

Explanation

A polynomial solver for any NP-complete problem would yield polynomial solvers for all NP problems.

Primary reading

• Automata, Computability, and Complexity: MIT OpenCourseWare

Open the study and save your work →