DOC PREVIEW
UVA CS 302 - Classy Complexity Classes

This preview shows page 1-2 out of 6 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

1Class 22: Class 22: ClassyClassyComplexity Complexity ClassesClassesDavid 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 ScienceOffice hours note: my office hours tomorrow will be 10-11am in my office.PS6 (the last one) is posted now and will be due Thursday, April 24.2Lecture 22: Classy Complexity ClassesMenu• Why 2150?• Asymptotic Analysis• Mind vs. Turing Machine (from PS5)• Complexity Class P• Complexity Class NP3Lecture 22: Classy Complexity ClassesComputability 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 AliveFrom last class:4Lecture 22: Classy Complexity ClassesPredicting Knowledge• In golden age fields, knowledge doubles every 15 years (read Neil DeGrasse Tyson’s Science’s Endless Golden Age)• Hence, in 2158, we should know ~1024 times (10 doublings) what we know today• So, guessing it will end in ~2150 implies:– Computational Complexity is a finite field– What we know today is about 1/1000thwhat there is I don’t know if either of these is true, but they seem like reasonable guesses...5Lecture 22: Classy Complexity ClassesAsymptotic Notation Recap• Big-O: f ∈ O(g): no faster thanif there exist c, n0> 0 such thatf(n) ≤≤≤≤ cg(n) for all n ≥ n0.• Omega: f ∈ Ω(g): no slower thanif there exist c, n0> 0 such that f(n) ≥≥≥≥ cg(n) for all n ≥ n0.• Theta: f ∈ Θ(g) iff f ∈ O(g) and f ∈ Ω(g)Little-o: < instead of ≤≤≤≤6Lecture 22: Classy Complexity ClassesAlgorithm Analysis• What is the asymptotic running time of the Java-ish procedure below:int gaussSum (int m) {int sum = 0;for (int i = 1; i <= m; i++) {sum = sum + i;}return sum;}Good “cs201/cs216” answer:Θ(n)What does this mean?What does it assume?27Lecture 22: Classy Complexity ClassesAlgorithm Analysis• gaussSum is order n: “A function that outputs the running time of gaussSum when the input is the value of the input is in Θ(n).int gaussSum (int m) {int sum = 0;for (int i = 1; i <= m; i++) {sum = sum + i;}return sum;}Assumes:m is unbounded(not true for real Java)+ is constant time(not true if m is unbounded)Note that these assumptions are mutually inconsistent so the answer is “wrong” (but useful).8Lecture 22: Classy Complexity Classes“Correct”ish Answersint gaussSum (int m) {int sum = 0;for (int i = 1; i <= m; i++) {sum = sum + i;}return sum;}Assume m is bounded (e.g., 32-bit integer as in real Java). Then, running time of gaussSum is in O(1).Assume m is unbounded. Then, the average running time of the + is in Θ(log m), so the running time of gaussSum is in Θ(m log m).9Lecture 22: Classy Complexity ClassesWhat are we really measuring?• Input size: number of tape squares it takes to write down the input• Running time: number of steps it takes before TM enters a final state• Input size for gaussSum = log m– Number of bits to represent m (not its magnitude)– Note: if we used unary it would be size mWhy doesn’t log base matter in asymptotic notations?10Lecture 22: Classy Complexity ClassesMost Correct Answerint gaussSum (int m) {int sum = 0;for (int i = 1; i <= m; i++) {sum = sum + i;}return sum;}Assume the size of the input Nis unbounded. Then, m ~ 2N. The running time of + is in Θ(log m) = Θ(N) so the running time of gaussSum is in ΘΘΘΘ(2NN) = where N is the sizeof the input.Is ΘΘΘΘ(2NN) = ΘΘΘΘ(2N)?Left as small challenge problem (everyone should be able to answer this using definition of ΘΘΘΘ.)11Lecture 22: Classy Complexity ClassesAlgorithm Analysisint gaussSum (int m) {int sum = 0;for (int i = 1; i <= m; i++) {sum = sum + i; }return sum;}cs201/cs216 answer: Θ(n)where n is the value of the inputcs302 answer: in ΘΘΘΘ(2NN) where N is the size of the input.cs432 answer: don't analyze Java code, analyze idealized pseudocode and state assumptions clearly.12Lecture 22: Classy Complexity ClassesgaussSum Problem• So, what is the time complexity of the gaussSum problem?Input: a positive integer mOutput: sum of the integers from 1 to m.From the previous analysis, we know an algorithm that solves it with running time in ΘΘΘΘ(N2N).This means the time complexity of the problem is in O(N2N). But it does not give a tight bound.313Lecture 22: Classy Complexity ClassesgaussSum Problem• Can we get a lower bound?Input: a positive integer mOutput: sum of the integers from 1 to m.At a minimum, we need to look at each symbol in the input. So, there is no algorithm asymptotically faster than ΘΘΘΘ(N).This means the time complexity of the problem is in Ω(N). But it does not give a tight bound.14Lecture 22: Classy Complexity ClassesgaussSum Problem• Can we get a tight bound?Input: a positive integer mOutput: sum of the integers from 1 to m.The time complexity of the problem is in Ω(N). The time complexity of the problem is in O(N2N). Ring ofpossibilitiesIs there a Θ bound?15Lecture 22: Classy Complexity ClassesGetting a Tighter BoundJohann Carl Friedrich Gauss, 1777-1855gaussSum(n) = (n + 1)(n/2)What is the fastest known multiplication algorithm?Until 2007: Schönhage-Strassen algorithmin Θ(N log N log log N)Today: Fűrer’s algorithmin Θ(N log N 2O(log*N))Tomorrow: unknown if there is a faster multiplication algorithm16Lecture 22: Classy Complexity ClassesBest Known BoundsInput: a positive integer mOutput: sum of the integers from 1 to m.The time complexity of the problem is in Ω(N). The time complexity of the problemis in O(N log N 2O(log*N)). Ring ofpossibilitiesGetting a tight bound for a problem is very hard!Need to prove you have the best possible algorithm.17Lecture 22: Classy Complexity ClassesMinds vs. Turing MachinesProblem Set 5, Question 6: Many people find the suggestion that a human mind is no more powerful than a Turing Machine to be disturbing, but there appear to be strong arguments supporting this position. … Write a short essay that counters this argument (although many books have been written on this question, you should limit your response to no more than one page). If you reject the premise of this question either because you


View Full Document
Download Classy Complexity Classes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Classy Complexity Classes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Classy Complexity Classes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?