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

BU CS 332 – Theory of Computation

Lecture 19: • More on P

• Nondeterministic time, NP

Mark Bun April 8, 2020

Reading:

Sipser Ch 7.2-7.3

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𝑓𝑓∶ N→ N

A TM 𝑀𝑀 runs in time 𝑓𝑓(𝑛𝑛) if on every input 𝑤𝑤 ∈ Σ𝑛𝑛, 𝑀𝑀 halts on 𝑤𝑤 within at most 𝑓𝑓(𝑛𝑛) steps

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

A language 𝐴𝐴 ∈ TIME(𝑓𝑓(𝑛𝑛)) if there exists a basic single-

tape (deterministic) TM 𝑀𝑀 that

1) Decides 𝐴𝐴, and

2) Runs in time 𝑂𝑂(𝑓𝑓(𝑛𝑛))

4/8/2020 CS332 – Theory of Computation 3

Complexity Class P

4/8/2020 CS332 – Theory of Computation 4

Complexity class P

Definition: P is the class of languages decidable in

polynomial time on a basic single-tape (deterministic) TM

P = ⋃∞ TIME(𝑛𝑛𝑘𝑘) 𝑘𝑘=1

• 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: poly(𝑛𝑛) executions of poly(𝑛𝑛)-time subroutines run on poly(𝑛𝑛)- size inputs gives an algorithm running in poly(𝑛𝑛) 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 P • 𝑃𝑃𝐴𝐴𝑃𝑃𝑃𝑃 =

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

• 𝐸𝐸DFA = 𝐷𝐷 𝐷𝐷 is a DFA that recognizes the empty language} 4/8/2020 CS332 – Theory of Computation 8

Examples of languages in P

• 𝑅𝑅𝐸𝐸𝑅𝑅𝑃𝑃𝑅𝑅𝑅𝑅𝑀𝑀𝐸𝐸 = 𝑥𝑥, 𝑦𝑦 𝑥𝑥 and 𝑦𝑦 are relatively prime}

• 𝑃𝑃𝑅𝑅𝑅𝑅𝑀𝑀𝐸𝐸𝑃𝑃 = 𝑥𝑥 𝑥𝑥 is prime}

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….

4/8/2020 CS332 – Theory of Computation 9

A polynomial-time algorithm for 𝑃𝑃𝑅𝑅𝑅𝑅𝑀𝑀𝐸𝐸𝑃𝑃? Consider the following algorithm for 𝑃𝑃𝑅𝑅𝑅𝑅𝑀𝑀𝐸𝐸𝑃𝑃

On input 𝑥𝑥 : For𝑏𝑏=2,3,5,…, 𝑥𝑥:

Try to divide 𝑥𝑥 by 𝑏𝑏

If 𝑏𝑏 divides 𝑥𝑥, accept If all 𝑏𝑏 fail to divide 𝑥𝑥, 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 P

• Can have a rule 𝑃𝑃 → 𝜀𝜀

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

Chomsky Normal Form for CFGs:

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 most2 𝑤𝑤 −1steps

4/8/2020 CS332 – Theory of Computation 11

Theorem: Every context-free language is in P

Proof attempt: Let 𝐴𝐴 be a CFL with a CFG 𝐺𝐺 in Chomsky Normal

CFG Generation

Form. Define a TM 𝑀𝑀 recognizing 𝐴𝐴:

On input 𝑤𝑤: (Let 𝑛𝑛 = |𝑤𝑤|)

1. Enumerate all strings derivable in ≤ 2𝑛𝑛 − 1 steps 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

4/8/2020 CS332 – Theory of Computation 13

Examples of languages in P

Problem

MULTIPLE

RELPRIME

PRIMES

all CFLs

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

LSOLVE

Description

Is x a multiple of y?

Are x and y relatively prime?

Is x prime?

Is a given string in a fixed CFL?

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

Is there a vector x that satisfies Ax = b?

Algorithm

Grade school division

Euclid (300 BCE)

AKS (2002)

Dynamic programming

Gauss-Edmonds elimination

Yes

51, 17

34, 39

53

No

51, 16

34, 51

51

Depends on

the

language;

e.g.

(([])[])

Depends on

the

language;

e.g.

