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 To solve Factor n we find EulerTotient n n p 1 q 1 n 1 p q We then solve the system of equations p q p q n 1 n p p p2 2pq q 2 p q 2 4n to 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 of minimal 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 vertices U 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 FeedbackNodeSet create a graph G0 V 0 E 0 with V 0 V For each undirected edge u v E create directed edges u0 v 0 and v 0 u0 in E Return the unprimed versions of the vertices returned by FeedbackNodeSet 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 Given a graph G V E for each vertex vi V create a set Fi E of edges that have vi as an endpoint Run SetCover on the Fi to get the covering Fi1 Fim Return the corresponding vertices vi1 vim 4 Consider the following two problems Partition Given a P set n of non negative integers a1 an decide if there is there a subset P P 1 n such that i P ai i6 P ai Knapsack Given a set S a1 an of Pnon negative integers and an integer K decide if there is there a subset P S such that ai P K 1 Reduce Knapsack to Partition Solution Assume we have a black box algorithm Partition that can solve the Partition probPn lem Given an instance of Knapsack with integers S a1 an let H 12 i 1 ai Add integers an 1 2H 2K and an 2 4H to the set and return Partition a1 an 2 The reduction isPclearly polynomial To show it works we must showPthere exists P 1 n 2 with P a i i P i6 P ai if and only if there is some Q S such that ai Q K We first show that if there exists P there exists Q Firstly note that if an 1 P an 2 6 P since their sum is greater than the sum of the remaining integers WLOG assume an 2 P Then X X 4H ai 2H 2K ai P an 2 X 4H 2 ai S P ai 4H 2K ai P an 2 X K ai P an 2 Now assume there exists Q Then X X X ai 2H 2K ai ai 4H 4H K 2H K ai ai Q ai 6 Q so 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 TRUE or FALSE v1 vn and the boolean operators AND OR NOT a boolean expression written in conjunctive normal form CNF has the form x11 x12 x1m1 x21 x2m2 xk1 xkmk where each xij is either a boolean variable or the negation of a boolean variable Given a boolean expression written in CNF determine if there is some assignment of TRUE FALSE to each of the boolean variables v1 vn such that the expression 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 written in 3 CNF form determine if there is some assignment to each of the boolean variables such that 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 an instance of CNFSatisfiability Consider an instance Pn of CNFSatisfiability f x1 1 x1 m1 xn 1 xn mn Let there be L i 1 mn literals We introduce L 3n dummy variables 1 1 1 m1 3 n mn 3 and create 3 SAT instance f 0 by rewriting each clause ci as 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 f 0 The reduction is polynomial since L is polynomial in the number of literals in the CNFSatisfiability instance To show it works we show that f 0 has a satisfying solution if and only if f has a satisfying solution 2 Firstly assume f has a satisfying solution X1 1 X1 m1 Xn mn where Xi j is the value of literal xi j For example if xi j vk and vk has value TRUE in the satisfying assignment then Xi j FALSE Now consider applying that clause to c0i At least one of the Xi j must be TRUE or the solution would not be satisfying Let Xi k be this TRUE literal We can satisfy c0i by setting j k 2 FALSE and j k 2 TRUE Now assume f 0 has a satisfying solution X1 1 X1 m1 Xn mn 1 1 n mn 3 Consider clause ci in f We show that Xi 1 Xi mi satisfies ci Clearly if i 1 TRUE or i mi 3 FALSE ci must be satisfied since one of Xi 1 Xi 2 Xi mi 1 or Xi mi is TRUE Therefore assume both i 1 FALSE and i mi 3 TRUE Then by construction there must be some i j 2 xi j i j 1 in c0i such that i j 2 FALSE and i j 1 TRUE Since c0i is satisfied we must have Xi j TRUE and ci will also be satisfied 3
View Full Document
Unlocking...