Class Note for CMPSCI 601 at UMass(18)
Class Note for CMPSCI 601 at UMass(18)
Popular in Course
Popular in Department
This 31 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(18)
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
CMPSCI601 Summary amp Conclusions Lecture 27 We ve studied the main models and concepts of the the ory of computation 0 Computability what can be computed in principle 0 Logic how can we express our requirements 0 Complexity what can be computed in practice Concrete Mathematical CMPSCI601 Models of Computation Lecture 27 c How is the input organized c What computational operations are allowed 0 Do we have internal memory and how much An answer to these questions gives us a formal model of computation Some Formal Models of Computation Boolean c Formal Language Theory c FirstOrder Logic c Recursive Function Theory c Abstract RAM as in an algorithms course Boolean Computation Data Type Booleans true or false 0 or 1 Operations AND OR inclusive NOT can de ne more Variables Inputs 31 acn others yl ym Expressions x1 at 923 etc StraightLine Program y1 2 NOT Xl y2 y1 OR X2 y3 X3 AND x4 y4 y2 AND y3 5 y 2 OR xl return NOT y5 A straightline program is equivalent to a boolean circuit about which more later Each line of the program gate of the circuit has a truth value that is a function ofihe input variables Given a function of the inputs a property we will consider among other things how long a program is needed to compute it in this way Boolean Logic Chapters 18 of BE dealt with propositional or boolean logic The main topics were 0 Syntax and semantics for boolean expressions 0 Rules for proving that an expression is a tautology or that one expression follows logically from another 0 A formal proof system encapsulating these rules and implemented as interactive software included with the book The basics of boolean logic should have been review but formal proof may not have been We studied the system from the book and software starting on HW2 We then considered two important properties of the system 0 Soundness everything provable is true Completeness everything true is provable Here everything refers only to statements that can be made within the system FirstOrder Logic We can think of a sequence of boolean variables 30 acn1 as a single object X a function from the set 0 n 1 to 0 1 Thus for any number 239 in the range X is the boolean variable we used to call an X is also called a unary relation a property that each number in the range either has or doesn t have We can also have binary ternary or kary relations For example in a directed graph where the vertices are named 0 n 1 we have a binary relation E where the boolean Ez j is 1 iff there is an edge from 239 to j More FirstOrder Logic A rstorder structure roughly speaking is a universe of base objects and a set of relations over them If one of these relations is the input we can use rstorder logic to de ne properties of the input For example the rstorder sentence Va Ely Eay is true for the graph with edge relation E iff every vertex has outdegree at least one In Chapters 913 of BE we saw syntax and semantics for rstorder logic a set of proof rules for it and soft ware that lets you play with structures consisting of sets of blocks of different types on a grid We proved us ing later chapters of BE that this proof system is also sound and complete Recursive Function Theory Bits can be used to represent numbers by which I gener ally mean n0nnegaiive integers in binary General com putations may be coded as functions from numbers or tuples of numbers to numbers Kleene s recursive function theory de nes a set of gen eral recursive functions by induction There are base functions and rules for creating new functions from old ones It turns out that general recursive corresponds to algo rithmically computable This is a theorem not a de nition Primitive Recursion and Bloop An important subset of the partial recursive functions is the primitive recursive functions We will de ne these in terms of a simple programming language called Bloop My Bloop is based on the language of the same name in Hofstadter s G del Escher Bach but has a different syntax Variables represent numbers nonnegative integers They are declared and initialized to 0 when they rst appear Statements of Bloop consist of assignment statements x 0 the increment operator 0 function declarations and calls callbyvalue no re cursion 0 bounded loops for x B where x is a variable and B is a block of code in which x is not modi ed This code executes B exactly x times A mction is primitive recursive iff it can be implemented by a Bloop program Relations Among The Models Let s look at a single problem Given n input bits we want to know whether exactly two of them are ones This question can be posed in each of our models 0 Boolean There are various ways to build an SLP or circuit which we explored on HW1 0 FiniteState Machine Sweep the input string left toright remembering whether we ve seen zero one two or more than two ones 0 FirstOrder Logic 3x ly a yVzlzlt gt zszzzy 0 Numerical Input Is the input the sum of two dis tinct powers of two On HW1 you wrote a Bloop program to decide this 0 Abstract RAM The problem probably defaults to one of the others once we decide on our data repre sentation CMPSCI 601 Regular Sets Lecture 27 Kleene s Theorem Let A g 2 be any language Then the following are equivalent 1 A 2 D for some DFA D 2 A 2 N for some NFA N without 6 transitions 3 A 2 N for some NFA N 4 A 2 e for some regular expression 8 MyhillNerode Theorem The language A is regular iff NA has a nite number of equivalence classes Fur thermore this number of equivalence classes is equal to the number of states in the minimumstate DFA that ac cepts A Pumping Lemma for Regular Sets Let D 2 QE6 1017 be a DFA Let n 2 Let w E D st 2 n Then Elmyz E 2 st the following all hold 0 acyz 2 w 0 g n 0 gt 0 and 0 WC 2 0ayquotquot39z E D 10 CMPSCI 601 C FL S Lecture 27 Closure Theorem for Context Free Languages Let A B Q 2 be contextfree languages let R g 2 be a regular language and let h 2 gt I and g I gt 2 be homomorphisms Then the following languages are contextfree l A U B 2 AB 3 A Q R 4 MA 5 9 1A CFL Pumping Lemma Let A be a CFL Then there is a constant 72 depending only on A such that if z E A and 2 n then there exist strings u v w as 3 such that z 2 unwary and 0 I m 2 1 0 11mm 3 n and o for all k E N ruckwacky E A ll CMPSCI 601 Recursive Sets Lecture 27 A partial function is recursive iff it is computed by some TM M LetS Q 01 orS g N S is a recursive set iff the function X3 is a total recursive function where 1 ifacES me 0 otherwise 5 is a recursively enumerable set S is re iff the func tion p3 is a partial recursive function where 1 ifacES 33 Z otherwise Theorem Recursive re c0re 12 De ne the primitive recursive functions to be the smallest class of functions that 0 contains the Initial functions C a and 7g n 2 1 2 1 g 239 g n and 0 is closed under Composition and 0 is closed under Primitive Recursion De ne the general recursive functions to be the smallest class of functions that 0 contains the Initial functions and 0 is closed under Composition and 0 is closed under Primitive Recursion and 0 is closed under Unbounded Mimimalization Theorem Kleene COMPn as cy is a primitive recursive predicate Theorem A partial function is recursive iff it is general recursive l3 Cantor s Theorem 30N is not countable Proof Suppose it were Let f N De ne the diagonal set on 0 D n l n f7 b Thus D 2 fk for some k E N kED ltgt mm ltgt MD i Therefore 30N is not countable A n012345678fn 0amp00000000m 0 111111111f1 210010101f2 301001010f3 410000000f4 501101001f5 610010000f6 711000000f7 801000000mf8 100011011 D l4 CMPSCI 601 Uses Of Diagonalization Lecture 27 K nannl Theorem F is not re Know how to prove this Hierarchy Theorems Let f be a well behaved function and C one of DSPACE NSPACE DTIME NTIME If gm is suf ciently smaller than f then Cgn is strictly contained in C f L 901 suf ciently smaller than f 71 means limnm 11 0 limnm W 0 C DSPACE NSPACE NTIME C DTIME Hence P 7 EXPTIME L PSPACE But these are the only separations of classes we know Except at the pr and above level and for REG and CFL 15 Theorem The busy beaver function is eventually larger than any total recursive function Theorem Let S g N TFAE l S is the domain of a partial recursive function 2 S 2 D or S is the range of a total recursive function 3 S is the range of a partial recursive function 4 S 2 Wm some n 2 012 where W m 1 MW 1 16 CMPSCI 601 Logic Lecture 27 De nitions of Formula Structure and Truth Fitch Proof Rules 0 Propositional 12 Intro and Elim rules for A V gt lt gt and i 0 Equality 2 Intro and Elim for 2 0 Quanti er 4 Intro and Elim for El and V FOTHEOREMS 2 go 1 t cp FOVALID 2 90190 17 Soundness Theorem If i cp then lch FOTHEOREMS g FOVALID Completeness Theorem If 90 then i cp FOTHEOREMS Q FOVALID Corollary l FOTHEOREMS 2 FOVALID Compactness Theorem If every nite subset of F has a model then T has a model Godel s Incompleteness Theorem TheoryN true arithmetic is not re and thus not ax iomatizable If F is an re set of axioms that are all true in N then there exists a formula in TheoryN that is not provable from F 18 CMPSCI 601 Complexity Classes Lecture 27 Theorem For tn 2 71301 2 log n DTIMEtn g NTIMEtn g DSPACEtn DSPACEsn g DTIME20ltSlt gtgt Savitch s Theorem For 302 2 log n NSPACEsn g ATIMEsn2 g DSPACEsn2 ImmermanSzelepcs nyi Theorem For 302 2 log n NSPACEsn 2 coNSPACEsn 19 CMPSCI 601 Complexity Classes Lecture 27 Theorem For tn 2 71301 2 log n DTIMEtn g NTIMEtn g DSPACEtn DSPACEsn g DTIME20ltSlt gtgt Savitch s Theorem For 302 2 log n NSPACEsn g ATIMEsn2 g DSPACEsn2 ImmermanSzelepcs nyi Theorem For 302 2 log n NSPACEsn 2 coNSPACEsn 19 CMPSCI 601 Reductions Lecture 27 De nition A g B means there exists f E FL such that for any as a E A ifffa E B This is also called a logspace manyone reduction Theorem Let C be one of the following complex ity classes L NL P NP coNP PSPACE EXPTIME PrimitiveRecursive RECURSIVE re core Suppose A g B IfBEC Then AEC All these complexity classes are closed downward un der reductions Lower Bounds If A is hard then B is hard Upper Bounds If B is easy then A is easy 20 CMPSCI 601 Complete Problems Lecture 27 Complete for NL REACH EMPTYDFA EMPTY NFA 2SAT Complete for P CVP MCVP EMPTYCFL Hom SAT REACHa Complete for NP TSP SAT 3SAT 3COLOR CLIQUE Subset Sum Knapsack Complete for PSPACE QSAT GEOGRAPHY SUCCINCT REACH REGEXPZ Complete for re K HALT A0 FOVALID Complete for core K 2CFL EMPTY FOSAT 21 CMPSCI 601 Descriptive Complexity Lecture 27 Theorem re 2 FOEKN c0 re 2 FOWN PH 2 SO NP 2 803 P 2 SOSHorn AC0 2 CRAM1 LH 2 F0 One can understand the complexity of a problem as the richness of a logical language that is needed to describe the problem 22 CMPSCI 601 Alternation Lecture 27 Theorem For 301 2 log n and for tn 2 n ElATIMEKth kongSPACEtnk ASPACEsn 0 DTIMEWW 1 Corollary In particular ASPACE10gn 2 P ATIMEn0lt1gt PSPACE ASPACEnOlt1gt EXPTIME 23 CMPSCI 601 Circuit Complexity Lecture 27 depth 2 parallel time width 2 hardware number of gates 2 computational work 2 sequential time Theorem For alli CRAMlognquot 2 AC2 ACO g ThCO g NC1 g L g NL g sAC1 g AC1 g ThC1 g NC2 g sAC2 g g g g g ACZ39 g ThCZ39 g NCM g sACM g g g g g NC 2 NC 2 NC 2 NC 2 NC g P g NP 24 AlternationCircuit Theorem Logspace ATM s with 0logi n time give NCZ39 239 2 1 0logi n alternations give AC2 239 2 1 Alternating TM s are one good way to design uniform families of circuits We used this method to prove CFL g sACl Firstorder logic gives us another way to design uniform families of circuits We ve used this to construct ACO circuits by showing a problem to be in F0 We need uniformity de nitions on our circuit classes to relate them to ordinary classes For example polysize circuit families compute languages in P only if they are at least Puniform 25 Theorem PRIME and Factoring are in NP coNP PRIME is now in P as well Theorem SolovayStrassen Miller PRIME E BPP Fact REACHu E BPL Interactive Proofs NP P gtMAAM AMpoly IP PSPACE BPN P BPP Fact PCPlog n 1 NP 26 CMPSCI 601 Optimization Lecture 27 A is an optimization problem iff For each instance as F is the set of feasible solutions Each 3 E has a cost 03 6 Z For minimization problems OPTa 2 831 03 For maximization problems OPTa 2 813215 03 Let M be an algorithm st on any instance as M is an eapproximation algorithm iff for all as 10M50 OPTWN maxOPTa0Ma S 6 4 27 Clique TSP INAPPROX exists P appmx algfar n0 8 lt 1 MAX SAT ATSP VerteXCover APPROX same but nat all 8lt I PT As ETSP all 8lt I Kn apsac poly in n 18 28 Arithmetic Hierarchy re 30 129 W c0re F0 N roe complete F0 V N Recursive F0 MN Primitive Recursive EXPTIME PSPACE CONP PolynomialTime Hierarchy NP 1 SO comp ete c0NP NP complete sov 503 NP 1 coNP P f quottruly feasible SOHorn NC NC 2 logCFL SACl NSPACElog n DSPACElog n 1 Regular NC LogarithmicTime Hierarchy AC 29 CMPSCI 601 Where s the Catch Lecture 27 Why are the following so hard to prove P 7 NP P PSPACE ThCO 7 NP BPPP We do know a lot about computation Reductions and complete problems are a key tool So is the equivalence of apparently different models and methods Yet much remains unknown 30
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'