Class Note for CMPSCI 601 at UMass(8)
Class Note for CMPSCI 601 at UMass(8)
Popular in Course
Popular in Department
This 16 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 12 views.
Reviews for Class Note for CMPSCI 601 at UMass(8)
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: 02/06/15
CMPSCI 601 Recall From Last Time Lecture 19 Finite Model Theory Descriptive Complexity Th FO g L DSPACE y Fagin s Th NP 2 03 ALltIgt ltgt NbinA1 I 303k Cg lAkE 2p is quanti erfree Space 0 1 72 1 72 nk l A TimeO 103200 wl wn1 LJ LJ 60 1 wt 6119111 wni U U 51 t a1a0 a1 6t 1 I 6H1 nk i 1151 LJ LJ LJ LJ Accepting computation of N on input wgwl wn1 Theorem 191 CookLevin Theorem SAT is NPcomplete Proof Let B E NP be arbitrary By Fagin s theorem BAAlltlgt ltIgt 303k 0351Akgtltvsc1 were with w quanti erfree and CNF Mi 2 K with each Tj a disjunction of literals For all A have A E B 42gt A l I Want A E B 42gt MA 6 SAT Let A be arbitrary n 2 Wanted A E B lt2 904 6 SAT De ne formula 904 as follows boolean variables 0681 38219A81338k 239 2 039 1 813 ng 61A clauses T j213r 6 6 14V Tj is Tj with the following replacements Rci cj r gt if 823 8 6 R then true else false 29 2 cj r gt if 81 2 8 then true else false 29 g cj r gt if 81 g 8 then true else false Cited 62k gt 05861 852k AC1 l gt A8 13 8 D 2 303k0 E1Mgtltm1w x il W J R T5 61ete1A1 321 J E E I AEB lt2 Al2ltlgt lt2 ltpAESAT Proposition 192 3SAT 2 90 E CNFSAT 0 has g 3 literalsper clause 3 S AT is NPcomplete Proof Show SAT g 3SAT Example 0 elvegvve7 C z 1v 2d1v 3d2v 4d3 V65Vd4AE4V 6V 7 Claim 0 6 SAT 42gt Cquot E 3SAT In general do this construction for each clause indepen dently p 6 SAT 42gt 90 e 3SAT 4 What about reducing 3SAT to SAT Can we do it Easily The identity function serves as a reduction be cause every 3SAT instance is also a SAT instance with the same answer This is an example of the general phe nomenon of one problem being a special case of another Another example was on HW5 where LEVELLED REACH was a special case of REACH and so clearly LEVELLEDREACH g REACH But what does it prove to reduce 3SAT to SAT Not much only the fact that 3 SAT is in NP or that LEVELLEDREACH is in NL neither of which was hard to prove anyway To prove that a special case of a general problem is complete for some class we have two options 1 Reduce the general problem to the speci c one or 2 Show that the completeness proof for the general case can be adapted to always yield an instance of the spe cial case For example in HW5 the rst method would be to fol low my hint and reduce REACH to LEVELLEDREACH directly The second method would be to show that when we map an arbitrary NL problem to a REACH instance we can get a LEVELLEDREACH instance This hap pens if the TM in question keeps a clock on its worktape for example Proposition 193 3COLOR is NPcomplete Proof Show 3SAT g 3COLOR 90 C1AC2AACt e 3CNF VARltp 2 3319 292 jacn Must build graph Gltp st 90 e 3SAT 42gt Gltp e 3COLOR Working assumption 3SAT requires 26 time G1 encodes clause 01 2 71 V 02 73 Claim Triangle a1 1 d1 serves as an or gate all may be colored true iff at least one of its inputs 571292 is colored true Similarly the output f1 may be colored true iff at least one of all and the third input 73 is colored true fi can only be colored true A three coloring of the literals can be extended to color G6 iff the corresponding truth assignment makes Ci true A Proposition 194 CLIQUE is NPcomplete Proof Show SAT g CLIQUE 90 C1AC2AAC e CNF VARltp 2 achacbuqacn Must build graph gltp st p 6 SAT 42gt gltp E CLIQUE L 173mT173Tn C39 2 chuqct W 2 was Ego km V C x L U 2110 EM 2 ahemcmm 1 c1 2 and 21 7 U 2002 lt6 6 manna 1 6 occurs in 6 kW 2 t1 10 X2 X2 X1 X1 1VT2VTn 01 90p v90 2 0 x L u mg ltCl 1gt3lt62 2gt 61 7A Cg and g1 7A 62 U 21203 033 ltc jw0 3 occurs inc E902 t1 km 11 v90 2 0 x L U 2120 Z Chg lt622 1 61 7A Cg and g1 7A 62 U 21 033 ltc jw0 3 occurs inc km t1 90 6 SAT 42gt 990 6 CLIQUE Claim 9 E FL 12 Proposition 195 Subset Sum is NPComplete m199mmT E N 35 Q 13r jsmi T 26 Show 3SAT g Subset Sum 90 C391C392C39t E 3CNF VARltp 2 123n Build f E FL such that for all p p E 3SAT 42gt ap 6 Subset Sum 13 E A gtm gt vnwb A2Rgtm gt v NO Ampugt gt v HHQ COCO Ov 1 O 1 v OOO 0000 1 000000 000000 CDC mv O v OOOO Q Knapsack Given n objects object 01 02 on weight w1 w2 mm 20 value 111 v2 on W max weight I can carry in my knapsack Optimization Problem chooseS C 13mm to maximize 2 vi 665 such that 2 mi g W 665 Decision Problem Given 2173179 W V can I get total value 2 V while total weight is g W 15 Proposition 196 Khapsack is NPComplete Proof Let I 2 m1 mm T be an instance of Subset Sum Problem ENS C 13n ZSmi 2 T 16 LetfI 2 m1 mmmlj 3mmTT be aninstance ofKnapsack Claim I E Subset Sum lt2 f I E Knapsack Fact 197 Even though Khapsack is NPComplete there is an e icieht dynamic programming algorithm that can closely approximate the maximum possible V 16
Are you sure you want to buy this material for
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'