Class Note for CMPSCI 601 at UMass(28)
Class Note for CMPSCI 601 at UMass(28)
Popular in Course
Popular in Department
This 23 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 15 views.
Reviews for Class Note for CMPSCI 601 at UMass(28)
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 Formal Models of Computation 0 FA g Regular Expression PDA E CFG 0 TM E Recursive Function g Boolean Circuits 0 logical formula CMPSCI 601 Regular Sets Lecture 27 Kleene s Theorem Let A Q 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 wo 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 QZ6 1017 be a DFA Let n 2 Let w E D st 2 n Then Elmyz E 23 st the following all hold 0 acyz 2 w 0 g n 0 gt 0 and 0 WC 2 0ayquotquot39z E D CMPSCI 601 C FL S Lecture 27 Closure Theorem for Context Free Languages Let A B Q 23 be contextfree languages let R Q 23 be a regular language and let h 23 gt I and g I gt 23 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 CMPSCI 601 Recursive Sets Lecture 27 A partial function is recursive iff it is computed by some TM M LetS Q 01 orS Q N S is a recursive set iff the function X3 is a total recursive function 1 ifacES me 0 otherwise 5 is a recursively enumerable set S is re iff the func tion p3 is a partial recursive function lifazES pg 33 otherwise Th Recursive re c0re De ne the primitive recursive functions to be the smallest class of functions that 0 contains the Initial functions C a and 7a 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 GO del 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 Th Kleene COMPn as c y is a primitive recursive predicate Theorem A partial function is recursive iff it is Godel recursive Cantor s Theorem 30N is not countable Proof Suppose it were Let f N De ne the diagonal set 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 CMPSCI 601 Uses Of Diagonalization Lecture 27 K 2 Theorem Fis not re 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 Z 0 mum Z 0 c DSPACE NSPACE NTIME c DTIME Hence P y 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 Th The busy beaver function is eventually larger than any total recursive function Th Let S Q 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 Wu some n 2 012 where W m 1 MW 1 CMPSCI 601 Logic Lecture 27 De nitions of Formula Structure and Truth Axioms and Proof Rules Modus Ponens MP From 0 p gt w conclude 2p Proposition Modus Ponens preserves validity Axioms all generalizations of the following O Tautologies on at most three boolean variables la tzt 1b tlzt lAnAtkztg gtft1tkf1t 1c tlzt lAnAtkzt g gtRt1tk gtR1t 2 WW gt W lt t 3 p gt Vacltp a not free in p 4 WW gt I gt WWW gt WWW Proposition Every instance of every axiom is valid FOTHEOREMS 2 go 1 i cp Soundness Theorem If l cp then lch FOTHEOREMS Q FOVALID Completeness Theorem If 90 then l cp FOTHEOREMS Q FOVALID Corollary l FOTHEOREMS 2 FOVALID Compactness Th If every nite subset of F has a model then P has a model Godel s Incompleteness Theorem TheoryN is not re and thus not axiomatizable 10 CMPSCI 601 Complexity Classes Lecture 27 Th For tn 2 71301 2 logn DTIMEtn g NTIMEtn g DSPACEtn DSPACEsn g DTIME205W Savitch s Theorem For 302 2 log n NSPACEsn g ATIMEsn2 g DSPACEsn2 ImmermanSzelepcs nyi Theorem For 302 2 log n NSPACEsn 2 coNSPACEsn 11 CMPSCI 601 Complexity Classes Lecture 27 Th For tn 2 71301 2 logn DTIMEtn g NTIMEtn g DSPACEtn DSPACEsn g DTIME205W Savitch s Theorem For 302 2 log n NSPACEsn g ATIMEsn2 g DSPACEsn2 ImmermanSzelepcs nyi Theorem For 302 2 log n NSPACEsn 2 coNSPACEsn 11 CMPSCI 601 Reductions Lecture 27 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 under reduc tions Lower Bounds If A is hard then B is hard Upper Bounds If B is easy then A is easy 12 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 SUCCINT REACH REGEXPE Complete for re K HALT A0317 FOVALID Complete for core K ZY CFL EMPTY FOSAT l3 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 14 CMPSCI 601 Alternation Lecture 27 Theorem For 301 2 log n and for tn 2 n leATIMEtnk 1DSPACEtnk ASPACEsn I DTIMEWW 1 Corollary In particular ASPACE10gn 2 P ATIMEn0lt1gt PSPACE ASPACEn0lt1gt EXPTIME 15 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 CRAMlognquot39 2 ACquot AC0 g ThC0 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 sAC g g g g 2 NC 2 NC 2 NC 2 NC 2 NC g P g NP l6 AlternationCircuit Theorem Logspace ATM s with Ouagi n time give NCl 239 2 1 0logi n alternations give ACquot 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 AC0 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 l7 Theorem PRIME and Factoring are in NP 0 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 18 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 Zer For minimization problems OPTa 2 Sgg 03 For maximization problems OPTa 2 813216 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 l9 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 20 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 21 CMPSCI 601 Where s the Catch Lecture 27 Why are the following so hard to prove P 7 NP P PSPACE ThC0 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 22
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'