# 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

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