Slide 1Exam 2Good NewsConfusing News?Bad NewsGood/Bad News4b4cComputability and ComplexityClasses 1-12Classes 13-20Today - EndComputability ComplexityComplexity ClassesInteresting Complexity ClassesThe “Petting Zoo”The Most Terrifying Beast: Subject of Ultimate MysteryP = NP ?Orders of GrowthOrder NotationSlide 21Big OExamplesFormal DefinitionO ExamplesLower Bound:  (Omega)Slide 27Inside-OutRecapSlide 30Theta (“Order of”)Tight Bound Theta ()SummaryAlgorithm AnalysisComplexity of ProblemsClass 21: Class 21: Introducing Introducing ComplexityComplexityDavid EvansDavid Evanshttp://www.cs.virginia.edu/evanshttp://www.cs.virginia.edu/evanscs302: Theory of Computationcs302: Theory of ComputationUniversity of Virginia Computer ScienceUniversity of Virginia Computer Science2Lecture 21: Introducing ComplexityExam 23Lecture 21: Introducing ComplexityGood News•96% of you got 1a (a language is a set of strings) correct•Most people got most credit for:–2a (design a TM)–2b (cyclical TM)–3a (one-way simulation proof claiming equivalence)4Lecture 21: Introducing ComplexityConfusing News?For question 1b (“Explain the essence of the Church-Turing Thesis in a way that would be understandable to a typical fifth grader”) more than half of you assumed a 5th grader knows what a Turing machine is (and about ¼ assumed they know Lambda calculus also!)Coming up with a good answer for this question with time pressure is tough. A good answer would either explain C-T thesis without needing TMs (using things a 5th grader already understands), or include an explanation of what a TM is. You can submit a new answer Tuesday. Or, find/make a 5th grader who understands TMs well enough to actually understand your answer.5Lecture 21: Introducing ComplexityBad News•Only 25/81 (>= 8 on 4b) and 24/81 (>= 8 on 4c) of you were able to get close to a convincing reduction proof.•But, to solve complexity problem, you will need to do tougher reduction proofs!These were pretty tough questions, so many its actually good news that ~30% got them.Practicing more now would be a good idea!6Lecture 21: Introducing ComplexityGood/Bad News•You have an opportunity to improve your score on Exam 2 by submitting improved answers to these questions•Good news: I will provide some hints how to get started next.•Bad news: Since I have provided hints, and you have as much time as you need, I expect very clear, convincing, correct answers.7Lecture 21: Introducing Complexity4bNOTSUBTM = { <A, B> | A and B are descriptions of TMs and there is some string which is accepted by A that is not accepted by B }8Lecture 21: Introducing Complexity4cLBusyBee = {<M, w, k> | M describes a TM, k is the number of different FSM states M enters before halting on w }9Lecture 21: Introducing ComplexityComputability and Complexity10Lecture 21: Introducing ComplexityClasses 1-12Regular LanguagesContext-Free LanguagesViolates Pumping Lemma For RLsViolates Pumping LemmaFor CFLsDescribed by DFA, NFA, RegExp, RegGramDescribed by CFG, NDPDA0n1n0n1n2n0nwDeterministic CFLsLL(k) LanguagesDescribed by LL(k) GrammarIndexed Grammars11Lecture 21: Introducing ComplexityClasses 13-20Decidable by any mechanical computing machineUndecidable12Lecture 21: Introducing ComplexityToday - EndDecidableUndecidableTractable: “Decidable in a reasonable amount of time and space”13Lecture 21: Introducing ComplexityComputability ComplexityDecidableUndecidable ~1800s – 1960s1900: Hilbert’s Problems1936: Turing’s Computable Numbers1957: Chomsky’s Syntactic Structures(Mostly) “Dead” fieldIntractableTractable1960s – 2150?1960s: Hartmanis and Stearns: Complexity class1971: Cook/Levin, Karp: P=NP?1976: Knuth’s O, Ω, ΘVery Open and Alive14Lecture 21: Introducing ComplexityComplexity Classes•Computability Classes: sets of problems (languages) that can be solved (decided/recognized) by a given machine •Complexity Classes: sets of problems (languages) that can be solved (decided) by a given machine (usually a TM) within a limited amount of time or spaceHow many complexity classes are there?Infinitely many! “Languages that can be decided by some TM using less than 37 steps” is a complexity class15Lecture 21: Introducing ComplexityInteresting Complexity Classeshttp://qwiki.stanford.edu/wiki/Complexity_Zoo467 “interesting” complexity classes (and counting)!16Lecture 21: Introducing ComplexityThe “Petting Zoo”“Under construction! Once finished, the Petting Zoo will introduce complexity theory to newcomers unready for the terrifying and complex beasts lurking in the main zoo.”cs302We will only get to the entrance of the “Petting Zoo”. But, even here there are “terrifying and complex beasts lurking”!17Lecture 21: Introducing ComplexityThe Most Terrifying Beast:Subject of Ultimate MysteryDecidableTractableNPOption 1: There are problems in Class NP that are not tractableOption 2: All problems in Class NP are tractableDecidableTractableNP18Lecture 21: Introducing ComplexityP = NP ?•We need a couple more classes before explaining this (but will soon)•This is an open question: no one knows the answer–If you can answer it, you will receive fame, fortune, and an A+ in cs302!–But, you should get some insight into what an answer would look like, and what it would mean19Lecture 21: Introducing ComplexityOrders of GrowthOrders of Growth20Lecture 21: Introducing ComplexityOrder NotationO( f ),  ( f ), o( f ), ( f ) Warning: you have probably seen some of these notations before in cs201 and cs216. What you learned about them there was probably (somewhat) useful but incorrect. (Note: if you learned them in cs150, then you learned them correctly.)21Lecture 21: Introducing ComplexityOrder Notation•O( f ), ( f ), o( f ), ( f ) •These notations define sets of functions–Generally: functions from positive integer to real•We are interested in how the size of the outputs relates to the size of the inputs22Lecture 21: Introducing ComplexityBig O•Intuition: the set O(f) is the set of functions that grow no faster than f–More formal definition coming soon•Asymptotic growth rate–As input to f approaches infinity, how fast does value of f increase–Hence, only the fastest-growing term in f matters:O(12n2 + n)  O(n3)O(n)  O(63n + log n – 423)23Lecture 21: Introducing ComplexityExamplesO(n3)O(n2)f(n) = n2.5f(n) = 12n2 + nf(n) = n3.1 – n2Faster Growing24Lecture 21: