The following are a set of reduction problems in approximate order of difficulty.1. Consider the two problems:• Factor: Given a number n = pq, the product of two distinct primes p and q, find p and q.• EulerTotient: Given a number n = pq, where p and q are unknown primes, find φ(n) =(p − 1)(q − 1), the number of numbers less than n relatively prime to n.Reduce Factor to EulerTotient.Solution:Assume we have a black-box algorithm EulerTotient(n) that returns φ(n) = (p − 1)(q − 1). Tosolve Factor(n), we find EulerTotient(n) = φ(n) = (p − 1)(q − 1) = n + 1 − (p + q). We thensolve the system of equations:p + q = n + 1 − φ(n)p − q =pp2− 2pq + q2=p(p + q)2− 4nto find p and q.2. Consider the following two problems:• FeedbackNodeSet: Given a directed graph G = (V, E), find a set of vertices U ⊆ V ofminimal size such that if U is removed from V , G has no cycles.• VertexCover: Given an undirected graph G = (V, E), find a minimum set of verticesU ⊆ V such that for all (u, v) ∈ E, either u ∈ U or v ∈ U or both.Reduce VertexCover to FeedbackNodeSet.Solution:Given an undirected graph G = (V, E) and an algorithm for solving FeedbackNode-Set, create a graph G0= (V0, E0) with V0= V . For each undirected edge (u, v) ∈ E, createdirected edges (u0, v0) and (v0, u0) in E. Return the unprimed versions of the vertices returned byFeedbackNodeSet(G0).3. Consider the following problem:• SetCover: Given a set of sets S = {{a11, a12, ..., a1n1}, {a21, ..., a2n2}, ..., {am1, ..., amnm}}where the aij’s may not necessarily be distinct, find the minimum number of sets, A1, ..., Ak,necessary such that every element in any set in S is in at least one of the Ai.Reduce VertexCover to SetCover.Solution:Assume we have a black-box algorithm SetCover that solves the SetCover problem. Givena graph G = (V, E), for each vertex vi∈ V , create a set Fi⊆ E of edges that have vias anendpoint. Run SetCover on the Fito get the covering Fi1, ..., Fim. Return the correspondingvertices vi1, ..., vim.4. Consider the following two problems:• Partition: Given a set n of non-negative integers {a1, ..., an}, decide if there is there a subsetP ⊆ [1, n] such thatPi∈Pai=Pi6∈Pai.• Knapsack: Given a set S = {a1, ..., an} of non-negative integers, and an integer K, decideif there is there a subset P ⊆ S such thatPai∈P= K.1Reduce Knapsack to Partition.Solution:Assume we have a black-box algorithm Partition that can solve the Partition prob-lem. Given an instance of Knapsack, with integers S = a1, ..., an, let H =12Pni=1ai. Addintegers an+1= 2H + 2K and an+2= 4H to the set and return Partition(a1, ..., an+2). Thereduction is clearly polynomial. To show it works, we must show there exists P ⊆ [1, n + 2] withPi∈Pai=Pi6∈Paiif and only if there is some Q ⊆ S such thatPai∈Q= K.We first show that if there exists P , there exists Q. Firstly note that if an+1∈ P , an+26∈ P sincetheir sum is greater than the sum of the remaining integers. WLOG assume an+2∈ P . Then4H +Xai∈P \an+2ai= 2H + 2K +Xai∈S\P⇒ 4H + 2Xai∈P \an+2ai= 4H + 2K⇒Xai∈P \an+2= KNow assume there exists Q. ThenXai∈Qai+ 4H = 4H + K = 2H + K +Xaiai= 2H + 2KXai6∈Qaiso there also exists P = Q ∪ 4H.5. Consider the two problems:• CNFSatisfiability: Given a set of boolean variables (i.e. variables that can only be TRUEor FALSE), {v1, ..., vn} and the boolean operators ∧ (AND), ∨ (OR), ¬ (NOT), a booleanexpression written in conjunctive normal form (CNF) has the form (x11∨ x12∨ ...x1m1) ∧(x21∨ ... ∨ x2m2) ∧ ... ∧ (xk1∨ ... ∨ xkmk) where each xijis either a boolean variable or thenegation of a boolean variable. Given a boolean expression written in CNF, determine if thereis some assignment of TRUE/FALSE to each of the boolean variables v1, ..., vnsuch that theexpression evaluates to TRUE. Assume that mi≥ 3 for all i.• 3-SAT: A boolean expression written in 3-CNF form has the form (x11∨ x12∨ x13) ∧ ... ∧(xk1∨ xk2∨ xk3) where each clause has exactly 3 literals. Given a boolean expression writtenin 3-CNF form, determine if there is some assignment to each of the boolean variables suchthat the expression evaluates to TRUE.Reduce CNFSatisfiability to 3-SAT.Solution:Assume we have a black-box algorithm for 3-SAT. We show we can use this algorithm to solve aninstance of CNFSatisfiability. Consider an instance of CNFSatisfiability f = (x1,1∨ ... ∨x1,m1) ∧ ... ∧ (xn,1∨ ... ∨ xn,mn). Let there be L =Pni=1mnliterals. We introduce L − 3n dummyvariables λ1,1, ..., λ1,m1−3, ..., λn,mn−3and create 3-SAT instance f0by rewriting each clause cias:c0i= (xi,1∨ xi,2∨ ¬λi,1) ∧ (λi,1∨ xi,3∨ ¬λi,2) ∧ (λi,2∨ xi,4∨ ¬λi,3) ∧ ...∧(λi,mi−4∨ xi,mi−2∨ ¬λi,mi−3) ∧ (λi,mi−3∨ xi,mi−1∨ xi,mi)We return 3-SAT(f0).The reduction is polynomial since L is polynomial in the number of literals in the CNFSatisfia-bility instance. To show it works, we show that f0has a satisfying solution if and only if f has asatisfying solution.2Firstly, assume f has a satisfying solution, X1,1, ..., X1,m1, ..., Xn,mnwhere Xi,jis the value ofliteral xi,j. For example, if xi,j= ¬vkand vkhas value TRUE in the satisfying assignment thenXi,j=FALSE. Now consider applying that clause to c0i. At least one of the Xi,jmust be TRUE orthe solution would not be satisfying. Let Xi,kbe this TRUE literal. We can satisfy c0iby settingλj≤k−2= FALSE and λj>k−2= TRUE.Now assume f0has a satisfying solution, X1,1, ..., X1,m1, ..., Xn,mn, Λ1,1, ..., Λn,mn−3. Considerclause ciin f. We show that Xi,1, ..., Xi,misatisfies ci. Clearly if Λi,1= TRUE or Λi,mi−3=FALSE, cimust be satisfied since one of Xi,1, Xi,2, Xi,mi−1, or Xi,miis TRUE. Therefore, assumeboth Λi,1= FALSE and Λi,mi−3= TRUE. Then by construction there must be some (λi,j−2∨xi,j∨ ¬λi,j−1) in c0isuch that Λi,j−2= FALSE and Λi,j−1= TRUE. Since c0iis satisfied, we musthave Xi,j= TRUE and ciwill also be
View Full Document
Unlocking...