NP-Hard and NP-Complete Problems
Open in the Padhaiko app7.1 Basic concepts
Computational complexity classifies decision problems (yes/no problems) according to whether they can be solved or verified in polynomial time ( for some constant ) as a function of input encoding size .
Complexity Classes P, NP, NP-Hard, and NP-Complete
- Class (Polynomial Time): The set of all decision problems solvable by a deterministic algorithm (or Turing machine) in polynomial time . Examples: Sorting, Shortest Path, Minimum Spanning Tree, 2-SAT.
- Class (Non-deterministic Polynomial Time): The set of all decision problems solvable by a non-deterministic algorithm in polynomial time—equivalently, decision problems whose "Yes" instances possess a polynomial-length certificate that can be verified deterministically in polynomial time. Clearly .
- Polynomial-Time Reduction (): Problem is polynomial-time reducible to if there exists a deterministic polynomial-time computable function mapping every instance of to an instance of such that . Thus .
- -Hard: A problem (decision or optimization) is -hard if every problem reduces to in polynomial time ( for all ). An NP-hard problem need not belong to (e.g., optimization TSP or the Halting Problem).
- -Complete (): A problem is -complete iff:
- , and
- is -hard ( for all , or equivalently some known problem reduces to in polynomial time).
| Aspect | P vs. NP | NP-Hard vs. NP-Complete |
|---|---|---|
| Core Meaning | : efficiently solvable; : efficiently verifiable | -Complete -Hard |
| Membership in | (whether is open) | -Complete ; -Hard may lie outside |
| Consequence if in | If any problem is in , then | Proving requires showing and |
7.2 Cook's theorem
Before any problem can be proved -complete by reduction from another -complete problem, one first problem had to be proved -hard directly from the definition of . Stephen Cook (1971) and Leonid Levin (1973) established this foundation using Boolean Satisfiability (SAT).
Cook's Theorem (Cook-Levin Theorem)
The Satisfiability problem (SAT)—given a Boolean formula in conjunctive normal form (CNF), decide whether there exists a truth assignment to its variables making true—is -complete.
Proof
- : Given a candidate truth assignment (certificate) for the variables, substituting and evaluating every clause takes deterministic polynomial time.
- is -hard: Let be decided by a non-deterministic Turing machine in polynomial time on input of length . Construct in polynomial time a CNF formula over Boolean variables representing the tape cell contents, head positions, and machine states across all time steps :
Each part has size (or ), and is satisfiable if and only if has an accepting computation path on . Hence for every .
Starting from Cook's Theorem, the classic chain of polynomial reductions proves thousands of problems -complete:
7.3 NP-Hard graph problems
Many classical graph decision and optimization problems are -complete (decision form) or -hard (optimization form):
| Problem | Decision Formulation | Reduction Source |
|---|---|---|
Clique (CDP) | Does contain a complete subgraph of size ? | (one vertex per literal, edges between non-conflicting literals in different clauses) |
Vertex (Node) Cover (NCDP) | Does have a subset of size touching every edge? | ( has a -clique has a vertex cover of size ) |
Chromatic Number (CNDP) | Can be properly colored using at most colors? | (truth gadgets + triangle palette) |
Hamiltonian Cycle (HC) | Does contain a simple cycle visiting every vertex once? | |
Travelling Salesperson (TSP) | Does a weighted complete graph have a Hamiltonian tour of cost ? | (weight for edges in , for non-edges, bound ) |
1
Using the standard reduction , construct the graph for the -CNF formula with clauses:
and identify a -clique in along with the corresponding satisfying truth assignment.
Constructing vertices and edges of :
- Vertices ( vertices): Create one vertex for each literal occurrence in clause :
- Clause : , ,
- Clause : , ,
- Clause : , , .
- Edges: Connect vertex and iff they belong to different clauses () and are not logical negations of each other ().
Finding a -clique and extracting the assignment: Pick one consistent literal per clause:
- From :
- From : (compatible with )
- From : (compatible with both and ).
Since , , and are pairwise non-contradictory and in distinct clauses, forms a -clique in . Setting (and or ) satisfies all three clauses of .
Graph has vertices across clause groups; the -clique maps directly to the satisfying assignment .
7.4 NP-Hard scheduling problems
Many practical processor and workshop scheduling formulations are -hard:
- Scheduling Identical Processors (): Given independent jobs with processing times and identical parallel processors, assign jobs to processors to minimize the makespan (maximum completion time across all processors).
- For , deciding whether makespan is identical to the Partition problem (), proving even -processor makespan minimization is NP-hard.
- Job-Shop and Flow-Shop Scheduling ( machines): While -machine flow shop scheduling () is solvable in via Johnson's rule, -machine flow-shop scheduling () and general job-shop scheduling () are NP-hard (via reduction from 3-Partition).
- Scheduling with Deadlines and Penalties: Choosing a subset of jobs with arbitrary processing times , deadlines , and penalties to minimize total late penalty on a single machine is NP-hard (reducible from 0/1 Knapsack / Partition).
7.5 NP-Hard code generation problems
In compiler design, optimal code generation translates an intermediate expression representation into machine instructions using a fixed finite number of CPU registers so as to minimize total instructions (or memory spills).
- Expression Trees (Solvable in ): When an expression has no common subexpressions (represented as a tree), the Sethi-Ullman (Ershov) labeling algorithm determines the exact minimum number of registers and generates optimal spill-free code in linear time .
- Expression DAGs with Common Subexpressions (NP-Hard): When subexpressions are shared and computed once, the expression forms a Directed Acyclic Graph (DAG). Deciding whether a given expression DAG can be evaluated with zero spills (or minimum instructions) on registers is NP-complete / NP-hard (proved by reduction from 3-SAT or Feedback Vertex Set / Vertex Cover), because choosing the evaluation order of shared nodes trades off register pressure against recomputation.
7.6 Simplified NP-hard problems
Small structural or parameter restrictions frequently separate an -hard problem from a polynomial-time () special case ("simplified" problems):
| NP-Hard / NP-Complete Problem | Simplified Special Case in | Reason for Tractability |
|---|---|---|
| 3-SAT (3 literals/clause) | 2-SAT (2 literals/clause) | Implication graph + Strongly Connected Components in |
| 3-Colorability () | 2-Colorability (Bipartiteness) | Simple BFS/DFS parity check in |
| Hamiltonian Cycle (visit every vertex once) | Eulerian Cycle (traverse every edge once) | Degree parity check (all degrees even + connected) in |
| Longest Simple Path | Shortest Simple Path (non-negative weights) | Dijkstra / Bellman-Ford in polynomial time |
| 0/1 Knapsack (integer items) | Fractional Knapsack (or small unary ) | Greedy by in |
| General Vertex Cover | Vertex Cover on Trees / Bipartite Graphs | Tree DP in / König's theorem via max matching |
| -Machine Flow Shop () | -Machine Flow Shop () | Johnson's rule in |
7.7 Approximation algorithms: -approximation, polynomial time approximation scheme, probabilistically good algorithms
Because -hard optimization problems have no known polynomial-time exact algorithms (unless ), we design polynomial-time approximation algorithms with provable quality guarantees.
Approximation Ratio, PTAS, FPTAS, and Probabilistic Algorithms
Let be the optimal objective value on instance and be the value returned by a polynomial-time approximation algorithm:
- -Approximation Algorithm: For inputs of size , the solution stays within factor of optimal:
- -Approximation Algorithm: An algorithm satisfying the relative error bound for a fixed constant :
(equivalently for minimization, or for maximization).
- Polynomial-Time Approximation Scheme (PTAS): A family of -approximation algorithms taking any as input and running in polynomial time in for each fixed , e.g. or .
- Fully Polynomial-Time Approximation Scheme (FPTAS): A PTAS whose running time is polynomial in both and , e.g. .
- Probabilistically Good (Randomized Approximation) Algorithm: Uses random choices so that for every input instance, it runs in polynomial time and produces a solution within the desired approximation ratio (or exact optimum) with high probability (e.g., , boostable by independent repetitions).
7.8 Vertex cover problem, subset sum problem
2-Approximation Algorithm for Vertex Cover
A vertex cover of is a subset such that every edge has at least one endpoint in .
// Repeatedly pick an arbitrary uncovered edge (u, v) and add BOTH u and v to C
void approxVertexCover(int V, int E, int u_edge[], int v_edge[], int inCover[]) {
for (int i = 0; i < V; i++) inCover[i] = 0;
for (int e = 0; e < E; e++) {
int u = u_edge[e], v = v_edge[e];
if (!inCover[u] && !inCover[v]) {
inCover[u] = 1;
inCover[v] = 1;
}
}
}2-Approximation Guarantee for Vertex Cover
approxVertexCover runs in time and returns a vertex cover of size at most , where is an optimal minimum vertex cover.
Proof
Let be the set of edges picked by the algorithm. No two edges in share an endpoint (since adding removes all edges incident to or ). Any valid vertex cover—including —must include at least one endpoint of every edge in , so . Meanwhile, the algorithm adds both endpoints of each edge in , giving .
2
Run approxVertexCover on the -vertex graph with edges (processed in that exact order), compare the output size against an optimal vertex cover , and compute the achieved approximation ratio.
Tracing approxVertexCover in edge order:
- Edge is uncovered add to (). Covered edges now: .
- Edge : vertex (already covered).
- Edge : vertex (already covered).
- Edge is uncovered () add to ().
- Edges and : vertices (both already covered).
Algorithm terminates with , .
Comparing with optimal : The three edges , , and are pairwise vertex-disjoint (share no endpoints), so every valid vertex cover must pick at least one vertex from each—meaning . Conversely, covers all edges with . Hence the achieved approximation ratio is .
approxVertexCover returns (). Since are disjoint, an optimal cover is (), giving an achieved ratio of .
Subset Sum Problem and Its FPTAS (APPROX-SUBSET-SUM)
Given positive integers and target , the Subset Sum optimization problem finds a subset maximizing .
- Exact Exponential DP: Maintain sorted list of all achievable subset sums using : filtered to . In the worst case .
- FPTAS via Trimming (
APPROX-SUBSET-SUM): After each merge, trim with parameter : remove any element if an earlier retained element already approximates closely (). Trimming keeps , yielding total running time (or polynomial in and ) while guaranteeing the returned sum satisfies (or ).
3
Trace APPROX-SUBSET-SUM with , target , and (so ). Compare the approximate answer against the exact optimum .
Steps and (using trim factor ):
- Init: .
- (): Merge . Trim (): .
- (): Merge . Trim: keep ; keep ; since , trim ; keep . .
Steps and :
- (): Merge . Trim ( trim ) and drop : .
- (): Merge . Trim (, , ) and drop : .
Maximum returned sum , well within of the exact optimum (actual relative error ).
APPROX-SUBSET-SUM returns (exact optimum is ; relative error ).
Exercises
Exercises — NP-Hard and NP-Complete Problems
Define the complexity classes , , -Hard, and -Complete, and state Cook's Theorem along with its role in proving new problems -complete.
Definitions of complexity classes:
- : Decision problems solvable in deterministic polynomial time.
- : Decision problems verifiable in deterministic polynomial time (equivalently, solvable in non-deterministic polynomial time).
- -Hard: Problems such that every reduces to in polynomial time ().
- -Complete: Problems in that are also -hard.
Cook's Theorem and reduction proofs: Cook's Theorem proves directly from Turing machine encodings that SAT is -complete. Once SAT is established as -complete, proving any new problem only requires two steps: (1) show (give a polynomial-time verifier), and (2) reduce a known -complete problem to in polynomial time ().
, and -Complete -Hard. Cook's Theorem proved SAT is -complete from first principles, enabling subsequent proofs via polynomial reductions .
Show how reduces in polynomial time to (). Illustrate the reduction on a -vertex graph containing a -clique (with edges ), giving the corresponding vertex cover in .
Reduction construction (): Given , construct the complement graph where and , and ask whether has a vertex cover of size :
- If is a -clique in , then no edge in has both endpoints in . Hence every edge in has at least one endpoint in , so is a vertex cover of of size .
- If is a vertex cover of of size , then no edge of connects two vertices in , meaning every pair in is connected in —a -clique.
Illustration on the -vertex graph (): Edges of : , so is a -clique. Complement edges (all missing pairs): . Taking (size ): every edge in touches either or , confirming is a vertex cover of of size .
has a -clique iff has a vertex cover of size . For the -vertex graph with -clique , the complement has vertex cover of size .
Explain why code generation for expression DAGs on registers is -hard while tree code generation is linear-time, and list four pairs of NP-hard problems vs. their simplified polynomial-time counterparts.
Expression Trees vs. DAGs in Code Generation: In an expression tree, every intermediate value has a single parent use, so optimal evaluation order (minimizing register usage) is computed bottom-up in time via Sethi-Ullman labeling. In an expression DAG (caused by common subexpressions), a computed value may have multiple consumers; keeping its register occupied across distant subtrees can cause register spills, making optimal zero-spill ordering -hard.
Four NP-hard vs. simplified polynomial-time pairs:
- 3-SAT () vs. 2-SAT ( via SCCs).
- 3-Colorability () vs. 2-Colorability / Bipartiteness ( via BFS).
- Hamiltonian Cycle () vs. Eulerian Cycle ( via vertex degree parity).
- -Machine Flow Shop (-hard) vs. -Machine Flow Shop ( via Johnson's rule).
Shared subexpressions in DAGs couple evaluation order with register lifetime, making -register code generation -hard (whereas expression trees take ). Key simplified tractable cases include 2-SAT, 2-Coloring, Eulerian Cycle, and 2-Machine Flow Shop.
Distinguish between an -approximation algorithm, a PTAS, an FPTAS, and a probabilistically good algorithm, and prove that the edge-pair approxVertexCover algorithm always achieves an approximation ratio of at most .
Approximation scheme definitions:
- -approximation: Returns within relative error : for a fixed .
- PTAS: Parameterized by , runs in polynomial time in for any fixed (e.g. ).
- FPTAS: Runs in time polynomial in both and (e.g. ).
- Probabilistically good algorithm: A randomized polynomial-time algorithm that meets the target quality guarantee with high probability (e.g. ) on every input.
Proof of -approximation for Vertex Cover: Let be the set of edges selected by approxVertexCover (both endpoints of each are added to ). Since no chosen edge is picked after either endpoint is covered, the edges in are pairwise vertex-disjoint (a matching). Any optimal cover must contain at least one endpoint from each edge in , so . Since , it follows that .
PTAS is polynomial in for fixed , FPTAS is polynomial in both and , and probabilistically good algorithms achieve high-probability guarantees via randomness. approxVertexCover chooses a matching with and , guaranteeing .
- On a cycle graph with vertices and edges , trace
approxVertexCoverwhen edges are inspected in order and compute the ratio . - Execute one trimming step of
APPROX-SUBSET-SUMon the sorted list with , and list the trimmed result.
Tracing approxVertexCover on :
- Edge is uncovered add to ().
- Edge is covered (contains ).
- Edge is uncovered add to ().
- Edge is covered.
Thus . An optimal minimum vertex cover of is of size , so the achieved ratio is .
Trimming with :
- Keep
last = 0. - Check keep , set
last = 50. - Check trim .
- Check keep , set
last = 100. - Check trim .
Trimmed list: .
- On ,
approxVertexCoveroutputs () against , achieving ratio . - Trimming with yields .