[SOLVED] CS algorithm BU CS 332 Theory of Computation

BU CS 332 Theory of Computation
Lecture 24:
Final review
Reading:
Sipser Ch 7.18.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, contextfree 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: BigOh, littleoh, BigOmega, little omega, Theta
Know the definition of running time for a TM and of time complexity classes (TIME / NTIME)
Understand how to simulate multitape TMs and NTMs using singletape 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 polytime
5/5/2020 CS332 Theory of Computation 5

NPCompleteness (7.4, 7.5)
Know the definition of polytime reducibility
Understand the definitions of NPhardness and NP
completeness
Understand the statement of the CookLevin theorem (dont need to know its proof)
Understand several canonical NPcomplete problems and the relevant reductions: SAT, 3SAT, CLIQUE, INDEPENDENTSET, VERTEXCOVER, 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 PSPACECompleteness (8.2, 8.3)
Know the definitions of PSPACE and NPSPACE
Know why theyre equivalent (statement of Savitchs
Theorem)
Understand how to show that languages are in PSPACE
Know the definition of PSPACEcompleteness
You will not be asked anything about the PSPACE complete language TQBF, or to show that any specific language is PSPACEcomplete
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 didnt 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://cspeople.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:Highleveldescriptionofalgorithm,analysisof running time and/or space usage
Agoodidea:Explaincorrectnessofyouralgorithm
5/5/2020 CS332 Theory of Computation 12

Designing NP verifiers
Keycomponents:Descriptionofcertificate,highleveldescriptionof algorithm, analysis of running time
Agoodidea:Explaincorrectnessofyouralgorithm
5/5/2020 CS332 Theory of Computation 13

NPcompleteness proofs
To show a language is NPcomplete:
1) Show is in NP (follow guidelines from previous two slides)
2) Show is NPhard (usually) by giving a polytime reduction

for some NPcomplete language
Highlevel 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 polynomialtime, 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 NPcompleteness
5/5/2020 CS332 Theory of Computation 27

Prove that
5/5/2020 CS332 Theory of Computation 28
is in NP

Prove that is NPhard
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 polynomialtime 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. Alices goal is to assemble a complete collection of marbles, and Bobs 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