New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Advanced Algorithms

by: Roman McCullough

Advanced Algorithms CMPSCI 611

Roman McCullough
GPA 3.57


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 36 page Class Notes was uploaded by Roman McCullough on Friday October 30, 2015. The Class Notes belongs to CMPSCI 611 at University of Massachusetts taught by Staff in Fall. Since its upload, it has received 16 views. For similar materials see /class/232274/cmpsci-611-university-of-massachusetts in ComputerScienence at University of Massachusetts.


Reviews for Advanced Algorithms


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/30/15
CMPSCI611 Greedy Algorithms and Matroids Lecture4 Our next algorithmic paradigm is greedy algorithms A greedy algorithm tries to solve an optimization problem by always choosing a next step that is locally optimal This will generally lead to a locally optimal solution but not necessarily to a globally optimal one When the goal of our optimization is to maximize some quantity we call a locally optimal solution maximal and a globally optimal one maximum If we are minimiz ing the quantity we call these minimal and minimum respectively We begin with a minimization problem that can be solved with a greedy algorithm CMPSCI611 Minimum Spanning Trees Lecture4 Suppose we have a weighted undirected graph G that is connected A spanning tree is a subset of the edges that is connected and is a tree that is it has no cycles Any connected graph has a spanning tree and it may have many of them A minimum spanning tree MST is a spanning tree that has a total weight sum of the weights of its edges that is no greater than that of any other span ning tree There may be more than one MST in case of t1es Note that edge weights are always positive We may sometimes use edge weights of zero but these could if necessary be thought of as just very small positive num bers Kruskal s Algorithm is a greedy solution to the mini mum spanning tree problem 0 Sort the edges by weight cheapest rst 0 Set F to be the empty set 0 For each edge e in order add 6 to F unless this would create a cycle in F 0 Return F We need a way to determine whether an edge 6 creates a cycle in F To do this we keep track of the connected components of F the sets of vertices of G such that two vertices are in the same component iff there is a path from one to the other in F Let 6 1 y where 1 and y are vertices If 1 and y are in the same component adding 6 to F would create a cycle If not adding 6 merges the two connected components The simplest way to merge the components is to scan a table mapping vertices to components moving each ver tex of the smaller component into the larger one We now need to prove that the Kruskal algorithm actually produces an MST First though a warrnup problem to get us used to working with graphs and induction OneQuestion Final Exam for CMPSCI 250 Let F be a forest a acyclic undirected graph with n ver tices k edges and 0 connected components Prove that e n k Proof by induction on e we show that the desired fact is an invariant As it was in the beginning is now and ever shall be Anglican Book of Common Prayer Base Case No edges n components n n 0 Inductive Step Add an edge it merges two connected components into one since if its endpoints were already connected it would create a cycle By induction 0 n 19 before now 0 l n k 1 Conclusion If we ever reach 19 n 1 then c l and we have a tree Correctness of Kruskal Given a forest F let S F be the set of spanning trees that contain all of F s edges As we add edges the following invariant stays true S F contains an MST Base Case Since G is connected an MST exists and it contains F which is 0 Inductive Step We assume that S F has an MST and we add the cheapest available edge called 6 1 y to F We must show that S F U 6 contains an MST We ll show that for any tree T in S F that doesn t in clude 6 there is a tree that does include 6 and has the same or lower total weight Since T is a tree it contains a path between 1 and y the endpoints of 6 Since there was no such path in F the path contains some edge e that is not in F Our cheaper tree is going to be T T e U 6 Since 6 was the cheapest available edge this set has total weight equal or smaller than that of T But how do we know that T is a tree T T 6 U 6 In T e u 1 was part ofa path from 1 to y In T we can still get from u to v by going from u back along the path to 1 over 6 to y and backward on the path to 1 So the only edge in T that is not in T can be successfully bypassed in T so every path in T can be simulated in T and T is connected Why doesn t T have a cycle A cycle would have to con nect 1 to y by another route But in the tree T there was a unique path from 1 to y and we broke it by removing 6 Conclusion At any time in the algorithm if F is not a tree there must be edges in G that join separate con nected components of F These edges must be at least as expensive as any edges in F since otherwise we would have looked at them already and added them to F be cause they join components of F So the algorithm can stop only when F is a tree At that point SF F so F itself must be an MST Timing of Kruskal The timing will depend on both n the number of vertices and k the number of edges Note that k 2 n l for a connected graph and k g 00 for any graph Sorting the list of edges takes 0k log k time Setting up our table of components for each vertex takes 0n time By the simple method we have described updating the table takes one pass over the table or C71 time We will make n 1 such sweeps for 00 total time because we will add an edge to F exactly n 1 times We also might spend up to 0k time checking edges that we don t add to F Thus Tn k 0k log k C71 0712 0k 0k log k 712 In a few lectures we ll see how to reduce this to 0k log k by using a better union nd data structure CMPSCI611 Subset Systems and Matroids Lecture4 When do greedy algorithms work It turns out that we can give an answer to this question for a wide class of optimization problems A subset system is a set E together with a set of subsets of E called I such that I is closed under inclusion This means that ifX g Y and Y E I then X E I The optimization problem for a subset system has as input a positive weight for each element of E Its output is a set X E I such that X has at least as much total weight as any other set in I We call I the independent sets of the subset system because in general I will be de ned so it will include ex actly those sets that don t have a particular kind of de pendence among their elements Let s see some exam ples Examples of Subset Systems Example 0 Let E be any set of vectors in some vector space and let I be the set of sets of linearly independent vectors Clearly this I is closed under inclusion This is the origin of the name independent sets Example 1 E 616263 I 061 2 37 17 27627693 The closure under inclusion can be checked directly I can also be described as all sets that don t contain both 61 and 63 Example 2 Let E be the edges of an undirected graph and I be the set of all acyclic sets of edges Example 3 Let E be the edges of an undirected graph and I be the set of sets of edges that don t have two or edges sharing a vertex These sets of edges are often called independent sets even outside this context and are also known as matchings The Generic Greedy Algorithm Given any nite subset system E I we nd a set in I as follows 0 Set X to 0 0 Sort the elements of E by weight heaviest rst 0 For each element of E in this order add it to X iff the result is in I 0 Return X This certainly gives us a set in I unless I is itself empty since 0 must be in I if any set is It is a maximal set meaning that no element of E can be added to it without bringing X outside of I But a solution to the optimiza tion must be a maximum set with weight greater than or equal to that of any other set in I Our main result is that there is a property of set systems that determines whether this greedy algorithm is guaran teed to give a maximum set for all possible weighting functions Greedy Algorithm Examples Subset System 1 not both 61 and 63 We will get 62 and the larger of 61 and 63 which must be a maximum set in I Subset System 2 acyclic sets This is the Maximum Weight Forest MWF problem which is the same as the MST problem except that a the input graph need not be connected and b we want to maximize instead of minimizing But we can convert the MST problem into an equivalent MWF problem and Vice versa as follows Let m be the maximum weight of any edge in the MWF problem and set the weight of each edge e in the MST problem to be m we E The greedy algorithms produce exactly the same set for the two weighting functions and since the number of edges in the MST must be n 1 a maximum set for one function is a minimum for the other Subset System 3 n0 edges sharing a vertex Here is an example where the greedy algorithm gets a maximal set that is not maximum 3 2 2 l2 l2 3 I 2 I I2 I I I l This is Figure 32 of the text The greedy algorithm takes both weight3 edges rst and gets the set in the center with a total weight of 6 But there is a different independent set that has weight 7 shown on the right CMPSCI611 De nition Of a Matroid Lecture 4 A subset system is a matroid if it satis es the exchange property If 239 and zquot are sets in I and 239 has fewer elements than 2 then there exists an element 6 E zquot 239 such that 2 U 6 E I Subset System 1 This is a matroid as we can check the exchange property by inspection For example if 2 61 zquot 62 63 we can let 6 62 Subset System 2 Next lecture we ll show that this is a matroid Subset System 3 This is not a matroid let 239 be the greedy matching and 2quot be the maximum matching in our example There is no edge e at all much less in 2quot that can be added to 239 while keeping it independent Next time we ll prove Theorem For any subset system E I the greedy al gorithm solves the optimization problem for E I if and only if E I is a matroid This is good mathematics We ve found a property of set systems that characterizes the behavior of the greedy al gorithm but doesn t have anything obvious to do with the algorithm Furthermore this property can be expressed in more than one way We ll also prove next time Cardinality Theorem A set system E I is a matroid iff for any set A g E any two maximal independent subsets of A have the same number of elements A property with ostensibly different characterizations is more likely to be mathematically interesting Examples of such properties in CMPSCI 601 include the regular languages and the Turingdecidable languages CMPSCI611 NP Completeness Lecture 17 Essential facts about NPcompleteness c Any NPcomplete problem can be solved by a simple but exponentially slow algorithm 0 We don t have polynomialtime solutions to any NP complete problem 0 We can prove that either all NPcomplete solutions have polynomialtime solutions or none of them do 0 It is generally believed that none of them do But proving this would require solving the P versus NP problem one of the best known unsolved problems in mathematics much less theoretical computer sci ence NPcompleteness is a property of decision problems It can be used to prove that other types of problems are NP hard which means that unless P NP they have no polynomialtime solutions These include search opti mization and approximation problems De nition The class P is the set of decision problems for which there exists an algorithm solving them in 0nk time for some constant 1 De nition A formal language A is in NP if there eXists another language B in P such that for any string 1 1 is in A iff there exists a string 3 with lyl m0 such that 1y is in B An equivalent more algorithmic de nition of NP is as follows An NPprocedure consists of a guess phase and a veri cation phase Given an input 1 the guess phase chooses an arbitrary string 3 such that lyl MO The veri cation phase is an algorithm that takes both 1 and y as input and returns a bit We say that 1 is in the language of the NPprocedure iff it is possible for the procedure to guess a 3 making the veri cation phase out put true There is an obvious deterministic decision procedure for any NP language simply cycle through all possible strings y and see whether the veri cation procedure accepts 1 y The problem is that there are 27pm possible y s of course Our question is whether there is a better way to decide membership in the NP language one that might run in polynomial time Proving a language to be in NP is generally simple We need to de ne a string to be guessed and de ne a poly time veri cation procedure that accepts the input and a guess iff the guess proves that the input is in the language We need to determine relationships among the languages in NP using the notion of reduction We want to show that if problem B is in P then so is problem A One way to do this is to describe an algorithm for A would run in polynomial time if it were allowed to make calls to a hypothetical polytime algorithm to decide membership in B This is called a Cook reduction For de ning NP completeness though we will need a slightly different notion of reduction Let A and B be two formal languages possibly over dif ferent alphabets A Karp reduction from A to B is a polytime computable function f such that for any string 51 1 E A if and only if f E B If such a reduction ex ists we say that A is polytime reducible to B and write A 3 B We also sometimes read this as A is no harder than B Two languages A and B are said to be pequivalent if both A 3 B and B 3p A The relation 3 is a partial order on the equivalence classes We are interested in the maximal equivalence class in NP De nition A language B is NPcomplete if 1 it is in NP and 2 for any language A in NP A 3 B Thus the NPcomplete languages if they exist are the hardest languages in NP It should be easy to see that they form an equivalence class and that if any NPcomplete language is also in P it follows that P NP If a language is NPcomplete then we have strong evi dence that it is not in P We can use the NPcompleteness of a language to talk about nondecision problems even though by de nition these cannot be NPcomplete De nition A problem X with boolean output or other wise is said to be NPhard if there is a Cook reduction from X to some NPcomplete problem B That is there is a polytime algorithm with access to a hypothetical polytime algorithm for X that decides B It should be clear that if X is NPhard and there actually is a polytime algorithm for X then P NP Our general methodology will be to develop a library of NPcomplete problems Once we have one problem there is a straightforward way to get more Lemma Let B be an NPcomplete language and A be a language If we prove OAENP ongl then we may conclude that A is NPcomplete But how do we start this process In CMPSCI 601 we prove the CookLevin Theorem that the language SAT is NPcomplete Last time we gave an unconditional proof that a particular generic NP language is NPcomplete We ll still need the CookLevin Theorem because SAT is a much more convenient starting place to build up a library of NPcomplete languages CMPSCI611 SAT and 3SAT Lecture 17 Remember that a boolean formula is de ned to be satis able if there is at least one setting of its input variables that makes it true The language SAT is the set of boolean formulas that are satis able Recall that a boolean formula is in conjunctive normal form CNF if it is the AND of zero or more clauses each of which is the OR of zero or more literals A for mula is in 3CNF if it is in CNF and has at most three literals in any clause The language CNFSAT is the set of CNF formulas that are satis able and the language 3SAT is the set of 3CNF formulas that are satis able Note that 3SAT is a subset of CNFSAT which is a sub set of SAT In general if A g B we can t be certain that A 3p B Although the identity function maps elements of A to elements of B we can t be sure that it doesn t map a nonelement of A to an element of B But here we know more we can easily test a formula to see whether it is in CNF or 3CNF To reduce 3SAT to SAT for ex ample we map a formula ltp to itself if it is in 3CNF and to 0 if it is not A similar reduction works to show A 3 B whenever A is such an identi able special case ofB thatiswhenA B CandC E P 6 The CookLevin Theorem tells us that SAT is NPcomplete essentially by mapping an instance of the generic NP problem to a formula that says that a particular string is a witness for a particular NPprocedure on a particular input Recall that if A is an NP language de ned so that 1 E A iff 3y 1 y E B we call 3 variously a witness proof or certi cate of x s membership in A We d like to show that CNFSAT and 3SAT are also NP complete It s clear that they are in NP but the easy spe cial case reduction does not su ice to show them NP complete We can reduce 3SAT to SAT but what we need is to reduce the known NPcomplete language SAT to the language we want to show to be NPcomplete 3 SAT On HW4 I ll have you work through the general re duction from SAT to 3SAT Here I ll present the eas ier reduction from CNFSAT to 3SAT The proof of the CookLevin Theorem given in CMPSCI 601 actually shows directly that CNFSAT is NPcomplete Let s now see how to reduce CNFSAT to 3SAT We need a function f that takes a CNF formula ltp in CNF and produces a new formula f m such that f m is in 3 CNF and the two formulas are either both satis able or both unsatis able If we could make ltp and f m equiv alent this would do but there is no reason to think that an arbitrary CNF formula will even have a 3CNF equiv alent form Every formula can be translated into CNF but not necessarily into 3CNF Instead we will make f m have a different meaning from ltp and even a different set of variables We will add vari ables to f m in such a way that a satisfying setting of both old and new variables of f m will exist if and only if there is a satisfying setting of the old variables alone in ltp In fact the old variables will be set the same way in each formula Because ltp is in CNF we know that it is the AND of clauses which we may name 11 V V Km 21 V V Em Elm V V Emkm where the E s are each literals For each of these clauses in ltp we will make one or more 3CNF clauses in f m possibly including new variables so that the one clause in ltp will be satis ed iff all the corresponding clauses in f m are satis ed So let s consider a single clause 1V V k in ltp Ifk g 3 we can simply copy the clause over to f m because it is already suitable for a CNF formula What if k 4 We can add one extra variable and make two clauses 1 V 2 V 11 and xl V 3 V 4 It s not too hard to see that both of these clauses are satis ed iff at least one of the E s is true If 1 or 2 is true we can afford to make 1 false and if E3 or E4 is true we can make 1 true The general construction for k gt 4 is similar We have 19 2 clauses and k 3 new variables The clauses are 1 V 2 V 1 171 V 3 V 2 172 V 4 V 3 and so on until we reach xkn V k2 V M4 and nally Ix k3 V k1 V If we satisfy the original clause with some 1 this satis es one of the new clauses and we can satisfy the others by making all the MS before it true and all those after it false Conversely if we satisfy all the new clauses we cannot have done it only with xi s because there are more clauses than xi s and each 511 only appears at most once as true and at most once as false and so can satisfy at most one clause Since this reduction is easily computable in polynomial time it shows that CNFSAT gp 3SAT and thus with the quoted result that CNFSAT is NPcomplete that 3 SAT is NPcomplete 3SAT is often the most convenient problem to reduce to something else but other variants of SAT are also some times useful One we ll use later is notallequalSAT or NAESAT Here the input is a formula in 3CNF but the formula is satis ed only if there is both a true literal and a false literal in each clause Let s prove that NABSAT is NPcomplete Is it in NP Yes if we guess a satisfying assignment it is easy in lin ear time to check the input formula and verify that there is a true literal and a false literal in each clause So we need to reduce a known NPcomplete problem to NAE SAT we ll choose 3SAT itself Again we ll transform each old clause into the AND of some new clauses in this case three of them Given the clause 1 V 2 V 3 we introduce two new vari ables 51 and 3 that appear only in the new clauses for this clause and a single new variable oz that appears several times The three new clauses are 1V 2VL IL V 3VyL VyVOz We must show that the three new clauses are jointly NAE satis able iff the original clause is satis able in the ordi nary way First we assume that the old clause is satis ed and show that we can choose values for 51 y and oz to NABsatisfy the new clauses We make oz true for all the clauses in the formula and consider the seven possibili ties for the values of 1 2 and 3 In each of the seven cases we can set 1 and 3 not both true to NABsatisfy the three new clauses we ll check this on the board Now assume that the three new clauses are NABsatis ed we will show that at least one of the Ei s is true First assume that 0 is true because if the new formula is NAE satis ed with 0 false we can just negate every variable in the formula and get a setting that NABsatis es all the clauses but has 0 true If 0 is true then either 1 or 3 must be false If 1 is false then either 1 or 2 must be true If y is false and 1 is true then 3 must be true So one of the three E s must be true and the original clause is satis ed in the ordinary way CMpscm CLIQUE and VERTEXCOVER Lecture 17 So far we ve seen that several problems in logic are NP complete In fact there are NPcomplete problems in a huge array of domains we ll next look at some prob lems in graph theory similar to some problems we ve already solved in polynomial time Let G be an undirected graph A clique in G is a set A of vertices such that all possible edges between elements of A exist in G Any vertex forms a clique of size 1 the endpoints of any edge form a clique of size 2 and any triangle is a clique of size 3 The language CLIQUE is the set of pairs G k such that G is an undirected graph that contains some clique of size k It should be clear that CLIQUE is in the class NP Our NPprocedure guesses an arbitrary set A of vertices by guessing a bitvector of length n Then the veri cation phase checks that A has size exactly 19 and that there is an edge between every pair of vertices in A We ll prove CLIQUE to be NPcomplete by reducing 3 SAT to it Recall that this means de ning a function from 3CNF formulas to graphinteger pairs such that satis able formulas are mapped to pairs G k such that G has a lcclique and unsatis able formulas are mapped to pairs where G does not have a lcclique The essential element of any reduction is a correspon dence between the witnesses of the two NPproblems The 3CNF formula is satis ed or not satis ed by a bitvec tor of length n and the possible cliques are also denoted by bitvectors We want to arrange the graph so that a sat isfying instance corresponds to a lcclique and Vice versa and we get to pick 19 for our convenience Here s the construction We have a node for each appear ance of a literal m the formula So if there are m clauses each with 1 literals the number of vertices in the graph is the sum from 1 to m of kl Now we need edges We place an edge between nodes 1 and y if they refer to lit erals that occur in di erem clauses and are not in con ict aren t negations of one another We set Is to be m the number of clauses Nodes Appearances of literals in clauses Edges Pairs of nodes that are in different clauses and not in con ict We claim that the 3CNF formula is satis able iff there is an mclique in the graph First assume that there is a sat isfying assignment which means that there is at least one literal in each clause that is set true Fix a set containing exactly one true literal in each clause The m nodes cor responding to these literals must form a clique No two of them are in the same clause and no two of them can be in con ict so all possible edges between then exist Conversely suppose that we have an mclique in the graph The m nodes must occur in m different clauses since edges only connect nodes in different clauses Because the m nodes also contain no con icts we can construct a setting of the variables consistent with all those literals We may have to arbitrarily set variables that don t occur in the set either as true or as false This setting makes at least one literal in each clause true so it satis es the formula With some easy reductions we can use CLIQUE to prove some similar problems to be NPcomplete Again let G be an undirected graph A set of vertices A is an independent set if there are no edges in G between vertices in A The language INDSET is the set of all pairs G k such that there exists an independent set of size k in G Clearly INDSET is in NP because we can guess the set A verify its size and verify that it contains no edges We prove INDSET to be NPcomplete by reducing CLIQUE to it now that we know CLIQUE to be NPcomplete This reduction will be a function that takes pairs G k to pairs H K such that G has a clique of size k iff H has an independent set of size E But this is easy The problems are very similar so much so that we can give H the same set of vertices as G and arrange that a set A is a clique in G iff it is an independent set in H How do we do this We want to map sets with all the edges to sets with none of the edges so we just make H the complement of G the graph that has an edge 1 y exactly when that edge is not an edge of G Then the function taking G k to H k is the desired reduction Another similar problem is VERTEXCOVER A set A of nodes of an undirected graph G is a vertex cover if every edge of G has at least one endpoint in A The lan guage VERTEXCOVER is the set of pairs G k such that G has a vertex cover of size k As before it is clear that VERTEXCOVER is in NP The Adler notes give a direct reduction from 3SAT to VERTEXCOVER which is very similar to the reduction from 3SAT to CLIQUE But we don t need to use this reduction because it s very easy to reduce CLIQUE or INDSET to VERTEXCOVER and thus use our previ ous work to prove VERTEXCOVER to be NPcomplete IfA g V is a vertex cover in G look at the set V A of nodes not in A There are no edges between these nodes since every edge has at least one endpoint in A So V A is an independent set in fact it is an independent set i A is a vertex cover So G has a vertex cover of size 9 iff it has an indepen dent set of size n k Thus the function taking G k to G n k is a reduction from INDSET to VERTEX COVER proving that the latter problem is NPcomplete We don t want to get carried away with this sort of ar gument though Consider the language NONCLIQUE de ned to be the set of pairs G k such that G does not have a clique of size k Is this problem NPcomplete In all likelihood it is not A Karp reduction must take yesinstances of one problem to yesinstances of the other so the identity map is not a Karp reduction In fact it s not at all clear that NONCLIQUE is in NP because there is nothing that we can guess to prove that a clique does not eX1st We de ne a class coNP to be the set of languages whose complements are in NP Note that this is quite different from the complement operation taking us from CLIQUE to INDSET We can de ne coNPcompleteness anal ogously to NPcompleteness and see that a language is coNPcomplete iff its complement is NPcomplete Could a language be both It follows easily from the de nitions that if there is NP and coNP are the same class This is considered unlikely though not quite as unlikely as P and NP being the same A Cook reduction is allowed to take the answer of a query and negate it so there is a simple Cook reduction from CLIQUE to NONCLIQUE To decide whether G k is in CLIQUE determine whether the same pair is in NONCLIQUE and reverse the answer So the coNP complete problems are all NPhard though probably not NPcomplete A nal note if we insist that k or n k be a constant CLIQUE and these other problems become solvable in P because we now have time to guess all possible cliques or independent sets or vertex covers Sometimes an identi able special case of an NPcomplete problem is eas1er l CMPSCI611 The SUBSET SUM Problem Lecture 17 For our nal problem today we revisit the SUB SETSUM problem the input is a set of numbers ah an and a target number t and we ask whether there is a sub set of the numbers that add exactly to t Using dynamic programming we showed that we could decide this lan guage in time that is polynomial in n and s the sum of all the 01 Now we allow the numbers to get larger so that they now might be n bits long The problem is still in NP because we can guess a subset by guessing a bitvector add the numbers in the set and verify that we get t But it s no longer clear that we are in P and in fact we will now see that the general problem is NPcomplete We reduce 3SAT to SUBSET SUM with large num bers We rst assume that every clause in our input for mula has exactly three literals we can just repeat literals in the same clause to make this true Our numbers will be represented in decimal notation with a column for each of the 1 variables and a column for each clause in the formula 20 We ll create an item 01139 for each of the 21 literals This item will have a l in the column for its variable a l in the column of each clause where the literal appears and zeroes everywhere else We also have two items for each clause each with a l in the column for that clause and zeroes everywhere else The target number has a l for each variable column and a 3 for each clause column We now have to prove that there is a subset summing to the target iff the formula is satis able If there is a sat isfying assignment we choose the item for each literal in that assignment This has one 1 in each variable col umn and somewhere from one to three 1 s in each clause column Using extra items as needed we can reach the target Conversely if we reach the target we must have chosen one item with a l in each variable column so we have picked 1 variables forming an assignment Since we have three 1 s in each clause column and at most two came from the extra items we must have at least one 1 in each clause column from our assignment making it a satisfy ing assignment 21 Given a problem with numerical parameters we say that it is pseudopolynomial if it becomes polynomial when those parameters are given in unary If it is NPcomplete with parameters given in unary we say that it is strongly NPcomplete The SUBSET SUM problem is pseudopoly nomial but all our graph problems are strongly NPcomplete Recall that the KNAPSACK is similar to SUB SETSUM but has a value for each item as well as its weight We are asked to nd whether a set of at least a given value exists with at most a given weight Since SUBSET SUM is an identi able special case of KNAPSACK where weight and value are both equal we know that SUB SETSUM 3p KNAPSACK Since KNAPSACK as a decision prob lem is in NP it is NPcomplete The associated opti mization problem is thus NPhard 22


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Kyle Maynard Purdue

"When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the I made $280 on my first study guide!"

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.