CS代考程序代写 compiler database algorithm Lecture 10:

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 Úx2 Úx3)Ù(x1 Úx2 Úx3)Ù(x1 Úx2 Úx4)Ù(x1 Úx3 Ú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, Gö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:
Ü 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 Í P.
– WealreadyknowP Í 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
Ù ¬Ù
ÙÚÚ
CIRCUIT-SAT Î 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.
Ù independent set of size 2?
independent set? ¬
both endpoints of some edge have been chosen?
Ú Ú
ÙÙÙ
Ú Ú
ÙÙÙ
æ n ö hard-coded inputs (graph description) n inputs (nodes in independent sPeatg)e 12 çè 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: x2Úx3 , x2Úx3
• x1 =x4 Úx5 Þ add3clauses: x1Úx4, x1Úx5 , x1Úx4 Ú x5
•x0=x1Ùx2 Þadd3clauses: x0Úx1, x0Úx2,x0Úx1Ú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. ▪ output x0 Ù Ú¬ x1 x2 x5 x4 x3 The University of Sydney Page 14 0?? Using transitivity • 3-SAT is NP-complete • 3-SAT £P INDEPENDENT-SET £P VERTEX-COVER £P SET-COVER Corollary: INDEPENDENT-SET, VERTEX-COVER and SET-COVER are NP-complete. The University of Sydney Page 15 Polynomial-Time Reductions constraint satisfaction 3-SAT Dick Karp (1972) 1985 Turing Award SUBSET-SUM SCHEDULING INDEPENDENT SET VERTEX COVER SET COVER packing and covering DIR-HAM-CYCLE HAM-CYCLE TSP sequencing GRAPH 3-COLOR PLANAR 3-COLOR The University of Sydney Page 16 partitioning numerical 3-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 Sydney Page 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 Sydney Page 18 NP-complete games and puzzles – Battleship – Candy Crush Saga – Donkey Kong – Eternity II – (Generalized) FreeCell – Lemmings – Minesweeper Consistency Problem – Pokémon – SameGame – (Generalized) Sudoku – (generalized) Tetris – Rush Hour – Hex – (Generalized) Super Mario Bros The University of Sydney Page 19 Class NP-hard Class 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_Zoo The University of Sydney Page 22 Taxonomy 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 Sydney Page 23 Reduction Template for NP-Completeness Proofs Algorithm for X Special Instance of Y f(I) Yes for f(I) No for f(I) Transforms instance of X to instance of Y Algorithm for Y Instance of X I Yes for I No for I Step 2 Step 1 Step 1: Construct a polynomial-time algorithm that transforms instance I of X to a special instance f(I) of Y Step 2: Prove correctness, which boils down to showing Answer 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 Sydney Page 24 Subset-Sum Given 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 t The University of Sydney Page 25 Vertex Cover Reduces to Subset Sum Theorem: 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 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. 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 av bi = 4i av = 4|E| + X 4i i:i-th edge is incident to v |EX|1 t = k · 4|E| + 2 · 4i The University of Sydney i=0 Page 28 Vertex Cover Reduces to 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. 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 av bi = 4i av = 4|E| + X 4i 0 xyz |EX|1 The University of Sydney i=0 t = k · 4|E| + Page 29 i:i-th edge is incident to v 2 · 4i az = 1104 ay = 1114 ax = 1014 t = 1224 k=1 b0 = 0014 b1 = 0104 1 Vertex Cover Reduces to 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. 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 av bi =4i av = 4|E| + X 0 xyz k=1 2 b0 = 00014 b1 = 00104 b2 =01004 i:i-th edge is incident to v |EX|1 t=k·4|E| + 2·4i The University of Sydney i=0 4i ax = 11014 ay = 10114 az = 11104 t=12224 Page 30 1 Vertex Cover Reduces to 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. 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 av bi =4i av = 4|E| + X 0 xyz k=2 2 b0 = 00014 b1 = 00104 b2 =01004 i:i-th edge is incident to v |EX|1 t=k·4|E| + 2·4i The University of Sydney i=0 4i ax = 11014 ay = 10114 az = 11104 t=22224 Page 31 1 Vertex Cover Reduces to Subset Sum Claim: 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 S X={av :v2C}[{bi :edgeiiscoveredbyexactlyonevertexinC} – The most significant digit is exactly k – The i-th digit is exactly 2. – Therefore sum of X is exactly t bi = 4i av = 4|E| + X 4i i:i-th edge is incident to v |EX|1 t = k · 4|E| + 2 · 4i The University of Sydney i=0 Page 32 Vertex Cover Reduces to Subset Sum Claim: G has vertex cover of size at most k iff (S, t) has a subset summing to t. Proof: Ü Let X be a subset of S summing to t – Then there exists vertex subset V’ and edge subset E’ such that |E|1 X 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 cover bi = 4i av = 4|E| + X 4i i:i-th edge is incident to v The University of Sydney Page 33 Partitioning 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 Sydney Page 34 Graph Coloring Given 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 Sydney Page 35 Graph Coloring Given 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 Sydney Page 36 Graph Coloring Given 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 Sydney Page 37 Graph Coloring k-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 colors 1 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 Sydney Page 38 3-SAT Reduces to 3-COLOR 3-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-COLOR Theorem: 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). O TF The University of Sydney x1 x1 Page 40 3-SAT Reduces to 3-COLOR Construction 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 Úx2 Úx3)Ù(x1 Úx2 Úx3)Ù(x1 Úx2 Úx4)Ù(x1 Úx3 Úx4) The University of Sydney x1 x2 x3 Page 41 3-SAT Reduces to 3-COLOR Construction 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 Úx2 Úx3)Ù(x1 Úx2 Úx3)Ù(x1 Úx2 Úx4)Ù(x1 Úx3 Úx4) TO FF The University of Sydney x1 x2 x3 Page 42 3-SAT Reduces to 3-COLOR Construction 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 Úx2 Úx3)Ù(x1 Úx2 Úx3)Ù(x1 Úx2 Úx4)Ù(x1 Úx3 Úx4) F TO FF The University of Sydney x1 x2 x3 Page 43 3-SAT Reduces to 3-COLOR Construction 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 OF (x1 Úx2 Úx3)Ù(x1 Úx2 Úx3)Ù(x1 Úx2 Úx4)Ù(x1 Úx3 Úx4) F TO FF The University of Sydney x1 x2 x3 Page 44 3-SAT Reduces to 3-COLOR Construction 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 right variable vertex must be colored T. T OF (x1 Úx2 Úx3)Ù(x1 Úx2 Úx3)Ù(x1 Úx2 Úx4)Ù(x1 Úx3 Úx4) F TO FF T The University of Sydney x1 x2 x3 Page 45 3-SAT Reduces to 3-COLOR Claim: 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. Ü Check all 7 such colorings by hand. T OF (x1 Úx2 Úx3)Ù(x1 Úx2 Úx3)Ù(x1 Úx2 Úx4)Ù(x1 Úx3 Úx4) F TO FF T The University of Sydney x1 x2 x3 Page 46 3-SAT Reduces to 3-COLOR Claim: 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. Ü 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 Gadget The University of Sydney Clause Gadget Page 47 Variable Gadget 8.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 Sydney Page 48 Hamiltonian Cycle HAM-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 Cycle HAM-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 1 1' 2 2' 3 3' 4 4' 5 Bipartite graph with odd number of nodes: No Page 50 Directed Hamiltonian Cycle DIR-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 graph G' with 3n vertices. a bv c G aout d din ein e bout cout vin v vout G' The University of Sydney Page 51 Directed Hamiltonian Cycle Claim: 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. Ü – – 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 reverse of one. ▪ aout bout vin cout din ein d dout v vout G' The University of Sydney Page 52 3-SAT Reduces to Directed Hamiltonian Cycle Theorem: 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 which correspond in a natural way to 2n possible truth assignments. The University of Sydney Page 53 3-SAT Reduces to Directed Hamiltonian Cycle Construction: 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 Û set variable xi = 1. s x2 x3 The University of Sydney Page 54 3k + 3 t x1 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 Vx3 clause node clause node s The University of Sydney Page 55 t C2 =x1 Vx2 Vx3 x1 x2 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 Vx3 clause node clause node s The University of Sydney Page 56 t C2 =x1 Vx2 Vx3 x1 x2 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 Vx3 clause node clause node s The University of Sydney Page 57 t C2 =x1 Vx2 Vx3 x1 x2 x3 3-SAT Reduces to Directed Hamiltonian Cycle Claim: 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 tour s x1 x2 The University of Sydney t Page 58 x3 3-SAT Reduces to Directed Hamiltonian Cycle Claim: F is satisfiable iff G has a Hamiltonian cycle. Proof: Ü – 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 traversed in "correct" direction, and each clause is satisfied. ▪ The University of Sydney Page 59 Longest Path SHORTEST-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 Problem TSP: 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 Sydney Page 61 Travelling Salesperson Problem TSP: Given a set of n cities and a pairwise distance function d(u, v), is there a tour of length £ D? Optimal TSP tour Reference: http://www.tsp.gatech.edu The University of Sydney Page 62 Travelling Salesperson Problem TSP: 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 Sydney Page 63 Travelling Salesperson Problem TSP: Given a set of n cities and a pairwise distance function d(u, v), is there a tour of length £ D? Optimal TSP tour Reference: http://www.tsp.gatech.edu The University of Sydney Page 64 Travelling Salesperson Problem TSP: 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 distance function – TSP instance has tour of length £ n iff G is Hamiltonian. ▪ d(u,v)=ìí1 if(u,v)ÎE î2 if(u,v)ÏE The University of Sydney Page 65 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 66 Reduction Template for NP-Completeness Proofs Algorithm for X Special Instance of Y f(I) Yes for f(I) No for f(I) Transforms instance of X to instance of Y Algorithm for Y Instance of X I Yes for I No for I Step 2 Step 1 Step 1: Construct a polynomial-time algorithm that transforms instance I of X to a special instance f(I) of Y Step 2: Prove correctness, which boils down to showing Answer 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 Sydney Page 67 The University of Sydney Page 68 Taxonomy 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 Sydney Page 69

Related Posts