([)], (()

01121001 2 4 −2 , 4 1 1 1 , 1 031536 0111

4/8/2020

CS332 – Theory of Computation 14

Beyond polynomial time

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

EXP = ⋃∞ TIME(2𝑛𝑛𝑘𝑘) 𝑘𝑘=1

4/8/2020 CS332 – Theory of Computation 15

Nondeterministic Time and NP

4/8/2020 CS332 – Theory of Computation 16

Nondeterministic time

Let𝑓𝑓∶ N→ N

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

𝒕𝒕(𝒏𝒏)

reject

accept

accept

accept or reject

reject

reject

4/8/2020

CS332 – Theory of Computation

18

Theorem: Let 𝑡𝑡 𝑛𝑛 ≥ 𝑛𝑛 be a function. Every NTM running in time 𝑡𝑡 𝑛𝑛 has an equivalent single-tape TM running in

Deterministic vs. nondeterministic time

time 2𝑂𝑂(𝑡𝑡 𝑛𝑛 )

Proof: Simulate NTM by 3-tape TM

𝑤𝑤1 𝑤𝑤2 𝑤𝑤3 𝑤𝑤4

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

nondeterministic choices from tape 3) Address in computation tree

Finite control

𝑤𝑤1 ⊔

𝑤𝑤3 𝑤𝑤4

#

4/8/2020

CS332 – Theory of Computation 19

1

3

3

7

Theorem: Let 𝑡𝑡 𝑛𝑛 ≥ 𝑛𝑛 be a function. Every NTM running in time 𝑡𝑡 𝑛𝑛 has an equivalent single-tape TM running in

Deterministic vs. nondeterministic time

time 2𝑂𝑂(𝑡𝑡 𝑛𝑛 )

Proof: Simulate NTM by 3-tape TM 𝑀𝑀 • # leaves:

• # nodes:

Running time:

To simulate one root-to-node path:

Total time:

input simulation address

4/8/2020 CS332 – Theory of Computation

20

Theorem: Let 𝑡𝑡 𝑛𝑛 ≥ 𝑛𝑛 be a function. Every NTM running in time 𝑡𝑡 𝑛𝑛 has an equivalent single-tape TM running in

Deterministic vs. nondeterministic time

time 2𝑂𝑂(𝑡𝑡 𝑛𝑛 )

Proof: Simulate NTM by 3-tape TM in time 2𝑂𝑂(𝑡𝑡 𝑛𝑛 )

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

time

(2𝑂𝑂(𝑡𝑡 𝑛𝑛 ))2 =22�𝑂𝑂(𝑡𝑡 𝑛𝑛 ) =2𝑂𝑂(𝑡𝑡 𝑛𝑛 )

4/8/2020 CS332 – Theory of Computation 21

Difference in time complexity

Extended Church-Turing Thesis:

At most polynomial difference in running time between all (reasonable) deterministic models

At most exponential difference in running time between deterministic and nondeterministic models

4/8/2020 CS332 – Theory of Computation 22

Nondeterministic time

Let𝑓𝑓∶ N→ N

A NTM 𝑀𝑀 runs in time 𝑓𝑓(𝑛𝑛) if on every input 𝑤𝑤 ∈ Σ𝑛𝑛,

𝑀𝑀 halts on 𝑤𝑤 within at most 𝑓𝑓(𝑛𝑛) steps on every computational branch

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

A language 𝐴𝐴 ∈ NTIME(𝑓𝑓(𝑛𝑛)) if there exists an NTM 𝑀𝑀

that

1) Decides 𝐴𝐴, and

2) Runs in time 𝑂𝑂(𝑓𝑓(𝑛𝑛))

4/8/2020 CS332 – Theory of Computation 23

NTIME explicitly

A language 𝐴𝐴 ∈ NTIME(𝑓𝑓(𝑛𝑛)) if there exists an NTM 𝑀𝑀 such that, on every input 𝑤𝑤 ∈ Σ∗

1. Every computational branch of 𝑀𝑀 halts in either the

2. 3.

accept or reject state within 𝑓𝑓( 𝑤𝑤 ) steps

𝑤𝑤 ∈ 𝐴𝐴 iff there exists an accepting computational

branch of 𝑀𝑀 on input 𝑤𝑤

𝑤𝑤 ∉ 𝐴𝐴 iff every computational branch of 𝑀𝑀 rejects on

input 𝑤𝑤 (or dies with no applicable transitions)

