BU CS 332 – Theory of Computation
Lecture 24:
• Final review
Reading:
Sipser Ch 7.1‐8.3, 9.1
Mark Bun April 29, 2020
Final Topics
5/5/2020 CS332 ‐ Theory of Computation 2
Everything from Midterms 1 and 2
• Midterm 1 topics: DFAs, NFAs, regular expressions, pumping lemma, context‐free grammars, pushdown automata, pumping lemma for CFLs
(more detail in lecture 9 notes)
• Midterm 2 topics: Turing machines, TM variants, Church‐ Turing thesis, decidable languages, countable and uncountable sets, undecidability, reductions, unrecognizability, mapping reductions
(more detail in lecture 17 notes)
5/5/2020 CS332 ‐ Theory of Computation 3
Time Complexity (7.1)
• Asymptotic notation: Big‐Oh, little‐oh, Big‐Omega, little‐ omega, Theta
• Know the definition of running time for a TM and of time complexity classes (TIME / NTIME)
• Understand how to simulate multi‐tape TMs and NTMs using single‐tape TMs and know how to analyze the running time overhead
5/5/2020 CS332 ‐ Theory of Computation 4
P and NP (7.2, 7.3)
• Know the definitions of P and NP as time complexity classes
• Know how to analyze the running time of algorithms to show that languages are in P / NP
• Understand the verifier interpretation of NP and why it is equivalent to the NTM definition
• Know how to construct verifiers and analyze their runtime
• Understand the surprising implications of P = NP, esp. how to show that search problems can be solved in poly‐time
5/5/2020 CS332 ‐ Theory of Computation 5
NP‐Completeness (7.4, 7.5)
• Know the definition of poly‐time reducibility
• Understand the definitions of NP‐hardness and NP‐
completeness
• Understand the statement of the Cook‐Levin theorem (don’t need to know its proof)
• Understand several canonical NP‐complete problems and the relevant reductions: SAT, 3SAT, CLIQUE, INDEPENDENT‐SET, VERTEX‐COVER, HAMPATH, SUBSET‐ SUM
5/5/2020 CS332 ‐ Theory of Computation 6
Space Complexity (8.1)
• Know the definition of running space for a TM and of space complexity classes (SPACE / NSPACE)
• Understand how to analyze the space complexity of algorithms (including SAT, NFA analysis)
5/5/2020 CS332 ‐ Theory of Computation 7
PSPACE and PSPACE‐Completeness (8.2, 8.3)
• Know the definitions of PSPACE and NPSPACE
• Know why they’re equivalent (statement of Savitch’s
Theorem)
• Understand how to show that languages are in PSPACE
• Know the definition of PSPACE‐completeness
• You will not be asked anything about the PSPACE‐ complete language TQBF, or to show that any specific language is PSPACE‐complete
5/5/2020 CS332 ‐ Theory of Computation 8
Hierarchy Theorems (9.1)
• Know that we can prove, unconditionally, that P ≠ EXP and that PSPACE ≠ EXPSPACE
• You will not be asked about the formal statements of the time/space hierarchy theorems, but should understand how they generalize the above statements
5/5/2020 CS332 ‐ Theory of Computation 9
Things we didn’t get to talk about
• Additional classes between NP and PSPACE (polynomial hierarchy)
• Logarithmic space
• Relativization and the limits of diagonalization
• Boolean circuits
• Randomized algorithms / complexity classes
• Interactive proof systems
• Complexity of counting
https://cs‐people.bu.edu/mbun/courses/535_F20/
5/5/2020 CS332 ‐ Theory of Computation 10
Tips for Preparing Exam Solutions
5/5/2020 CS332 ‐ Theory of Computation 11
Designing (nondeterministic) time/space‐ bounded deciders
…
• Keycomponents:High‐leveldescriptionofalgorithm,analysisof running time and/or space usage
• Agoodidea:Explaincorrectnessofyouralgorithm
5/5/2020 CS332 ‐ Theory of Computation 12
Designing NP verifiers
• Keycomponents:Descriptionofcertificate,high‐leveldescriptionof algorithm, analysis of running time
• Agoodidea:Explaincorrectnessofyouralgorithm
5/5/2020 CS332 ‐ Theory of Computation 13
NP‐completeness proofs
To show a language is NP‐complete:
1) Show is in NP (follow guidelines from previous two slides)
2) Show is NP‐hard (usually) by giving a poly‐time reduction
for some NP‐complete language
• High‐level description of algorithm computing reduction • Explanation of correctness: Why is iff for
your reduction ?
• Analysis of running time
5/5/2020 CS332 ‐ Theory of Computation 14
Practice Problems
5/5/2020 CS332 ‐ Theory of Computation 15
5/5/2020 CS332 ‐ Theory of Computation 16
5/5/2020 CS332 ‐ Theory of Computation 17
5/5/2020 CS332 ‐ Theory of Computation 18
5/5/2020 CS332 ‐ Theory of Computation 19
5/5/2020 CS332 ‐ Theory of Computation 20
P
5/5/2020 CS332 ‐ Theory of Computation 21
Give examples of the following languages: 1) A language in P. 2) A decidable language that is not in P. 3) A language for which it is unknown whether it is in P.
5/5/2020 CS332 ‐ Theory of Computation 22
Give an example of a problem that is solvable in polynomial‐time, but which is not in P
5/5/2020 CS332 ‐ Theory of Computation 23
Let
. Showthat
5/5/2020
CS332 ‐ Theory of Computation 24
Which of the following operations is P closed under? Union, concatenation, star, intersection, complement.
5/5/2020 CS332 ‐ Theory of Computation 25
5/5/2020 CS332 ‐ Theory of Computation 26
NP and NP‐completeness
5/5/2020 CS332 ‐ Theory of Computation 27
Prove that
5/5/2020 CS332 ‐ Theory of Computation 28
is in NP
Prove that is NP‐hard
5/5/2020 CS332 ‐ Theory of Computation 29
Which of the following operations is NP closed under? Union, concatenation, star, intersection, complement.
5/5/2020 CS332 ‐ Theory of Computation 30
Show that if P = NP, there is a polynomial‐time decider for
5/5/2020 CS332 ‐ Theory of Computation 31
5/5/2020 CS332 ‐ Theory of Computation 32
Space Complexity
5/5/2020 CS332 ‐ Theory of Computation 33
Which of the following statements are true?
• = • =
• =
5/5/2020 CS332 ‐ Theory of Computation 34
Consider the inheritance problem from HW9, except Alice and Bob now take turns drawing bags from boxes. Alice’s goal is to assemble a complete collection of marbles, and Bob’s is to thwart her. Prove that determining whether Alice has a winning strategy is in PSPACE.
5/5/2020 CS332 ‐ Theory of Computation 35
5/5/2020 CS332 ‐ Theory of Computation 36
5/5/2020 CS332 ‐ Theory of Computation 37