PowerPoint Presentation
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
P ≠ EXP
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
https://cs-people.bu.edu/mbun/courses/535_F20/
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
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
Use a mapping reduction to show that
𝐴𝐴𝐿𝐿𝐿𝐿TM = { 𝑀𝑀 |𝑀𝑀 is a TM and 𝐿𝐿 𝑀𝑀 = Σ∗} is
co-unrecognizable
4/28/2021 CS332 – Theory of Computation 21
Use a mapping reduction to show that
𝐴𝐴𝐿𝐿𝐿𝐿TM = { 𝑀𝑀 |𝑀𝑀 is a TM and 𝐿𝐿 𝑀𝑀 = Σ∗} is
unrecognizable
4/28/2021 CS332 – Theory of Computation 22
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 23
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 24
Let 𝐿𝐿 =
{ 𝑤𝑤1,𝑤𝑤2 |∃ strings 𝑥𝑥,𝑦𝑦, 𝑧𝑧 such that 𝑤𝑤1 = 𝑥𝑥𝑦𝑦𝑧𝑧
and 𝑤𝑤2 = 𝑥𝑥𝑦𝑦𝑅𝑅𝑧𝑧}. Show that 𝐿𝐿 ∈ P.
4/28/2021 CS332 – Theory of Computation 25
Which of the following operations is P closed
under? Union, concatenation, star, intersection,
complement.
4/28/2021 CS332 – Theory of Computation 26
Prove that 𝐿𝐿𝐿𝐿𝐴𝐴𝐿𝐿𝐿𝐿 =
{ 𝐺𝐺, 𝑠𝑠, 𝑡𝑡, 𝑘𝑘 |𝐺𝐺 is an undirected graph containing
a simple path from 𝑠𝑠 to 𝑡𝑡 of length ≥ 𝑘𝑘} is in NP
4/28/2021 CS332 – Theory of Computation 27
Prove that 𝐿𝐿𝐿𝐿𝐴𝐴𝐿𝐿𝐿𝐿 is NP-hard
4/28/2021 CS332 – Theory of Computation 28
Which of the following operations is NP closed
under? Union, concatenation, star, intersection,
complement.
4/28/2021 CS332 – Theory of Computation 29
4/28/2021 CS332 – Theory of Computation 30
Which of the following statements are true?
• 𝑆𝑆𝐿𝐿𝐴𝐴𝑆𝑆𝑆𝑆(2𝑛𝑛) = 𝑆𝑆𝐿𝐿𝐴𝐴𝑆𝑆𝑆𝑆(2𝑛𝑛+1)
• 𝑆𝑆𝐿𝐿𝐴𝐴𝑆𝑆𝑆𝑆(2𝑛𝑛) = 𝑆𝑆𝐿𝐿𝐴𝐴𝑆𝑆𝑆𝑆(3𝑛𝑛)
• 𝑁𝑁𝑆𝑆𝐿𝐿𝐴𝐴𝑆𝑆𝑆𝑆(𝑛𝑛2) = 𝑆𝑆𝐿𝐿𝐴𝐴𝑆𝑆𝑆𝑆(𝑛𝑛5)
4/28/2021 CS332 – Theory of Computation 31
4/28/2021 CS332 – Theory of Computation 32
BU CS 332 – Theory of Computation
Final Topics
Everything from Midterms 1 and 2
Mapping Reducibility (5.3)
Time and Space Complexity (7.1)
P and NP (7.2, 7.3)
NP-Completeness (7.4, 7.5)
Hierarchy Theorems (9.1)
Things we didn’t get to talk about
Theory and Algorithms Courses after 332
Algorithms and Theory Research Group
Tips for Preparing Exam Solutions
Designing (nondeterministic) time/space-bounded deciders
Designing NP verifiers
NP-completeness proofs
Practice Problems
Slide Number 17
Slide Number 18
Slide Number 19
Slide Number 20
Use a mapping reduction to show that 𝐴𝐿𝐿 TM ={ 𝑀 |𝑀 is a TM and 𝐿 𝑀 = Σ ∗ } is co-unrecognizable
Use a mapping reduction to show that 𝐴𝐿𝐿 TM ={ 𝑀 |𝑀 is a TM and 𝐿 𝑀 = Σ ∗ } is unrecognizable
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.
Give an example of a problem that is solvable in polynomial-time, but which is not in P
Let 𝐿={ 𝑤 1 , 𝑤 2 |∃ strings 𝑥,𝑦,𝑧 such that 𝑤 1 = 𝑥𝑦𝑧 �and 𝑤 2 =𝑥 𝑦 𝑅 𝑧}. Show that 𝐿∈P.
Which of the following operations is P closed under? Union, concatenation, star, intersection, complement.
Prove that 𝐿𝑃𝐴𝑇𝐻={ 𝐺,𝑠,𝑡,𝑘 |𝐺 is an undirected graph containing� a simple path from 𝑠 to 𝑡 of length≥𝑘} is in NP
Prove that 𝐿𝑃𝐴𝑇𝐻 is NP-hard
Which of the following operations is NP closed under? Union, concatenation, star, intersection, complement.
Slide Number 30
Which of the following statements are true?
Slide Number 32