COMPSCI320 Chap.13 NP-Completeness and Polynomial-Time Reductions
NP-Completeness and Polynomial-Time Reductions
The last module asks what to do when no efficient algorithm is likely.
This chapter defines polynomial-time reductions and their direction, separates P, NP, NP-hard and NP-complete with certificates and certifiers, proves clique NP-complete from independent set, builds the 3-SAT to independent set gadget, and surveys the colouring, subset-sum and knapsack reductions from the lecture.
The worked proof gives a certificate, a certifier and a reduction with both directions, the structure the NP activity asks for.
A figure draws the clause triangles for a three-clause formula, and the practice cards apply the vertex cover to set cover reduction and test reasoning about the direction of reductions.
What this chapter covers
- 01
Polynomial-time reductions and their direction
- 02
Certificates and certifiers
- 03
P, NP, NP-hard and NP-complete
- 04
Independent set, vertex cover and clique
- 05
The 3-SAT to independent set gadget
- 06
Colouring, subset sum and knapsack reductions
Worked example · free
Build the clause triangles for three clauses
- 1Make a triangle of three literal vertices for each clause.
- 1Join every literal to each occurrence of its negation in another clause, and set k = 3.
- 1The assignment x1, x2 and x3 all true satisfies every clause.
- 1Choose x1, x2 and x1 from the three triangles; no edge joins them, so the set has size 3.
Key terms
- Polynomial-Time Reduction
- A method of solving one problem with polynomially many steps and calls to a solver for another problem.
- Certifier
- A polynomial-time algorithm that checks a proposed certificate for a yes answer.
- NP-Complete Problem
- A problem that belongs to NP and to which every problem in NP reduces in polynomial time.
- Vertex Cover
- A set of vertices that touches every edge of a graph.
- Reduction Gadget
- A small constructed piece of an instance that forces one variable, clause or choice to behave as required.
- 3-SAT
- The satisfiability problem for formulas whose clauses each contain exactly three literals.
NP-Completeness and Polynomial-Time Reductions FAQ
Which way should a hardness reduction go?
From the known hard problem to the new one. To show a new problem Y is hard, take an arbitrary instance of a known NP-complete problem X and build an instance of Y with the same answer, proving X ≤p Y. Reducing Y to X only shows Y is no harder than X, which says nothing about its difficulty.
Why must a reduction be proved in both directions?
The constructed instance must have exactly the same answer as the original. Showing only that yes for X gives yes for Y would allow a construction that always outputs a yes instance, which proves nothing. The second direction, that a yes for Y yields a yes for X, is what makes the answers equivalent.
Does an O(nW) algorithm for subset sum mean P equals NP?
No. The target W is written in binary, so the input contains only about log W bits for it, and a running time that grows with the value of W can be exponential in the input length. Such an algorithm is called pseudo-polynomial, and subset sum remains NP-complete.
What is the difference between NP-hard and NP-complete?
A problem is NP-hard when every problem in NP reduces to it in polynomial time; it need not be in NP itself and need not be a decision problem. A problem is NP-complete when it is NP-hard and also belongs to NP, so its yes answers have short certificates that can be checked in polynomial time.
Exam move
Write the two-part template for an NP-completeness proof from memory, then apply it to clique and to one problem of your own choice. Redraw the 3-SAT gadget for a new formula and check both directions on it. Finally list the lecture's reduction tree with one sentence describing each arrow. In the final week, practise one full reduction under time pressure, writing the five labelled parts in order without notes.
Practise saying in one sentence why each gadget forces the property it is designed to force.
Working through NP-Completeness and Polynomial-Time Reductions in COMPSCI320? Sia is AskSia’s AI Computer Science tutor — ask any COMPSCI320 NP-Completeness and Polynomial-Time Reductions question and get a clear, step-by-step explanation grounded in how COMPSCI320 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
