Microsoft PowerPoint – CS332-Lec25-ann
BU CS 332 – Theory of Computation
Lecture 25:
• Final review
Reading:
Sipser Ch 7.1‐8.2, 9.1
Mark Bun
April 28, 2021
Final Topics
4/28/2021 CS332 ‐ Theory of Computation 2
Everything from Midterms 1 and 2
• Midterm 1 topics: DFAs, NFAs, regular expressions,
distinguishing set method
(more detail in lecture 8 notes)
• Midterm 2 topics: Turing machines, TM variants, Church‐
Turing thesis, decidable languages, countable and
uncountable sets, undecidability, reductions,
unrecognizability
(more detail in lecture 16 notes)
4/28/2021 CS332 ‐ Theory of Computation 3
Mapping Reducibility (5.3)
• Understand the definition of a computable function
• Understand the definition of a mapping reduction
• Know how to use mapping reductions to prove
decidability, undecidability, recognizability, and
unrecognizability
4/28/2021 CS332 ‐ Theory of Computation 4
Time and Space Complexity (7.1)
• Asymptotic notation: Big‐Oh, little‐oh
• Know the definition of running time and space for a TM
and of time and space complexity classes (TIME / NTIME
/ SPACE / NSPACE)
• Understand how to simulate multi‐tape TMs and NTMs
using single‐tape TMs and know how to analyze the
running time overhead
4/28/2021 CS332 ‐ Theory of Computation 5
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
4/28/2021 CS332 ‐ Theory of Computation 6
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/28/2021 CS332 ‐ Theory of Computation 7
Hierarchy Theorems (9.1)
• Formal statements of time and space hierarchy
theorems and how to apply them
• How to use hierarchy theorems to prove statements like
4/28/2021 CS332 ‐ Theory of Computation 8
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 and probabilistic proof systems
• Complexity of counting
https://cs‐people.bu.edu/mbun/courses/535_F20/
4/28/2021 CS332 ‐ Theory of Computation 9
Theory and Algorithms Courses after 332
• Algorithms
• CS 530/630 (Advanced algorithms)
• CS 531 (Optimization algorithms)
• CS 537 (Randomized algorithms)
• Complexity
• CS 535 (Complexity theory)
• Cryptography
• CS 538 (Foundations of crypto)
• Topics (CS 591)
E.g., Privacy in machine learning, algorithms and society,
sublinear algorithms, new developments in theory of
computing, communication complexity
4/28/2021 CS332 ‐ Theory of Computation 10
Algorithms and Theory Research Group
• https://www.bu.edu/cs/research/theory/
• Weekly seminar: Mondays at 11
https://www.bu.edu/cs/algorithms‐and‐theory‐seminar/
Great way to learn about research in theory of
computation!
4/28/2021 CS332 ‐ Theory of Computation 11
Tips for Preparing Exam
Solutions
4/28/2021 CS332 ‐ Theory of Computation 12
Designing (nondeterministic) time/space‐
bounded deciders
4/28/2021 CS332 ‐ Theory of Computation 13
• Key components: High‐level description of algorithm, explanation of
correctness, analysis of running time and/or space usage
…
Designing NP verifiers
4/28/2021 CS332 ‐ Theory of Computation 14
• Key components: Description of certificate, high‐level description of
algorithm, explanation of correctness, analysis of running time
NP‐completeness proofs
4/28/2021 CS332 ‐ Theory of Computation 15
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
Practice Problems
4/28/2021 CS332 ‐ Theory of Computation 16
4/28/2021 CS332 ‐ Theory of Computation 17
4/28/2021 CS332 ‐ Theory of Computation 18
4/28/2021 CS332 ‐ Theory of Computation 19
4/28/2021 CS332 ‐ Theory of Computation 20
4/28/2021 CS332 ‐ Theory of Computation 21
Use a mapping reduction to show that
∗ is
co‐unrecognizable
4/28/2021 CS332 ‐ Theory of Computation 22
Use a mapping reduction to show that
∗ is
unrecognizable
4/28/2021 CS332 ‐ Theory of Computation 23
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/28/2021 CS332 ‐ Theory of Computation 24
Give an example of a problem that is solvable in
polynomial‐time, but which is not in P
4/28/2021 CS332 ‐ Theory of Computation 25
Let
. Show that
4/28/2021 CS332 ‐ Theory of Computation 26
Which of the following operations is P closed
under? Union, concatenation, star, intersection,
complement.
4/28/2021 CS332 ‐ Theory of Computation 27
Prove that
is in NP
4/28/2021 CS332 ‐ Theory of Computation 28
Prove that is NP‐hard
4/28/2021 CS332 ‐ Theory of Computation 29
Which of the following operations is NP closed
under? Union, concatenation, star, intersection,
complement.
4/28/2021 CS332 ‐ Theory of Computation 30
Which of the following statements are true?
• =
• =
• =
4/28/2021 CS332 ‐ Theory of Computation 31
4/28/2021 CS332 ‐ Theory of Computation 32