4/8/2020 CS332 – Theory of Computation 24

Complexity class NP

Definition: NP is the class of languages decidable in

polynomial time on a nondeterministic TM

NP = ⋃∞ NTIME(𝑛𝑛𝑘𝑘) 𝑘𝑘=1

4/8/2020 CS332 – Theory of Computation 25

Hamiltonian Path

𝑃𝑃𝐴𝐴𝑀𝑀𝑃𝑃𝐴𝐴𝑃𝑃𝑃𝑃 = 𝐺𝐺, 𝑠𝑠, 𝑡𝑡 𝐺𝐺 is a directed graph and there

is a path from 𝑠𝑠 to 𝑡𝑡 that passes through every vertex exactly once}

𝑠𝑠𝑡𝑡

4/8/2020 CS332 – Theory of Computation 26

𝑃𝑃𝐴𝐴𝑀𝑀𝑃𝑃𝐴𝐴𝑃𝑃𝑃𝑃 ∈ NP

The following nondeterministic algorithm accepts in time 𝑂𝑂 𝑛𝑛3 , where 𝑛𝑛 = 𝐺𝐺, 𝑠𝑠, 𝑡𝑡 , adjacency matrix encoding

On input 𝐺𝐺,𝑠𝑠,𝑡𝑡 : (Vertices of 𝐺𝐺 are numbers 1,…,𝑘𝑘) 1. Nondeterministically guess a sequence

𝑐𝑐 , 𝑐𝑐 ,…,𝑐𝑐 of numbers 1,…,𝑘𝑘

12𝑘𝑘

2. Check that 𝑐𝑐 , 𝑐𝑐 ,…,𝑐𝑐 is a permutation: Every 12𝑘𝑘

number 1, … , 𝑘𝑘 appears exactly once 3.Checkthat𝑐𝑐 =𝑠𝑠,𝑐𝑐 =𝑡𝑡,andthereisanedge

fromevery𝑐𝑐 to𝑐𝑐

𝑖𝑖 𝑖𝑖+1

1𝑘𝑘

4. Accept if all checks pass, otherwise, reject.

4/8/2020 CS332 – Theory of Computation 27

An alternative characterization of NP “Languages with polynomial-time verifiers”

A verifier for a language 𝑅𝑅 is a deterministic algorithm 𝑉𝑉 such that 𝑤𝑤 ∈ 𝑅𝑅 iff there exists a string 𝑐𝑐 such that

𝑉𝑉( 𝑤𝑤, 𝑐𝑐 ) accepts

Runningtimeofaverifierisonlymeasuredintermsof 𝑤𝑤 𝑉𝑉 is a polynomial-time verifier if it runs in time polynomial

in|𝑤𝑤|oneveryinput 𝑤𝑤,𝑐𝑐

(Without loss of generality, |𝑐𝑐| is polynomial in |𝑤𝑤|, i.e.,

𝑐𝑐 = 𝑂𝑂(|𝑤𝑤|𝑘𝑘) for some constant 𝑘𝑘)

4/8/2020 CS332 – Theory of Computation 28

𝑃𝑃𝐴𝐴𝑀𝑀𝑃𝑃𝐴𝐴𝑃𝑃𝑃𝑃 has a polynomial-time verifier Certificate 𝑐𝑐:

Verifier 𝑉𝑉:

On input 𝐺𝐺,𝑠𝑠,𝑡𝑡,𝑐𝑐 : (Vertices of 𝐺𝐺 are numbers 1,…,𝑘𝑘)

1. Check that 𝑐𝑐1, 𝑐𝑐2, … , 𝑐𝑐𝑘𝑘 is a permutation: Every number 1, … , 𝑘𝑘 appears exactly once

2.Checkthat𝑐𝑐1 =𝑠𝑠,𝑐𝑐𝑘𝑘 =𝑡𝑡,andthereisanedge from every 𝑐𝑐𝑖𝑖 to 𝑐𝑐𝑖𝑖+1

3. Accept if all checks pass, otherwise, reject.

4/8/2020 CS332 – Theory of Computation 29

NP is the class of languages with polynomial- time verifiers

Theorem: A language 𝑅𝑅 ∈ NP iff there is a polynomial- time verifier for 𝑅𝑅

Proof:

4/8/2020 CS332 – Theory of Computation 30