EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 9 1 Polynomial Time Reducibility
Definition 1.1. A function f : Σ∗ → Σ∗ is polynomial time computable if there exists a polynomial- time program M that, on any input w, prints f(w) and halts.
Definition 1.2. Language A is polynomial time mapping reducible to language B, written A ≤p B, if there exists a polynomial time computable function f : Σ∗ → Σ∗ such that for every w,
Copyright By PowCoder代写 加微信 powcoder
w∈A ⇐⇒ f(w)∈B.
The function f is called a polynomial time reduction from A to B.
Theorem 1.3. If A ≤p B and B ∈ P, then A ∈ P.
Proof. Let M be the polynomial time algorithm that decides B and f be a polynomial time reduc- tion from A to B. We describe a polynomial time algorithm N that decides A as follows:
N = “On input w:
1. Compute f(w).
2. Run M on input f(w) and output whatever M outputs.”
We will show that N decides A and runs in polynomial time.
w∈A =⇒ f(w)∈B =⇒ M acceptsf(w) =⇒ N acceptsw.
w∈/A =⇒ f(w)∈/B =⇒ M rejectsf(w) =⇒ N rejectsw.
Furthermore, N runs in polynomial time because each of its two steps runs in polynomial
time. Step 1 runs in time O(|w|k) for some constant k, by definition of f being polynomial time computable. The result f(w) has size |f(w)| = O(|w|k), since we can’t construct an object of larger size in time O(|w|k). Step 2 runs in time polynomial with respect to |f(w)| by the definition of M, so it takes time O(|f(w)|m) = O(|w|km) for some constant m. Since km is a constant, N decides A in polynomial time, which means that A ∈ P.
EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 9 2 NP-Completeness
Definition 2.1. A language is NP-Hard if every language in NP can be mapping reduced to it in polynomial time. In other words, L is NP-Hard if A ≤p L for all A ∈ NP.
Intuitively, every NP-Hard language is at least as hard as every language in NP. If, in addition to being NP-Hard, a language is contained in NP, then it is NP-Complete.
Definition 2.2. A language L is NP-Complete if: 1. L∈NP.
2. L is NP-Hard.
The difficulty of solving an NP-Complete problem is related to the difficulty of solving arbitrary
problems in NP:
Claim 2.3. Suppose L is NP-Complete language. Then:
L ∈ P ⇒ P = NP.
Proof. We already know that P ⊆ NP. It remains to show that, if L ∈ P, then NP ⊆ P. So let A ∈ NP. By the definition of NP-Completeness, A ≤p L. Since we have assumed that L ∈ P, we can use Theorem 1.3 to conclude that A ∈ P as well. Therefore, P = NP.
The discovery of NP-Complete languages was a major step in our understanding of the relation- ship between P and NP. It shows that, if we want to prove that P = NP, it suffices to show that a single NP-Complete language is in P. Conversely, if P ̸= NP, then there can be no polynomial time solution to an NP-Complete problem.
Shortly after the discovery of the first NP-Complete problem, many other natural problems were found to be NP-Complete. If we know one NP-Complete problem, we can use it to prove the NP-Completeness of another problem similarly to how we proved the undecidability of problems using reductions.
Claim 2.4. If A ≤p B and A is NP-Hard, then B is NP-Hard.
This follows from transitivity of ≤p, which is proven in the homework.
Corollary 2.5. If A ≤p B, A is NP-Hard and B is in NP, then B is NP-Complete. This follows from the definition of NP-Completeness.
2.1 Examples of NP-Complete problems
Below are some languages that we have seen are NP-Complete and the method used to prove it.
• SAT: Cook- (Lecture 15)
• 3SAT: SAT ≤p 3SAT (Discussion Notes 8)
• VertexCover: 3SAT ≤p VertexCover (Lecture 16) • SetCover: VertexCover ≤p SetCover (Lecture 17) • HamCycle: HamPath ≤p HamCycle (Lecture 17)
EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 9 3 Examples of NP-Completeness Proofs
In this section, we will use what we learned about polynomial-time reducibility and NP-Completeness to prove the NP-Completeness of a few languages not listed above.
3.1 IndependentSet is NP-Complete
We give here for reference the definitions of the languages we will use in this section. Definition 3.1. Let G = (V,E) be an undirected graph.
• A vertex cover of G is a subset C ⊆ V such that for every edge (u,v) ∈ E, either u ∈ C or v ∈ C. In other words, every edge is touched by at least one vertex in C.
• An independent set of G is a subset I ⊆ V such that no two vertices in I share an edge. Definition 3.2.
VertexCover = {⟨G, k⟩ | G has a vertex cover of size k} IndependentSet = {⟨G, k⟩ | G has an independent set of size k}
We already know that VertexCover is NP-Complete. In this section, we will show that IndependentSet is NP-Complete.
Remember, to show that a language is NP-Complete, we need to show two things: that it is reducible from an NP-Hard language, and that it is in NP.
Claim 3.3. IndependentSet ∈ NP.
Proof. Given a certificate c = V′ such that V′ ⊆ V. We can find if c is a k-node independent set
with the following algorithm:
1. Check that c has k vertices
2. Check that c is a subset of V
3. For every pair of vertices (u, v) from V ′, check if (u, v) is an edge. If some pair has an edge between them, reject; otherwise, accept.
The first step takes O(|V|) time. The second step takes O(|V|2) time. The third step takes O(|V |2·|E|) time, since there are O(|V |2) pairs to check, and |E| edges to iterate through. Therefore, IndependentSet ∈ NP.
Claim 3.4. IndependentSet is NP-Hard.
Proof. We will show that VertexCover ≤p IndependentSet. Since VertexCover is NP- Hard, this will show that IndependentSet is NP-Hard.
Our input is of the form ⟨G, k⟩ where G is a graph and k is an integer. We want to construct a new pair ⟨G′,k′⟩ such that G has a vertex cover of size k if and only if G′ has an independent set of size k′.
We will simply output ⟨G, n − k⟩. Clearly, this can be performed in polynomial time. We claim that G has a vertex cover of size k if and only if it has an independent set of size n − k. In the following polynomial-time reduction we let G = (V, E).
EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 9
First, suppose G has a vertex cover C of size k. Let D = V \C, i.e., the set of vertices not in C. Then D has size n − k, where n is the number of vertices in G. We claim that D is an independent set. To see why, consider two vertices u, v ∈ D. Suppose (u, v) is an edge. Then either u or v is in the vertex cover C, which contradicts the fact that D consists of the vertices not in C. So (u,v) is not an edge; therefore, no vertices in D have an edge between them.
Now, suppose G has an independent set I of size n − k. Let H = V \ I, i.e., the set of vertices not in I. Then H has size k, and we claim that it is a vertex cover. To see why, consider any edge (u, v) ∈ E. Since I is an independent set, it cannot contain both u and v. So one of them must be in H. So H covers the edge (u, v).
From Claims 3.3 and 3.4, we have shown that IndependentSet is NP-Complete. 3.2 TSP is NP-Complete
We now turn our attention to a different graph problem that you may already be familiar with: the Traveling Salesperson Problem, or TSP. Our goal is to show that TSP is NP-Complete. Recall the following definitions of the decision versions of the following graph problems:
Definition 3.5.
HamCycle = {⟨G⟩ | G is an undirected graph with a Hamiltonian cycle}
TSP = {⟨G, k⟩ | G is an undirected, weighted, complete graph with a tour of weight ≤ k}
We proved in lecture that HamCycle is NP-Complete. Since every TSP tour is a Hamiltonian cycle by definition, it is intuitive to use HamCycle to show that TSP is NP-Complete.
Note that in our definition of TSP, we require that the graph be complete, while in our definition of HamCycle, a complete graph is not required. This is how TSP is commonly formulated, and it will require us to be more careful in our proof that TSP is NP-Hard.
Claim 3.6. TSP ∈ NP
Proof. We write an efficient verifier V for TSP that takes input (G,k), where G = (V,E), and a
certificate c, which is an ordered list of vertices in V . V((G,k),c) :
1. If G is not a complete graph, |c| ≠ |V |, or a vertex is repeated in c, then reject.
3. For each pair of adjacent vertices in c (the first and last vertices are also adjacent):
S := S + weight of edge 4. If S ≤ k, accept. Else, reject.
We will show that the verifier is correct. In order for c to be a correct solution to TSP given (G,k), it must contain every vertex in the original set of vertices exactly once. Furthermore, G must be a complete graph to allow a solution to TSP in the first place. The first step of the verifier correctly checks for these criteria, rejecting if one is not met. Next, the total weight of the tour described in c must be no greater than k. Steps 2 through 4 of the verifier check this by iterating over every adjacent pair of vertices in c and summing the edge weights into a variable, S, which is compared to k. If S ≤ k, then the verifier accepts, otherwise it rejects. Thus, the verifier is correct.
EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 9
Next, we will show that the verifier runs in polynomial time. Step 1 of the verifier checks if G is a complete graph, if |c| = |V |, and if c contains a repeated vertex. These operations are O(|E|), O(|V |), and O(|V |) respectively (note that if |c| ̸= |V |, then we can immediately reject). Step 2 initializes a variable, which is constant time. Step 3 iterates through every pair of adjacent vertices in c, which is O(|V |). If you do not assume random lookup is possible for finding the edges corresponding to each pair of vertices, Step 3 is O(|V ||E|), which is still efficient. Finally, Step 4 is a comparison against k which is O(|k|). Since every step of the verifier runs in polynomial time, the verifier is efficient.
We have shown that this verifier for TSP is correct and efficient. This proves TSP ∈ NP. Claim 3.7. TSP is NP-Hard
Proof. We will show that HamCycle ≤p TSP. Since HamCycle is NP-Hard, then it will follow that TSP is also NP-Hard.
We construct a function f that takes a graph G = (V, E) as input and outputs a graph-integer pair (G′, |V |) such that G ∈ HamCycle ⇔ f(G) = (G′, |V |) ∈ TSP. In English, f maps specific instances of HamCycle to specific instances of TSP, and specific non-instances of HamCycle to specific non-instances of TSP.
f(G = (V,E)) :
1. DefineE∗ :={(u,v)|u,v∈V}. NotethatE⊆E∗. 2. Define the weighted, complete graph G′ := (V, E∗). 3. For each e ∈ E∗, assign edge weights in G′ as follows:
if e ∈ E, |e| := 1
else, |e| := 2 4. Return (G′, |V |).
Now, we will analyze the correctness of this reduction. In both parts of this analysis, assume G = (V,E) and G′ = (V,E∗).
Suppose G ∈ HamCycle. Then by definition, there is a Hamiltonian cycle in G that traverses exactly |V | edges. Each edge in this cycle will be assigned a weight of 1 in the constructed graph G′,soG′ hasatourofweight|V|. Thus,f(G)=(G′,|V|)∈TSP.
Now let f(G) ∈ TSP. Then by definition, the graph G′, which is constructed by adding all the “missing” edges to G, has a tour of weight at most |V |. Since all edges in G′ have weight at least 1, and all tours in G′ must contain exactly |V | edges, then all tours in G′ must have a total weight of at least |V |. Consequently, G′ has a tour T of weight |V |. All edges in T must have weight 1, so by construction, T ⊆ E. In other words, all edges of the tour are part of the original graph G, so G ∈ HamCycle.
This shows that the reduction is correct, but it remains to be shown that it can be done in polynomial time. Step 1 of the reduction creates edges by finding every pair of vertices, which is O(|V |2). Step 2 of the reduction creates a graph using these edges, and so is O(|V |+|V |2) = O(|V |2). Step 3 of the reduction iterates through the edges, and so is O(|V |2). Step 4 of the reduction simply returns the new graph and number of vertices, and so is O(|V |2 + |V |) = O(|V |2). Every step of the reduction is polynomial time, so the reduction as a whole can be done in polynomial time. Therefore, we have shown that HamCycle ≤p TSP, proving that TSP is NP-Hard.
From Claims 3.6 and 3.7, we have shown that TSP is NP-Complete.
EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 9 3.3 (Optional) SetCover is NP-Complete
In this section we give a more formal version of a reduction that was given in lecture. Recall that if U is a set, the power set of U, denoted P(U), is the set of all subsets of U.
Definition 3.8. Let U be a set. A set cover of U is a subset T ⊆ P(U) such that for every element u ∈ U, there is some set in T that contains u. In other words, S∈T S = U. The language SetCover is
SetCover = {⟨U,S,k⟩ | S ⊆ P(U) and some subset T ⊆ S is a set cover of U of size k}. Claim 3.9. VertexCover ≤p SetCover.
Proof. We want to find a polynomial-time computable function f that maps strings of the form ⟨G, k⟩ to strings of the form ⟨U, S, k⟩ such that
⟨G, k⟩ ∈ VertexCover ⇔ ⟨U, S, k⟩ ∈ SetCover.
To perform the mapping, we will let U be the edge set of the graph, and then think of a vertex of the graph as a set of edges, those edges which are incident to it. More explicitly, the following program R computes the function f:
R = “On input ⟨G = (V,E),k⟩:
1. Let U = E.
2. Letn=|V|. Leti=1.
3. Let V = (v1, . . . , vn) be an arbitrary ordering of the vertices. 4. Fori=1,…,n:
(a) LetSi ={e∈E:eisincidenttovi} 5. Output ⟨U,S,k⟩, where S = {S1,…,Sn}.”
The only step that does not take constant time is step 4. In that step, we iterate through the edge set for each vertex, so the overall running time is O(|V | · |E|), which is polynomial in the input size |V | + |E|. Now we show that the reduction is correct.
First, suppose that G has a vertex cover W of size k. Then every edge of G is incident to some vertex of W. Therefore, vi∈W Si = U, so the Si form a set cover of U.
Now, suppose that U has a set cover T of size k. Then the sets in T represent vertices that cover the graph G; that is, {vi | Si ∈ T } is a vertex cover. This completes the proof.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com