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
4/29/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)
4/29/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
4/29/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
4/29/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
4/29/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)
4/29/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
4/29/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
4/29/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/
4/29/2020 CS332 – Theory of Computation 10
Tips for Preparing Exam Solutions
4/29/2020 CS332 – Theory of Computation 11
Designing (nondeterministic) time/space- bounded deciders
…
• Key components: High-level description of algorithm, analysis of running time and/or space usage
• A good idea: Explain correctness of your algorithm
4/29/2020 CS332 – Theory of Computation 12
Designing NP verifiers
• Key components: Description of certificate, high-level description of algorithm, analysis of running time
• A good idea: Explain correctness of your algorithm
4/29/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
4/29/2020 CS332 – Theory of Computation 14
Practice Problems
4/29/2020 CS332 – Theory of Computation 15
4/29/2020 CS332 – Theory of Computation 16
4/29/2020 CS332 – Theory of Computation 17
4/29/2020 CS332 – Theory of Computation 18
4/29/2020 CS332 – Theory of Computation 19
4/29/2020 CS332 – Theory of Computation 20
P
4/29/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.
4/29/2020 CS332 – Theory of Computation 22
Give an example of a problem that is solvable in polynomial-time, but which is not in P
4/29/2020 CS332 – Theory of Computation 23
𝐿𝐿=
{ 𝑤𝑤 ,𝑤𝑤 |∃strings𝑥𝑥,𝑦𝑦,𝑧𝑧suchthat𝑤𝑤 = 𝑥𝑥𝑦𝑦𝑧𝑧 Let1 2 1
and 𝑤𝑤2 = 𝑥𝑥𝑦𝑦𝑅𝑅𝑧𝑧}. Show that 𝐿𝐿 ∈ P. 4/29/2020 CS332 – Theory of Computation 24
Which of the following operations is P closed under? Union, concatenation, star, intersection, complement.
4/29/2020 CS332 – Theory of Computation 25
NP and NP-completeness
4/29/2020 CS332 – Theory of Computation 26
Prove that 𝐿𝐿𝐿𝐿𝐴𝐴𝐿𝐿𝐿𝐿 =
{ 𝐺𝐺, 𝑠𝑠, 𝑡𝑡, 𝑘𝑘 |𝐺𝐺 is an undirected graph containing
a simple path from 𝑠𝑠 to 𝑡𝑡 of length ≥ 𝑘𝑘} is in NP 4/29/2020 CS332 – Theory of Computation 27
Prove that 𝐿𝐿𝐿𝐿𝐴𝐴𝐿𝐿𝐿𝐿 is NP-hard
4/29/2020 CS332 – Theory of Computation 28
Which of the following operations is NP closed under? Union, concatenation, star, intersection, complement.
4/29/2020 CS332 – Theory of Computation 29
Show that if P = NP, there is a polynomial-time decider for 𝑈𝑈𝑈𝑈𝐴𝐴𝐿𝐿 = { 𝜙𝜙 |𝜙𝜙 is a formula
with exactly one satisfying assignment}
4/29/2020 CS332 – Theory of Computation 30
4/29/2020 CS332 – Theory of Computation 31
Space Complexity
4/29/2020 CS332 – Theory of Computation 32
Which of the following statements are true?
• 𝑈𝑈𝐿𝐿𝐴𝐴𝑆𝑆𝑆𝑆(2𝑛𝑛) = 𝑈𝑈𝐿𝐿𝐴𝐴𝑆𝑆𝑆𝑆(2𝑛𝑛+1) • 𝑈𝑈𝐿𝐿𝐴𝐴𝑆𝑆𝑆𝑆(2𝑛𝑛) = 𝑈𝑈𝐿𝐿𝐴𝐴𝑆𝑆𝑆𝑆(3𝑛𝑛)
• 𝑁𝑁𝑈𝑈𝐿𝐿𝐴𝐴𝑆𝑆𝑆𝑆(𝑛𝑛2) = 𝑈𝑈𝐿𝐿𝐴𝐴𝑆𝑆𝑆𝑆(𝑛𝑛5)
4/29/2020 CS332 – Theory of Computation 33
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.
4/29/2020 CS332 – Theory of Computation 34
4/29/2020 CS332 – Theory of Computation 35