Lecture 10:
NP and Computational Intractability II
The University of Sydney
Page 1
8.3 Definition of NP
• Class P
• Class NP
• Class NP-complete
The University of Sydney
Page 2
Definition of the class P
Class P: Decision problems for which there is a deterministic poly-time algorithm.
Problem
Description
Algorithm
Yes
No
MULTIPLE
Is x a multiple of y?
Grade school division
51, 17
51, 16
RELPRIME
Are x and y relatively prime?
Euclid (300 BCE)
34, 39
34, 51
PRIMES
Is x prime?
AKS (2002)
53
51
RNA secondary structure
Is there an RNA secondary structure of weight at most 3?
Dynamic programming
accgguagu
aaaaggggg
MST
Is there a MST of weight at most 5?
Prim’s
The University of Sydney Page 3
Definition of the class NP (Non-Deterministic Polynomial)
Class NP: Decision problems for which YES-instances have a poly-time certifier (aka verifier).
Certification algorithm intuition.
– Certifier views things from “managerial” viewpoint.
– Certifier does not solve the problem by its own; rather, it checks if a proposed proof t is a valid solution.
Definition: Algorithm C(s,t) is a certifier for problem X if for every input instance s and proposed proof t, C(s, t) = `yes’ if and only if t is a valid solution to s.
“certificate” or “witness”
The University of Sydney
Page 4
Certifiers and Certificates: 3-Satisfiability
SAT: Given a CNF formula F, is there a satisfying assignment? Certificate: An assignment of truth values to the n boolean variables. Certifier: Check that each clause in F has at least one true literal.
(x1 Úx2 Úx3)Ù(x1 Úx2 Úx3)Ù(x1 Úx2 Úx4)Ù(x1 Úx3 Úx4) instance s
Conclusion: SAT is in NP. The University of Sydney
Page 5
x1,x2,x4=true, x3=false certificate t
The Main Question: P Versus NP
Is P = NP? [Cook 1971, Edmonds, Levin, Yablonski, Gödel]
– Is the search problem as easy as the certification problem?
– One of the seven Millennium Prize problems: $1 million prize if solved.
EXP
P NP
EXP
P = NP
If P=NP
P 1 NP: No efficient algorithms possible for 3-COLOR, TSP, SAT, … Consensus opinion on P = NP? Probably no.
Intuition: Appreciating good music is vastly easier than making it. Checking the correctness of a given solution is easier than finding a correct solution.
If P1NP
P=NP: Efficient algorithms for 3-COLOR, TSP, FACTOR, SAT, …
would break RSA cryptography
The University of Sydney Page 6
8.4 NP-Completeness
The University of Sydney Page 7
Polynomial Transformation
Definition: Problem X polynomial reduces (Cook) to problem Y if arbitrary instances of problem X can be solved using:
– Polynomial number of standard computational steps, plus
– Polynomial number of calls to oracle that solves problem Y.
Definition: Problem X polynomial transforms (Karp) to problem Y if given any input x to X, we can construct an input y such that x is a yes instance of X iff y is a yes instance of Y.
Note. Polynomial transformation is polynomial reduction with just one call to oracle for Y, exactly at the end of the algorithm for X. Almost all previous reductions were of this form.
Open question. Are these two concepts the same?
we abuse notation £ p and blur distinction
The University of Sydney
Page 8
Class NP-Complete
NP-complete: A problem Y in NP with the property that for every problem X in NP, X£ pY.
Theorem: Suppose Y is an NP-complete problem. Then Y is solvable in poly-time iff P = NP.
Proof:
Ü If P = NP then Y can be solved in poly-time since Y is in NP=P. Þ Suppose Y can be solved in poly-time.
– LetXbeanyprobleminNP. SinceX£p Y,wecansolveXin poly-time. This implies NP Í P.
– WealreadyknowP Í NP.ThusP=NP. ▪
The University of Sydney
Page 9
Circuit Satisfiability
CIRCUIT-SAT. Given a combinational circuit built out of AND, OR, and NOT gates, is there a way to set the circuit inputs so that the output is 1?
output
Ù ¬Ù
ÙÚÚ
CIRCUIT-SAT Î NP
Yes: 101
10??? hard-coded inputs inputs
The University of Sydney
Page 10
The Mother of NP-Complete Problems
Theorem: CIRCUIT-SAT is NP-complete. [Cook 1971, Levin 1973] Proof: (main idea)
– Any algorithm that takes a fixed number of bits n as input and produces a yes/no answer can be represented by such a circuit. Moreover, if algorithm takes poly-time, then circuit is of poly-size.
– Represent certifier as a circuit whose input is proposed certificate
– YES-instances are those for which there exists an input that makes the
circuit output 1.
Proof not part of the course.
The University of Sydney Page 11
Example
Construction below creates a circuit K whose inputs can be set so that K outputs true iff graph G has an independent set of size 2.
Ù independent set of size 2?
independent set? ¬
both endpoints of some edge have been chosen?
Ú Ú
ÙÙÙ
Ú Ú
ÙÙÙ
æ n ö hard-coded inputs (graph description) n inputs (nodes in independent sPeatg)e 12 çè 2 ÷ø
set of size 2?
u
vw
G = (V,E) The University of Sydney
uvw
u-v u-w v-w 101???
Establishing NP-Completeness
Remark: Once we establish first “natural” NP-complete problem, others fall like dominoes.
Recipe to establish NP-completeness of problem Y. – Step1. ShowthatYisinNP.
– Step 2. Choose an NP-complete problem X. – Step 3. Prove that X £ p Y.
Justification: If X is an NP-complete problem, and Y is a problem in NP with the property that X £ P Y then Y is NP-complete.
Proof: LetWbeanyprobleminNP. ThenW £P X £P Y. – Bytransitivity,W£P Y.
– Hence Y is NP-complete. ▪ The University of Sydney
by definition of NP-complete
by assumption
Page 13
3-SAT is NP-Complete
Theorem. 3-SAT is NP-complete.
Proof: Suffices to show that CIRCUIT-SAT £ P 3-SAT since 3-SAT is in NP.
– Let K be any circuit.
– Create a 3-SAT variable xi for each circuit element i.
– Make circuit compute correct values at each node:
•x2=¬x3 Þadd2clauses: x2Úx3 , x2Úx3
• x1 =x4 Úx5 Þ add3clauses: x1Úx4, x1Úx5 , x1Úx4 Ú x5
•x0=x1Ùx2 Þadd3clauses: x0Úx1, x0Úx2,x0Úx1Úx2
– Hard-coded input values and output value. • x5 =0 Þ add1clause: x5
• x0 =1 Þ add1clause: x0
– Final step: turn clauses of length < 3 into clauses of length exactly 3. ▪outputx0 Ù Ú¬ x1x2 x5 x4x3The University of SydneyPage 140?? Using transitivity• 3-SAT is NP-complete• 3-SAT £P INDEPENDENT-SET £P VERTEX-COVER £P SET-COVERCorollary:INDEPENDENT-SET, VERTEX-COVER and SET-COVER are NP-complete.The University of SydneyPage 15Polynomial-Time Reductions constraint satisfaction3-SATDick Karp (1972) 1985 Turing AwardSUBSET-SUMSCHEDULINGINDEPENDENT SETVERTEX COVERSET COVERpacking and coveringDIR-HAM-CYCLEHAM-CYCLETSPsequencingGRAPH 3-COLORPLANAR 3-COLORThe University of SydneyPage 16partitioningnumerical3-SAT reduces to INDEPENDENT SET Extent and Impact of NP-Completeness– Extent of NP-completeness. [Papadimitriou 1995] – Prime intellectual export of CS to other disciplines.– 6,000 citations per year (title, abstract, keywords).• more than “compiler”, “operating system”, “database” – Broad applicability and classification power.The University of SydneyPage 17 More NP-Hard Computational Problems– Aerospace engineering: optimal mesh partitioning for finite elements.– Biology: protein folding.– Chemical engineering: heat exchanger network synthesis.– Civil engineering: equilibrium of urban traffic flow.– Economics: computation of arbitrage in financial markets with friction.– Electrical engineering: VLSI layout.– Environmental engineering: optimal placement of contaminant sensors.– Financial engineering: find minimum risk portfolio of given return.– Game theory: find Nash equilibrium that maximizes social welfare.– Genomics: phylogeny reconstruction.– Mechanical engineering: structure of turbulence in sheared flows.– Medicine: reconstructing 3-D shape from biplane angiocardiogram.– Operations research: optimal resource allocation.– Physics: partition function of 3-D Ising model in statistical mechanics.– Politics: Shapley-Shubik voting power.– Pop culture: Minesweeper consistency.– Statistics: optimal experimental design.The University of SydneyPage 18 NP-complete games and puzzles– Battleship– Candy Crush Saga– Donkey Kong– Eternity II– (Generalized) FreeCell– Lemmings– Minesweeper Consistency Problem– Pokémon– SameGame– (Generalized) Sudoku– (generalized) Tetris– Rush Hour– Hex– (Generalized) Super Mario BrosThe University of SydneyPage 19 Class NP-hardClass NP-complete: A problem in NP such that every problem in NP polynomial reduces to it.Class NP-hard:A decision problem such that every problem in NP reduces to it. not necessarily in NP The University of Sydney Page 21 Many classes?https://complexityzoo.uwaterloo.ca/Complexity_ZooThe University of Sydney Page 22Taxonomy of NP-Complete Problems Six Basic genres§ Constraint satisfaction problems: SAT, 3-SAT.§ Packing problems: SET-PACKING, INDEPENDENT SET. § Covering problems: SET-COVER, VERTEX-COVER.§ Sequencing problems: HAMILTONIAN-CYCLE, TSP.3-SAT £P DIR HAMILTONIAN CYCLE £P HAMILTONIAN CYCLE £P TSP § Partitioning problems: 3D-MATCHING, 3-COLOR.§ Numerical problems: SUBSET-SUM, KNAPSACK. The University of SydneyPage 23Reduction Template for NP-Completeness ProofsAlgorithm for XSpecial Instance of Yf(I)Yes for f(I) No for f(I)Transforms instance of X to instance of YAlgorithm for YInstance of XIYes for I No for IStep 2Step 1Step 1: Construct a polynomial-time algorithm that transforms instance I of X to a special instance f(I) of YStep 2: Prove correctness, which boils down to showingAnswer for I is Yes iff answer for f(I) is Yes(⇒) Transform a YES-certificate for I into a YES-certificate for f(I)(⇐) Transform a YES-certificate for f(I) into a YES-certificate for I The University of SydneyPage 24 Subset-SumGiven a set S of n integers v1, …, vn, and a target value t, is there a subset of S that sum to exactly t?Example: 3, 6, 7, 2, 4, 3, t = 10. Yes Certificate?Certificate = Subset of S that sum to exactly tThe University of Sydney Page 25 Vertex Cover Reduces to Subset SumTheorem: VERTEX-COVER £P SUBSET-SUM.Proof: Given an instance (G, k) of VERTEX-COVER, construct an instance (S, t) of SUBSET-SUM that has a subset of S summing to t iff G has a vertex cover of size at least k. The University of Sydney Page 26 Vertex Cover Reduces to Subset SumProof: Given an instance (G, k) of VERTEX-COVER, construct an instance (S, t) of SUBSET-SUM that has a subset of S summing to t iff G has a vertex cover of size at least k.Number edges from 0 to |E|-1. Set S of integers:– For the i-th edge, add an integer bi– For each vertex v, add an integer avbi = 4iav = 4|E| + X 4ii:i-th edge is incident to v |EX| 1t = k · 4|E| + 2 · 4i The University of Sydney i=0Page 28 Vertex Cover Reduces to Subset SumProof: Given an instance (G, k) of VERTEX-COVER, construct an instance (S, t) of SUBSET-SUM that has a subset of S summing to t iff G has a vertex cover ofsize at least k.Number edges from 0 to |E|-1. Set S of integers:– For the i-th edge, add an integer bi– For each vertex v, add an integer avbi = 4iav = 4|E| + X 4i0 xyz|EX| 1 The University of Sydney i=0t = k · 4|E| +Page 29i:i-th edge is incident to v2 · 4iaz = 1104 ay = 1114ax = 1014 t = 1224k=1b0 = 0014b1 = 01041 Vertex Cover Reduces to Subset SumProof: Given an instance (G, k) of VERTEX-COVER, construct an instance (S, t) of SUBSET-SUM that has a subset of S summing to t iff G has a vertex cover ofsize at least k.Number edges from 0 to |E|-1. Set S of integers:– For the i-th edge, add an integer bi– For each vertex v, add an integer avbi =4iav = 4|E| + X0xyz k=1 2b0 = 00014 b1 = 00104 b2 =01004i:i-th edge is incident to v |EX| 1t=k·4|E| + 2·4i The University of Sydney i=04iax = 11014 ay = 10114 az = 11104t=12224Page 301Vertex Cover Reduces to Subset SumProof: Given an instance (G, k) of VERTEX-COVER, construct an instance (S, t) of SUBSET-SUM that has a subset of S summing to t iff G has a vertex cover ofsize at least k.Number edges from 0 to |E|-1. Set S of integers:– For the i-th edge, add an integer bi– For each vertex v, add an integer avbi =4iav = 4|E| + X0xyz k=2 2b0 = 00014 b1 = 00104 b2 =01004i:i-th edge is incident to v |EX| 1t=k·4|E| + 2·4i The University of Sydney i=04iax = 11014 ay = 10114 az = 11104t=22224Page 311 Vertex Cover Reduces to Subset SumClaim: G has vertex cover of size at most k iff (S, t) has a subset summing to t. Proof: Þ Let C be a vertex cover of size exactly k.– Consider the subset of SX={av :v2C}[{bi :edgeiiscoveredbyexactlyonevertexinC}– The most significant digit is exactly k – The i-th digit is exactly 2.– Therefore sum of X is exactly tbi = 4iav = 4|E| + X 4ii:i-th edge is incident to v |EX| 1t = k · 4|E| + 2 · 4i The University of Sydney i=0Page 32Vertex Cover Reduces to Subset SumClaim: G has vertex cover of size at most k iff (S, t) has a subset summing to t. Proof: Ü Let X be a subset of S summing to t– Then there exists vertex subset V’ and edge subset E’ such that |E| 1X av + X bi = k · 4|E| + X 2 · 4i v2V 0 i2E0 i=0– No carries in the first |E| digits– Each edge number bi contributes at most 1 to the i-th digit of the sum – So, at least one of its endpoints must be in V’– Thus, V’ is a vertex coverbi = 4iav = 4|E| + X 4i i:i-th edge is incident to vThe University of SydneyPage 33Partitioning Problems Six basic genres§ Packing problems: SET-PACKING, INDEPENDENT SET. § Covering problems: SET-COVER, VERTEX-COVER.§ Constraint satisfaction problems: SAT, 3-SAT.§ Sequencing problems: HAMILTONIAN-CYCLE, TSP.3-SAT £P DIR HAMILTONIAN CYCLE £P HAMILTONIAN CYCLE £P TSP § Partitioning problems: 3D-MATCHING, 3-COLOR.§ Numerical problems: SUBSET-SUM, KNAPSACK. The University of SydneyPage 34Graph ColoringGiven an undirected graph G = (V, E), a proper coloring is a coloring of vertices such that every edge has two different colors at its endpoints.Optimization version: Find a proper coloring using as few colors as possible. Example: How many colors? A complete graph on n vertices require at least n colors. (Proof by induction.) The University of SydneyPage 35 Graph ColoringGiven an undirected graph G = (V, E), a proper coloring is a coloring of vertices such that every edge has two different colors at its endpoints.Optimization version: Find a proper coloring using as few colors as possible. Example: How many colors?1 1′ 2 2’3 3’The University of SydneyPage 36 Graph ColoringGiven an undirected graph G = (V, E), a proper coloring is a coloring of vertices such that every edge has two different colors at its endpoints.Optimization version: Find a proper coloring using as few colors as possible. Example: How many colors?1 1′ 2 2’3 3’A graph can be colored with at most 2 colors iff it is bipartite The University of SydneyPage 37 Graph Coloringk-COLOR: Given an undirected graph G = (V, E) with n vertices, does there exist a proper coloring using at most k colors?k-COLOR is in NP:– certificate = k-coloring,– certifying algorithm checks that it is a proper coloring and uses at most k colors1 1′ 2 2’3 3’2-COLOR is equivalent to testing for bipartiteness and so is in P. 1-COLOR and n-COLOR is also in P (why?)The University of SydneyPage 38 3-SAT Reduces to 3-COLOR3-COLOR: Given an undirected graph G = (V, E), does there exist a proper coloring using at most 3 colors?Theorem: 3-SAT £P 3-COLOR.The University of Sydney Page 39 3-SAT Reduces to 3-COLORTheorem: 3-SAT £P 3-COLOR.Proof: Given an arbitrary instance F of 3-SAT, we construct an instance G of 3-COLOR that has a 3-coloring iff F is satisfiable. Construction of G:1. Truth gadget. Introduce 3 special vertices called T, F and O connected to each other. Call their colors T, F and O.2. Variable gadget. Introduce 2 literal vertices per variable and connect them to each other and O. Literals with same color as T is assigned true, those with same color as F is assigned false. Thus, 3-coloring = consistent truth assignment (every variable is either true or false).OTF The University of Sydneyx1 x1Page 40 3-SAT Reduces to 3-COLORConstruction of G:3.– –Clause gadget.For each clause, add 5 new vertices, connecting them and the corresponding variable vertices with T in the following manner.Suppose both left and middle variable vertices colored with F.T (x1 Úx2 Úx3)Ù(x1 Úx2 Úx3)Ù(x1 Úx2 Úx4)Ù(x1 Úx3 Úx4)The University of Sydney x1 x2 x3 Page 413-SAT Reduces to 3-COLORConstruction of G:3.– –Clause gadget.For each clause, add 5 new vertices, connecting them and the corresponding variable vertices with T in the following manner.Suppose both left and middle variable vertices colored with F. Then, the highlighted vertices must have the following colors.T(x1 Úx2 Úx3)Ù(x1 Úx2 Úx3)Ù(x1 Úx2 Úx4)Ù(x1 Úx3 Úx4) TOFFThe University of Sydney x1 x2 x3 Page 423-SAT Reduces to 3-COLORConstruction of G:3.– –Clause gadget.For each clause, add 5 new vertices, connecting them and the corresponding variable vertices with T in the following manner.Suppose both left and middle variable vertices colored with F. Then, the highlighted vertices must have the following colors.T(x1 Úx2 Úx3)Ù(x1 Úx2 Úx3)Ù(x1 Úx2 Úx4)Ù(x1 Úx3 Úx4) FTOFF The University of Sydney x1 x2 x3 Page 433-SAT Reduces to 3-COLORConstruction of G:3.– –Clause gadget.For each clause, add 5 new vertices, connecting them and the corresponding variable vertices with T in the following manner.Suppose both left and middle variable vertices colored with F. Then, the highlighted vertices must have the following colors.TOF(x1 Úx2 Úx3)Ù(x1 Úx2 Úx3)Ù(x1 Úx2 Úx4)Ù(x1 Úx3 Úx4) FTOFFThe University of Sydney x1 x2 x3 Page 443-SAT Reduces to 3-COLORConstruction of G:3.– –Clause gadget.For each clause, add 5 new vertices, connecting them and the corresponding variable vertices with T in the following manner.Suppose both left and middle variable vertices colored with F. Then, the highlighted vertices must have the following colors. In particular, the rightvariable vertex must be colored T.TOF (x1 Úx2 Úx3)Ù(x1 Úx2 Úx3)Ù(x1 Úx2 Úx4)Ù(x1 Úx3 Úx4) F TOFFTThe University of Sydney x1 x2 x3 Page 453-SAT Reduces to 3-COLORClaim: For each clause gadget, a coloring of variable vertices using T and F colors can be extended to a proper 3-coloring of the entire gadget iff at least one variable vertex is colored T. Proof:Þ Done in previous slide.Ü Check all 7 such colorings by hand.TOF(x1 Úx2 Úx3)Ù(x1 Úx2 Úx3)Ù(x1 Úx2 Úx4)Ù(x1 Úx3 Úx4) F TOFFTThe University of Sydney x1 x2 x3 Page 463-SAT Reduces to 3-COLORClaim: G has a 3-coloring iff F is satisfiable.Proof: Þ Suppose G has a 3-coloring.– Assign literals with same color as vertex T true, rest is false.– We have argued previously that assignment is consistent and claim implies every clause has at least one true literal.Ü Suppose F has a satisfying assignment.– Color literal vertices and truth gadget accordingly.– Claim implies: For each clause gadget, can extend to a proper 3- coloring if at least one literal vertex is set to true.Truth GadgetThe University of SydneyClause GadgetPage 47Variable Gadget8.5 Sequencing Problems Six Basic genres§ Packing problems: SET-PACKING, INDEPENDENT SET. § Covering problems: SET-COVER, VERTEX-COVER.§ Constraint satisfaction problems: SAT, 3-SAT.§ Sequencing problems: HAMILTONIAN-CYCLE, TSP.3-SAT £P DIR HAMILTONIAN CYCLE £P HAMILTONIAN CYCLE £P TSP § Partitioning problems: 3D-MATCHING, 3-COLOR.§ Numerical problems: SUBSET-SUM, KNAPSACK. The University of SydneyPage 48Hamiltonian CycleHAM-CYCLE: given an undirected graph G = (V, E), does there exist a simple cycle G that contains every node in V. The University of Sydney Vertices and faces of a dodecahedron: Yes Page 49 Hamiltonian CycleHAM-CYCLE: given an undirected graph G = (V, E), does there exist a simple cycle G that contains every node in V.The University of Sydney1 1’2 2’3 3’4 4’5Bipartite graph with odd number of nodes: NoPage 50 Directed Hamiltonian CycleDIR-HAM-CYCLE: Given a directed graph G = (V, E), does there exist a simple directed cycle G that contains every node in V?Theorem: DIR-HAM-CYCLE £ P HAM-CYCLE.Proof idea: Given a directed graph G = (V, E), construct an undirected graphG’ with 3n vertices.abv cG aout ddineinebout coutvin v voutG’ The University of SydneyPage 51 Directed Hamiltonian CycleClaim: G has a Hamiltonian cycle iff G’ does.Proof:Þ –– Then G’ has an undirected Hamiltonian cycle (same order).Suppose G has a directed Hamiltonian cycle G.Ü –– G’ must visit nodes in G’ using one of two orders:Suppose G’ has an undirected Hamiltonian cycle G’…., B, G, R, B, G, R, B, G, R, B, ……, B, R, G, B, R, G, B, R, G, B, …– Blue nodes in G’ make up directed Hamiltonian cycle G in G, or reverseof one. ▪ aoutbout vin coutdineind dout v vout G’The University of SydneyPage 52 3-SAT Reduces to Directed Hamiltonian CycleTheorem: 3-SAT £ P DIR-HAM-CYCLE.Proof: Given an instance F of 3-SAT, we construct an instance of DIR-HAM-CYCLE that has a Hamiltonian cycle iff F is satisfiable.Construction. First, create graph that has 2n Hamiltonian cycles whichcorrespond in a natural way to 2n possible truth assignments.The University of SydneyPage 53 3-SAT Reduces to Directed Hamiltonian CycleConstruction: Given a 3-SAT instance F with n variables xi and k clauses. – Construct G to have 2n Hamiltonian cycles.– Intuition: Traverse path i from left to right Û set variable xi = 1.s x2x3 The University of SydneyPage 543k + 3tx13-SAT Reduces to Directed Hamiltonian Cycle– Construction. Given 3-SAT instance F with n variables xi and k clauses. – For each clause: add a node and 6 edges.C1 =x1 Vx2 Vx3clause nodeclause node sThe University of SydneyPage 55tC2 =x1 Vx2 Vx3 x1x2x3 3-SAT Reduces to Directed Hamiltonian Cycle– Construction. Given 3-SAT instance F with n variables xi and k clauses. – For each clause: add a node and 6 edges. C1 =x1 Vx2 Vx3clause nodeclause nodesThe University of SydneyPage 56tC2 =x1 Vx2 Vx3x1x2 x3 3-SAT Reduces to Directed Hamiltonian Cycle– Construction. Given 3-SAT instance F with n variables xi and k clauses. – For each clause: add a node and 6 edges. C1 =x1 Vx2 Vx3clause nodeclause nodesThe University of SydneyPage 57tC2 =x1 Vx2 Vx3x1x2 x3 3-SAT Reduces to Directed Hamiltonian CycleClaim: F is satisfiable iff G has a Hamiltonian cycle.Proof: Þ– Suppose 3-SAT instance has satisfying assignment x*. – Then, define Hamiltonian cycle in G as follows:• if x*i = 1, traverse row i from left to right• if x*i = 0, traverse row i from right to left• for each clause Cj , there will be at least one row i in which we are going in “correct” direction to splice node Cj into tours x1 x2 The University of Sydney t Page 58×33-SAT Reduces to Directed Hamiltonian CycleClaim: F is satisfiable iff G has a Hamiltonian cycle.Proof: Ü– Suppose G has a Hamiltonian cycle G.– If G enters clause node Cj , it must depart on mate edge.• thus, nodes immediately before and after Cj are connected by an edge e in G• removing Cj from cycle, and replacing it with edge e yields HamiltoniancycleonG{Cj }– Continuing in this way, we are left with Hamiltonian cycle G’ in G-{C1,C2, …,Ck}.– Set x*i = 1 iff G’ traverses row i left to right.– Since G visits each clause node Cj , at least one of the paths is traversedin “correct” direction, and each clause is satisfied. ▪ The University of SydneyPage 59 Longest PathSHORTEST-PATH: Given a digraph G = (V, E), does there exists a simple path of length at most k edges?LONGEST-PATH: Given a digraph G = (V, E), does there exists a simple path of length at least k edges?Theorem: 3-SAT £ P LONGEST-PATH.Proof: Redo the proof for DIR-HAM-CYCLE, ignoring back-edge from t to s. Corollary: Deciding who wins in Catan and Ticket to Ride is NP-hard.The University of Sydney Page 60 Travelling Salesperson ProblemTSP: Given a set of n cities and a pairwise distance function d(u, v), is there a tour of length £ D?All 13,509 cities in US with a population of at least 500 Reference: http://www.tsp.gatech.edu The University of SydneyPage 61 Travelling Salesperson ProblemTSP: Given a set of n cities and a pairwise distance function d(u, v), is there a tour of length £ D?Optimal TSP tourReference: http://www.tsp.gatech.edu The University of SydneyPage 62 Travelling Salesperson ProblemTSP: Given a set of n cities and a pairwise distance function d(u, v), is there a tour of length £ D?11,849 holes to drill in a programmed logic array Reference: http://www.tsp.gatech.edu The University of SydneyPage 63 Travelling Salesperson ProblemTSP: Given a set of n cities and a pairwise distance function d(u, v), is there a tour of length £ D?Optimal TSP tourReference: http://www.tsp.gatech.edu The University of SydneyPage 64 Travelling Salesperson ProblemTSP: Given a set of n cities and a pairwise distance function d(u, v), is there a tour of length £ D?HAM-CYCLE: given a graph G = (V, E), does there exists a simple cycle that contains every node in V?Theorem: HAM-CYCLE £ P TSP. Proof:– Given instance G = (V, E) of HAM-CYCLE, create n cities with distancefunction– TSP instance has tour of length £ n iff G is Hamiltonian. ▪d(u,v)=ìí1 if(u,v)ÎE î2 if(u,v)ÏEThe University of Sydney Page 65 Establishing NP-CompletenessRemark: Once we establish first “natural” NP-complete problem, others fall like dominoes.Recipe to establish NP-completeness of problem Y. – Step1. ShowthatYisinNP.– Step 2. Choose an NP-complete problem X. – Step 3. Prove that X £ p Y.Justification: If X is an NP-complete problem, and Y is a problem in NP with the property that X £ P Y then Y is NP-complete.Proof: LetWbeanyprobleminNP. ThenW £P X £P Y. – Bytransitivity,W£P Y.– Hence Y is NP-complete. ▪ The University of Sydneyby definition of NP-completeby assumptionPage 66 Reduction Template for NP-Completeness ProofsAlgorithm for XSpecial Instance of Yf(I)Yes for f(I) No for f(I)Transforms instance of X to instance of YAlgorithm for YInstance of XIYes for I No for IStep 2Step 1Step 1: Construct a polynomial-time algorithm that transforms instance I of X to a special instance f(I) of YStep 2: Prove correctness, which boils down to showingAnswer for I is Yes iff answer for f(I) is Yes(⇒) Transform a YES-certificate for I into a YES-certificate for f(I)(⇐) Transform a YES-certificate for f(I) into a YES-certificate for I The University of SydneyPage 67 The University of Sydney Page 68Taxonomy of NP-Complete Problems Six Basic genres§ Constraint satisfaction problems: SAT, 3-SAT.§ Packing problems: SET-PACKING, INDEPENDENT SET. § Covering problems: SET-COVER, VERTEX-COVER.§ Sequencing problems: HAMILTONIAN-CYCLE, TSP.3-SAT £P DIR HAMILTONIAN CYCLE £P HAMILTONIAN CYCLE £P TSP § Partitioning problems: 3D-MATCHING, 3-COLOR.§ Numerical problems: SUBSET-SUM, KNAPSACK. The University of SydneyPage 69
Reviews
There are no reviews yet.