Class Note for CMPSCI 601 at UMass(6)
Class Note for CMPSCI 601 at UMass(6)
Popular in Course
Popular in Department
This 20 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 14 views.
Reviews for Class Note for CMPSCI 601 at UMass(6)
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 18 Savitch s Theorem For 2 log n NSPACEsn Q DSPACEKSWW ImmermanSzelepcs nyi Theorem For 2 log n NSPACEsn c0NSPACEsn Closure Theorem Virtually all the classes we ve con sidered are closed downward under logspace reductions Exercise HW6 Logspace reductions are transitive ieifA g BandB g CthenA g C CMPSCI 601 Finite Model Theory Lecture 18 Consider the input the object we are working on to be a nite logical structure eg a binary string a graph a relational database or whatever Remember that a struc ture includes a list of the objects and lookup tables for all the variables constants relations and functions De nition 181 F0 is the set of rstorder de nable deci sion problems on nite structures Let S g STRUC nE S 6 F0 iff S A E STRUC nE A l 99 some cp E E Addition Q STRUCEAB gt STRUCZS A a1 a2 an1 an B 1quot b1 b2 bn l bn S 81 82 sn1 8n 02 E 3939 gt iAj BU ij gt k gt iAk v Bk QM 5 Ni 69 3 69 0039 QC 6 F0 Encode structures A E STRUC nE as binary strings binA Example binary strings binAw w 0 graphs 6 1 nEst bll lG 2 Guam annslsg Slogntl tlogn Theorem 182 FO g L DSPACE10gn Proof Given cp E 31V2 V2k Build DSPACE10g 71 TM M st A cp ltigt MbinA 1 By induction on k Base case k 0 9 E Est ll 9 Sgt Inductive step cp E 33V4 Vmgkkb By inductive assumption there is logspace TM M may ltgt M binA1 Modify M by adding 2 log nl worktape cells Worktape of M 51 02 Worktape of M WW og n1 og M M cycles through all values of 51 until it nds one such that for all 02 M accepts A A Java program can easily be written to test Whether A cp It has nested f or loops one for each quanti er Since it uses only a constant number of variables of logn bits each it represents a deterministic logspace algorithm CMPSCI 601 SecondOrder Logic Lecture 18 Secondorder logic consists of rstorder logic plus new relation variables over which we may quantify WNW For all choices of the rary relation A 99 holds SO is the set of secondorder expressible boolean queries 803 is the set of secondorder existential boolean queries AA xv SAT is the set of boolean formulas in conjunctive normal form CNF that admit a satisfying assignment CESAT E 351Vt30t gt Pt 1 Nt a IS Ct E t is a clause otherwise t is a variable Pt 19 E Variable 1 occurs positively in clause t N t 19 E Variable 1 occurs negatively in clause t 9 E 01VLT2V2931V2VAWV2V CLIQUE is the set ofpairs G k such that G is a graph that has a complete subgraph of size k Let Injf mean that f is an injective function 1njf E Vivy fv M gt 5621 CDCUQUE E 3f1Injfvayfv y it lt k y lt k gt E00 10 Theorem 183 Fagin s Theorem NP is equal to the set of existential secondorder b00lean queries NP SOS Proof NP Q 803 We are given a secondorder exis tential sentence I 31113RZ CM e mi Build NP machine N st for all A E STRUC nE A CD ltgt NbinA 1 184 A E STRUC nE n N nondeterministically writes down a binary string of length n quot1 representing R1 and similarly for R2 through Rk A Z A R13R2739 39 39 N accepts iff A l w Since FO g L Th 192 we can test if A l w in logspace and s0 certainly in NP Thus Equivalence 184 holds 11 NP g 803 Let N be an NTIMEnquot TM Write an SOS sentence e m h1 n e mag meaning There exists an accepting computation a A of N We will Show that Atc1gt ltgt NbinA1 Remark 186 Assume that language has numeric rela tions 3 SUC ana constants 0 max refering to total or a ering on the universe its successor relation the min imum and maximum elements in this ordering respec tively Then 9 in Equation 85 can be made universal 99 E V5131 WW with w quanti er free 12 CMPSCI 601 Encoding N s Computation Lecture 18 Fix A n Possible contents of a computation cell for N F y yg1 0581 8k t1 tk means cell 5 at time is symbol Yz A03 means the f 1St step of the computation makes choice 1 otherwise it makes choice 0 l3 Space 0 1 g n 1 n 71 1 A TimeO 10200 wl wn1 LJ LJ 60 1 wt fl11111 wn i LJ LJ 51 I CL1 a0 a1 6 1 I 6t1 nk l qf1 LJ LJ um LJ Accepting computation of N on input wgwl wn1 14 Write rstorder sentence 996 A saying that a A codes a valid accepting computation of N 9 E aA AnAC ll row 0 codes input binA V5 ii ohmic 035 13 V aow f 1 follows from row i Via move A0 of N H Ixde I ll last row of computation is accept ID A Cl ltigt NbinA 1 D s Seamancgwm ll 3 an accepting compution N me l 15 04 E row 0 codes input binA Assume E has only single unary relation symbol R i O 1 71 1 n iltqow0gt wl wn1 L L 70 0 71 1 72 LJ 3 m0 4 101 a E R0 gt 04016 A 410 gt 036 6 A W gt 0Ri gt 016239 6 A 412 gt 006239 6 A V3 2 nC 2 6 l6 Most interesting case 77 a1 a0 a1 A b Triple a1 a0 a1 leads to 1 Via move 6 of N H 771 4A0 A7 lta1a0a16 b C a1 1 C ao C a1 1 Cb f1 Here 4 is if6 l and it is the empty symbol if6 0 77 E 770 771 772 where 770 and 772 encode the same information when E U and imax respectively A 17 Theorem 187 CookLevin Theorem SAT is NPcomplete This theorem was proved roughly simultaneously by Steve Cook in the USA and Leonid Levin in the USSR before Fagin proved his theorem We ll prove CookLevin as a corollary of Fagin s Theorem somewhat contrary to his tory But note that the proof of CookLevin in Sipser for example is almost the same as our proof of Fagin Proof Let B E NP By Fagin s theorem BAA q 303 39C39EfiAkva1wrvt fE with w quanti erfree and CNF with each Tj a disjunction of literals 18 Let A be arbitrary n De ne formula MA as follows boolean variables Caleb397e2k7AelaHaeka 1quot39gel quot39762k6 clauses 735 j1r Wt T is 736 with atomic numeric or input predicates R replaced by true or false according as they are true or false in A Occurrences of 066 and A are consid ered boolean variables 6 II 303 C39gZAkXle act J K 775 61etelA1j1 3 Elise E E m AEB ltgt AltIgt ltgt 99AESAT l9 Proposition 188 3SAT 99 E CNFSAT 9 has 3 3 literalsper clause 3 S AT is NPcomplete Proof Show SAT 3 3SAT Example 0 1V 2 H 7 C E 1 2d1AEV BVd2AV 4Vdg ESVK5Vd4AE4V 6v 7 Claim 0 6 SAT ltigt Cquot E 3SAT In general just do this construction for each clause in dependently introducing separate dummy variables for each cluase The AND of all the new 3Variable clauses is satis able iff the AND of all the 01d clauses is A 20
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'