### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Class Note for CMPSCI 601 at UMass(17)

### View Full Document

## 16

## 0

## 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.

## Similar to Course at UMass

## Popular in Subject

## Reviews for Class Note for CMPSCI 601 at UMass(17)

### 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

### 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

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION 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 support@studysoup.com

#### STUDYSOUP REFUND POLICY

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: support@studysoup.com

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 support@studysoup.com

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.