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

BU CS 332 – Theory of Computation

Lecture 19: • More on P

Reading:

Sipser Ch 7.2‐7.3

• Nondeterministic time, NP

Mark Bun April 8, 2020

First topic: Time complexity

Last time: Answering the basic questions

1. How do we measure complexity? (as in CS 330)

2. Asymptotic notation (as in CS 330)

3. How robust is the TM model when we care about measuring complexity?

4. How do we mathematically capture our intuitive notion of “efficient algorithms”?

4/8/2020 CS332 ‐ Theory of Computation 2

Running time and time complexity classes

Let

A TM runs in time if on every input , halts on within at most steps

is a class (i.e., set) of languages:

A language

tape (deterministic) TM that

1) Decides , and

2) Runs in time

if there exists a basic single‐

4/8/2020 CS332 ‐ Theory of Computation 3

Complexity Class

4/8/2020 CS332 ‐ Theory of Computation 4

Complexity class

Definition: is the class of languages decidable in polynomial time on a basic single‐tape (deterministic) TM

• Class doesn’t change if we substitute in another reasonable deterministic model (Extended Church‐Turing)

• Cobham‐Edmonds Thesis: Captures class of problems that are feasible to solve on computers

4/8/2020 CS332 ‐ Theory of Computation 5

A note about encodings

We’ll still use the notation for “any reasonable” encoding of the input to a TM…but now we have to be more careful about what we mean by “reasonable”

How long is the encoding of a ‐vertex graph… … as an adjacency matrix?

… as an adjacency list?

How long is the encoding of a natural number

… in binary? … in decimal?

… in unary?

4/8/2020 CS332 ‐ Theory of Computation 6

Describing and analyzing polynomial‐time algorithms

• Due to Extended Church‐Turing Thesis, we can still use high‐level descriptions on multi‐tape machines

• Polynomial‐time is robust under composition: executions of ‐time subroutines run on ‐ size inputs gives an algorithm running in time.

=> Can freely use algorithms we’ve seen before as subroutines if we’ve analyzed their runtime

• Need to be careful about size of inputs! (Assume inputs represented in binary unless otherwise stated.)

4/8/2020 CS332 ‐ Theory of Computation 7

Examples of languages in

• 𝑃𝐴𝑇𝐻 𝐺, 𝑠, 𝑡

𝐺 is a directed graph with a directed path from 𝑠 to 𝑡

• 𝐸

𝐷 𝐷 is a DFA that recognizes the empty language

4/8/2020

CS332 ‐ Theory of Computation 8

Examples of languages in

• •

4/8/2020

CS332 ‐ Theory of Computation 9

2006 Gödel Prize citation

The 2006 Gödel Prize for outstanding articles in theoretical computer science is awarded to Manindra Agrawal, Neeraj Kayal, and Nitin Saxena for their paper “PRIMES is in P.”

In August 2002 one of the most ancient computational problems was finally solved….

A polynomial‐time algorithm for ? Consider the following algorithm for

On input For

: by

Try to divide

If divides If all fail to divide

, accept , reject

How many divisions does this algorithm require in terms of ?

4/8/2020 CS332 ‐ Theory of Computation 10

CFG Generation

Theorem: Every context‐free language is in

Chomsky Normal Form for CFGs:

• Canhavearule𝑆 → 𝜀

• Allremainingrulesoftheform𝐴→𝐵𝐶or𝐴→𝑎 • Cannot have 𝑆 on the RHS of any rule

Lemma: Any CFG can be converted into an equivalent CFG in Chomsky Normal Form

Lemma: If is in Chomsky Normal Form, any nonempty string w that can be derived from has a derivation with at most steps

4/8/2020

CS332 ‐ Theory of Computation 11

CFG Generation

Theorem: Every context‐free language is in

Proof attempt: Let Form. Define a TM

be a CFL with a CFG recognizing :

in Chomsky Normal

On input : (Let

1. Enumerate all strings derivable in

2. If any of these strings equal , accept. Else, reject.

What is the running time of this algorithm?

A better idea: Use dynamic programming

‐ Identify subproblems

‐ Record solutions to subproblems in a table

)

‐ Solve bigger subproblems by combining solutions to smaller subproblems

4/8/2020 CS332 ‐ Theory of Computation 12

steps

4/8/2020 CS332 ‐ Theory of Computation 13

Examples of languages in

Problem

Description

Algorithm

Yes

No

MULTIPLE

Is x a multiple of y?

Grade school division

51, 17

51, 16

RELPRIME

Are x and y relatively prime? Is x prime?

Euclid (300 BCE) AKS (2002)

34, 39 53

34, 51

PRIMES

51

all CFLs

Is a given string in a fixed CFL?

Depends on

the

language;

e.g.

(([])[])

Depends on

the

language;

e.g.

([)], (()

(e.g. the language of balanced parentheses and brackets)

(E.g., is the string of parentheses and brackets balanced?)

Dynamic programming

LSOLVE

Isthereavectorxthat satisfiesAx=b?

Gauss-Edmonds elimination

1 0 0 1 1 1 1,1

4/8/2020

CS332 ‐ Theory of Computation

14

0 1 1 2

2 4 2, 4

031536 0111

Beyond polynomial time

Definition: is the class of languages decidable in exponential time on a basic single‐tape (deterministic) TM

4/8/2020

CS332 ‐ Theory of Computation 15

Nondeterministic Time and NP

4/8/2020 CS332 ‐ Theory of Computation 16

Nondeterministic time

Let

A NTM runs in time if on every input halts on within at most steps on every

,

computational branch

4/8/2020 CS332 ‐ Theory of Computation

17

Deterministic vs. nondeterministic time

Deterministic

Nondeterministic

accept or reject

reject reject

4/8/2020

CS332 ‐ Theory of Computation

18

𝒕𝒏

reject

accept

accept

Deterministic vs. nondeterministic time

Theorem: Let be a function. Every NTM running in time has an equivalent single‐tape TM running in

Finite control

𝑤 ⊔

# 𝑤 3 7

𝑤

nondeterministic choices from tape 3) Address in computation tree

4/8/2020

CS332 ‐ Theory of Computation 19

time

Proof: Simulate NTM by 3‐tape TM

𝑤 𝑤 𝑤 𝑤

Input 𝑤 to 𝑁 (read‐only) Simulation tape (run 𝑁 on 𝑤 using

1 3

Deterministic vs. nondeterministic time

Theorem: Let be a function. Every NTM running in time has an equivalent single‐tape TM running in

time

input

Proof: Simulate NTM by 3‐tape TM • # leaves:

• # nodes:

Running time:

simulation address

To simulate one root‐to‐node path:

Total time:

4/8/2020 CS332 ‐ Theory of Computation

20

Deterministic vs. nondeterministic time

Theorem: Let be a function. Every NTM running in time has an equivalent single‐tape TM running in

time

Proof: Simulate NTM by 3‐tape TM in time

We know that a 3‐tape TM can be simulated by a single‐ tape TM with quadratic overhead, hence we get running time

= ·=

4/8/2020 CS332 ‐ Theory of Computation 21