NP-Complete
Watch on YouTube →
Overview
Kent Quanrud connects graph-coloring reductions to the central complexity-theory result that every problem with a polynomial-time-verifiable certificate can be encoded as a polynomial-size circuit, then reduced to 3-SAT. The chain of reductions explains why problems such as 3-coloring, independent set, Hamiltonian path, and subset sum are NP-complete, while the distinction between polynomial-time computation and verification remains the open P versus NP question.
Key takeaways
- A polynomial-time algorithm can be unrolled into a polynomial-size circuit by assigning each time step a fresh copy of memory, avoiding the cycles created by overwriting locations.
- Any problem with polynomial-time-verifiable certificates can be reduced to circuit SAT, and circuit SAT can be transformed into 3-SAT, making 3-SAT a universal target for NP problems.
- List 3-coloring can encode 3-SAT: a palette triangle establishes three color identities, variable edges encode truth choices, and clause gadgets enforce that at least one literal is true.
- NP-complete means both efficiently verifiable and at least as hard as every problem in NP; a polynomial-time algorithm for any one NP-complete problem would solve all NP problems in polynomial time.
- Richard Karp’s 1972 reductions linked classic problems including satisfiability, clique, Hamiltonian path, and graph coloring, revealing that their polynomial-time solvability rises or falls together.
- P versus NP remains unresolved largely because proving that no polynomial-time algorithm exists requires strong lower bounds, which are harder to establish than the correctness of a proposed algorithm.
Chapters
- Boolean satisfiability, subset sum, Hamiltonian path, and general-graph independent set have all been shown hard through reductions.
- Special structure can make graph problems tractable: interval independent set uses left-to-right dynamic programming, while tree problems use rooted subtrees.
- The lecture introduces graph coloring as another problem to connect to 3-SAT.
- A proper coloring assigns colors to graph vertices so adjacent vertices receive different colors.
- For the illustrated graph, a four-vertex clique proves that at least four colors are necessary.
- The decision version asks whether a graph can be colored with a specified number of colors, such as three.
- In list coloring, each vertex receives a list of permitted colors; vertices without a list may use any of the three colors.
- A triangle forces its three vertices to take distinct colors, creating a palette that represents the color identities consistently.
- Edges from a constrained vertex to palette vertices exclude colors, translating list restrictions into an ordinary 3-coloring instance.
- Variable vertices represent true and false choices, with an edge forcing complementary values to receive different colors.
- Clause gadgets use restricted color lists and edges to encode an OR condition: a clause can be colored when at least one literal is true.
- Combining the variable and clause gadgets reduces 3-SAT to list 3-coloring; the palette construction then reduces list coloring to ordinary 3-coloring.
- A circuit is a directed acyclic graph, while a program can repeatedly overwrite the same memory location over time.
- Quanrud models a computer as memory plus a CPU applying logical operations to a finite number of inputs at each step.
- The key obstacle to viewing a program as a circuit is its reuse of memory, which creates apparent cycles in the computation.
- The construction makes a fresh copy of memory at each time step, carrying forward unchanged values and writing updates into the new copy.
- This time-layered representation resembles Bellman-Ford, where adding a step parameter handles computation across successive layers.
- For a polynomial-time algorithm, the number of time steps and the memory needed at each step are polynomially bounded, so the resulting circuit has polynomial size.
- SAT assignments, Hamiltonian paths, independent sets, and subset-sum solutions can each be checked efficiently once supplied.
- The Good Will Hunting story illustrates the distinction between finding a solution and checking a proposed certificate.
- A polynomial-time checker can be represented as a polynomial-size circuit by the program-to-circuit construction.
- A verifier circuit takes the original instance and a proposed certificate, accepting exactly when the certificate proves a yes-instance.
- Circuit SAT can therefore determine whether any polynomial-time-verifiable problem has a valid certificate.
- Because circuit SAT reduces to 3-SAT, and the lecture develops further reductions to problems such as independent set and Hamiltonian path, the reductions form a chain among these problems.
- NP means nondeterministic polynomial time, not 'not polynomial time.'
- The nondeterministic-computer model branches on choices and accepts if any branch succeeds, allowing it to guess a certificate and verify it.
- A polynomial-time verifier and a polynomial-size certificate characterize the same class of problems as this nondeterministic model.
- A problem is NP-hard if every problem in NP can be reduced to it; it need not itself have efficiently verifiable solutions.
- An NP-complete problem is both in NP and NP-hard, so a polynomial-time algorithm for one would solve every problem in NP in polynomial time.
- P versus NP asks whether every problem with a polynomial-time-verifiable certificate also has a polynomial-time solution algorithm.
- Richard Karp’s 1972 paper, 'Reducibility Among Combinatorial Problems,' connected many problems involving graphs, integers, and arrays.
- The paper framed polynomial-time solvability as the relevant standard and showed that a polynomial-time algorithm for one problem in the reduction network yields algorithms for others.
- Its examples include satisfiability, clique, Hamiltonian path, and graph coloring, building on foundational work by Stephen Cook and Leonid Levin.
- Quanrud identifies two recurring techniques: decompose a problem into subproblems using recursion or dynamic programming, and transform one input into another problem’s input.
- The time-layered circuit construction applies the first style, echoing Bellman-Ford’s layered dynamic programming.
- Reductions from 3-SAT to independent set, Hamiltonian path, and coloring apply the second style.
- Showing that an algorithm works can be done by presenting and checking it; proving that no polynomial-time algorithm exists requires a lower bound.
- The lecture notes that lower bounds are difficult and that many proposed approaches to P versus NP have failed.
- The question remains open despite extensive research and significant computational resources.
- Cantor’s diagonal argument assumes a list of real numbers, flips the diagonal bits, and constructs a number that differs from every listed row.
- Turing formalized computation with a machine that reads and writes memory, making it possible to represent programs as strings and ask whether they halt.
- Diagonalization proves that no algorithm can decide the halting question for every program and input.
- Turing’s machine model and the idea of a universal programmable computer supplied new language for studying computability.
- The lecture connects major advances to reframing problems, rather than only applying familiar tools to them.
- The final takeaway is that difficult questions such as P versus NP may require ideas that change how computation itself is understood.
Transcript excerpt
0:03 Okay. All right. So, today's lecture is called polinomial times a flat circle, but it's going to it's going to bring together like kind of a lot of stuff we've been discussing. So, this one's kind of nice. So, what have we been discussing? Ah, same usual warm-up. We started with these kind of boolean formulas. They seem like a perfect fit for computers, but we don't know how to solve them, right? Computer can easily evaluate a boolean formula, but it can't solve a boolean formula. We don't really know why even when we pass to to simpler questions uh like CNFSAT or threes uh we don't seem to be able to solve those either. Um we can um however show that if you can solve three set or some other special case you can solve boolean sat and that's a different kind of result than
0:50 we're typically used to. uh two sat you know was just like this on steroids down to two variables. If it's two setat and you're solving exactly, it actually just turns out to be some kind of clever reachability problem. But if it's max two setat, then we don't have an algorithm. Again, if you can solve max two setat, you can solve boolean formulas. We also did subset sum. Even adding up numbers to a target is as strong as solving a boolean formula. We did longest path in a graph like Hamiltonian path. That also turns out to be hard. Although in a dab you can do anything as you may be finding out in your homework. And last time we did independent set. So you have a bunch bunch of vertices in a graph. You want to take as many as possible. That turns out hard to be to do in a general graph. But if we look at
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
Related notes
Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Kent Quanrud.