Class Note for CMPSCI 601 at UMass(27)
Class Note for CMPSCI 601 at UMass(27)
Popular in Course
Popular in Department
This 17 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(27)
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 10 Thm The following problems are in polynomial time EmptyNFA N 1 Nisan NFA N 1 2DFA D 1 DisaDFA D 2 MemberNFA Nw 1 Nis an NFA w E N EqualDFA 101021 1 13102 DFAs 101 1021 EmptyCFL G 1 GisaCFG 10 1 MemberCFL Gw 1 GisaCFG w E G Thm E CFL is coRE complete CMPSCI 601 Logic Lecture 10 We turn now to a unit on mathematical logic the study of how mathematicians do mathematics We model this process as a piece of mathematics itself de ning mathe matical entities such as propositions and proof systems and proving things about them Because our problems are so general and abstract it is of ten hard to see exactly what real problems we are dealing with Logic is important to computer science in two main ways 1 Because computers implement mathematicallyde ned rules the results of logic tell us things about com putability and complexity 2 The problems of logic themselves provide applica tions for computing CMPSCI 601 Boolean Logic Syntax Lecture 10 Boolean variables X x1x2x3 A boolean variable represents an atomic statement that may be either true or false Boolean expressions 0 atomic xi T l 0 a ea for a Boolean eXp s A literal is an atomic expression or its negation xi xi T l Abbreviations lt gt is an abbreviation for is an abbreviation for a 5 gt ba V W a gt 5 lt gt w v 5 CH gt5 gt a gt gta Examples of boolean expressions 0 x1 0 2 V 152 0 171 lt gt 82 a gtbb gtc gta gtc CS601CM730A Boolean Logic Semantics Lecture 8 Truth assignment T X g X gt true false Xltp EX xi occurs in cp If X cp g X then T is appropriate to p T assigns truth value to p TT Tk i T ltgt true Ta ltgt TizaorTiz Tiz a ltgt Tb a Lemma101 Ta8 ltgt TaandT8 Ta gt ltgt Tbv aorTiz Talt gt ltgt Tai T2 De nition 102 a and B are semantically equivalent a E 5 iff for all T appropriate to a and T l a ltgt 0931 E x1Vi a gta E T a H E b gt a a gtb avb ab E av b ab E aA b tavb E bVa 0avbc E aVbc taVbc E aVbac 0 E lla Proposition 103 Every boolean expression up is equiv alent to one in Conjunctive Normal Form CNF and to one in Disjunctl ve Normal Form DNF Proof DNF look at the truth table for p HHHHOOOOR HHOOHHOOQ z lt gt y 0 1 O 1 1 1 O O 1 1 O O O O 1 1 O O O 1 O 1 1 1 itAngz ityAi xAgjM atyAz CNF put ap in DNF Use De Morgan s law C 1vCk og Ck De nition 104 A boolean expression 0 is satis able iff there exists T p p is valid iff for all T appropriate to p T p Q Proposition 105 For any boolecm expression up 906 UNSAT ltgt we VALID UNSAT g VALID VALID g UNSAT I t Proposition 106 0 p is unsatis able i cp p is satis able i cp E L a pisvalidi cp E T Proposition 107 SAT 6 NP Proof 0 6 SAT ltgt ETXT i 90 Given ltpwith Xltp 21 52 x3 xn1 x Nondeterminsitically T 1 b2 b3 bn1 bn Accept iff T p CMPSCI 601 HornSAT Lecture 10 Horn formulas are CNF formulas with at most one posi tive literal per clause Compare to PROLOG not that I know anything about PROLOG l Vy 2 ngVi 3 lylt x RI 3 2l lt xyz 351 lt T Theorem 108 HORNSAT E P Algorithm 109 HORNSATltp l T D no variables assigned true 2 While T PE 0 3 choose clause lt al or not satis ed 4 T T U B 5 if i e T then reject else accept 10 CMPSCI 601 2SAT Lecture 10 2SAT 90 6 SAT p e CNF with two literals per clause p0 x1VT2x2VT3x3x1 Fact 1010 2SAT E P and infact 2SAT is complete for NSPACElog Given a 2CNF formula 0 de ne the directed graph f 90 V90 E90 as follows Vgo 58178717 axnvxin E90 uv a v or v 22 occurs in 90 Two bars cancel out so i u 90 E 2SAT ltgt Vx e Xltp x i not in same SCC SCC strongly connected component 11 90 E 2SAT ltgt Vx e Xltp x i not in same SCC There is a path from 1 to T so T must hold There is a path from 2 to Z so 3 must hold Either y or y may hold 0 E 2SAT 12 CMPSCI 601 Boolean Circuits Lecture 10 De nition 1011 A boolean circuit is a rooted directed acyclic graph DAG C V E 81quot 8 V gt truefalse V U 551x2 13 CMPSCI 601 CircuitSAT Lecture 10 Proposition 1012 CircuitSAT E NP 14 CMPSCI 601 CVP Lecture 10 Proposition 1013 Circuit Value Problem CVP E P 15 CMPSCI 601 Circuit Classes Lecture 10 Circuits give a lowlevel model of computation partic ularly of parallel computation since gates on the same level operate in parallel C 01 02 Cg a sequence of boolean circuits where On has inputs x1 x2 2 36 w 6 071 1 0120100 1 Circuits are a hardware implementation of straightline programs gate inputl gate input2 gate not gatel gatel and gate4 gate2 and gate3 6 l 2 3 gate 4 not gate2 5 6 7 gate5 or gate 16 Complexity Resources for Circuits 0 Size number of gates and Wires 0 Depth length of longest path from r to leaf 0 Uniformity complexity of f n r gt On We de ne classes based on these just as we de ned classes based on time and space for Turing machines We ll see much more about these classes later 17
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'