Class Note for CMPSCI 601 at UMass(17)
Class Note for CMPSCI 601 at UMass(17)
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 16 views.
Reviews for Class Note for CMPSCI 601 at UMass(17)
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 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 Important Technical Fact Logspace reductions are transitive ie ifA g B and B 3 C then A g C CMPSCI 601 Finite Model Theory Lecture 19 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 191 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 EQ De ning Addition in FirstOrder Logic Addition is a function from pairs of binary numbers to binary numbers that is a map from structures of one VO cabulary to structures of another Q STRUC2AB gt STRUCES A a1 a2 an1 an B b1 b2 bn1 bn S 81 82 sn1 8n 0039 E 3939 gtiAjBj Vim gt k gt 29mm v Bk QM 3 Ah 69 3039 69 0039 QC 6 F0 Each bit of the sum is de nable by a rstorder formula Structures and Strings Our computational models act on various different data structures Turing machines take strings usually binary strings as input Propositional formulas take unstruc tured sets of bits Firstorder formulas take rstorder structures As long as typecasting among these different representa tions is easy in the context of the complexity problem we are considering we can deal with any of these rep resentations If pressed we can say that we are always dealing with strings With rstorder structures we pick a natural way to en code each structure A E STRUCf1n E as a binary strings binA Example 0 binary strings binAw w 0 graphs 6 l nEst 2 Guam annslsg Slogntl tlogn 0 pair ofnumbers ana1nb11b1n 4 Theorem 192 FO g L DSPACElogn Proof GiVeni 99 E 31V2 V2k a we build a DSPACElog 71 TM M such that A cp ltigt MbinA 1 We use induction on k the number of quanti er pairs Base case k 0 p E Es t or another atomic predicate Look up the right bit 99 E s g t or another numerical predicate Do the calcu lation with the given values Inductive step 9939 E 3503XW4 va2kW Note that if other variables like 51 or 52 appear in w they must be replaced by particular values By the inductive hypothesis there is a logspace TM M A l 99 ltigt M binA 1 We modify M by adding 2 log nl worktape cells Worktape of M 01 02 Worktape of M WW log n log n M cycles through all values of 51 until it nds one such that for all 02 M accepts Q 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 19 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 In a nite model with a universe of size n a rstorder variable represents the name of an element of the uni verse which is flog nl bits A unary secondorder vari able Ac represents a property which each element of the domain has or doesn t have which is 71 bits And a kary relation Bc1 zrk requires n C bits to specify because it is true or false for each ktuple of domain ele ments SO is the set of secondorder expressible boolean queries SOS is the set of secondorder existential boolean queries where all the secondorder quanti ers are existential A x xv Graph 3C010rability is in SOS 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 onetoone func tion Being an injective function is a rstorder de nable property of a binary relation 1njf E Vivy fv M gt 5621 CDCUQUE E 3f1Injfvayfv y it lt k y lt k gt E00 We could name a particular set of vertices with a unary relation but the injective function lets us easily say that the set has size exactly k 10 Theorem 193 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 Cl E 3R ERZkkb E E We build an NP machine N such that for every A E STRUC nE A Cl ltigt NbinA 1 194 A E STRUC nE n N nondeterrninistically writes down a binary string of length n quot1 representing R1 and similarly for R2 through Rk A 1131132 Rk N accepts iff A l w Since FO g L as we showed earlier this lecture we can test whether A l w in logspace and so certainly in NP Thus Equivalence 194 holds 11 NP g SOS Let N be an NTIMEW onetape TM We will de ne an SOS sentence CD 303 og lnkyp 195 meaning There exists an accepting computation a A of N The main work will be de ning the rstorder paIt 9 We will show that A CI ltigt NbinA 1 Remark 196 Assume that language has numeric rela tions 3 SUC and 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 95 can be made universal 99 E V5131 WW with w quanti er free 12 CMPSCI 601 Encoding N s Computation Lecture 19 Fix A n Possible contents of a computation cell for N P y g1QXEUE 0581 3k t1 tk means that cell 5 at time is sym bOl A03 means that the 18t step of the computation makes nondeterministic choice 1 otherwise it makes choice 0 We have normalized N so that it chooses one bit per step 13 Space 0 l g n l n 71 l A TimeO 10200 wl wn1 LJ LJ 60 1 wt fl11111 wn i LJ LJ 51 I CL1 a0 a1 6t 1 5 6H1 nk l qf1 LJ LJ um LJ Accepting computation of N on input wgwl wn1 Note that we can tell Whether the symbol 1 occurs legally in this computation by looking at the symbols a1 a0 and a1 and consulting the state table of N 14 We now write a rstorder sentence 996 A saying that C39 A codes a valid accepting computation of N 9 E aA AnAC ll row 0 codes input binA V5 ii j 0z 035 13 V aow t 1 follows from row i Via move A0 of N H Ixde I ll last row of computation is accept ID A CI ltigt NbinA 1 ch E 303 Cg lnw ll 3 an accepting compution N me 1 15 Checking the start con guration 04 E row 0 codes input binA For simplicity we look at what happens when E has only a single unary relation symbol R so the input is just a binary string l O 1 71 171 nk1 ltqaw0gt wl wn1 L L 70 0 71 1 72 LJ 3 100 74 001 or 2 120 gt 040 0 A 430 gt 03 0 0 A w gt 0Rz gt 010 0 A 239 gt 000 0 A W 2 nCg 0 l6 The most interesting case 77 We View the state table of N as a nite function so that r a1 a0 a1 A b means that the triple a1 a0 a1 leads to 1 Via move 6 of N 4A0 N lta1a0a16 b C a1 1 0a0 ow 13 055 1514 Here 4 is if6 l and it is the empty symbol if6 0 77 E 770A771772 where 770 and 772 encode the same information when E U and imax respectively Q 17 Theorem 197 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 with n De ne a boolean 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 61et 4 i1 9 Elise E E m AEB ltgt AltIgt ltgt 99AESAT l9 Proposition 198 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 Q 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'