# CS代考计算机代写 algorithm BU CS 332 – Theory of Computation

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