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

BU CS 332 – Theory of Computation

Lecture 20:

• More on NP

Reading:

Sipser Ch 7.3‐7.5

• P vs. NP

Mark Bun April 13, 2020

Goals of complexity theory

Ultimate goal: Classify problems according to their feasibility and inherent computational difficulty

Decision problems which can be solved efficiently

Can we exhibit general classes of problems which are either in or provably not in ?

Some problems provably require exponential time! (Chapter 9)

: A fundamental and practically important class of problems which have defied classification, but nevertheless exhibits important structure ( completeness)

4/13/2020 CS332 ‐ Theory of Computation 2

Nondeterministic Time and NP

4/13/2020 CS332 ‐ Theory of Computation 3

Nondeterministic time

Let

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

,

computational branch

4/13/2020 CS332 ‐ Theory of Computation

4

Deterministic vs. nondeterministic time

Deterministic

Nondeterministic

accept or reject

reject reject

4/13/2020

CS332 ‐ Theory of Computation

5

𝒕𝒏

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/13/2020

CS332 ‐ Theory of Computation 6

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/13/2020 CS332 ‐ Theory of Computation

7

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/13/2020 CS332 ‐ Theory of Computation 8

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/13/2020 CS332 ‐ Theory of Computation 9

Nondeterministic time

Let

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

computational branch

1) Decides , and 2) Runs in time

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

A language if there exists an NTM that

4/13/2020 CS332 ‐ Theory of Computation 10

NTIME explicitly

A language if there exists an NTM

such that, on every input

∗

1. 2. 3.

Every computational branch of halts in either the accept or reject state within steps

iff there exists an accepting computational branch of on input

input

iff every computational branch of rejects on (or dies with no applicable transitions)

4/13/2020

CS332 ‐ Theory of Computation 11

Complexity class

Definition: is the class of languages decidable in polynomial time on a nondeterministic TM

4/13/2020

CS332 ‐ Theory of Computation 12

Hamiltonian Path

4/13/2020 CS332 ‐ Theory of Computation 13

The following nondeterministic algorithm accepts in time

.

, where , adjacency matrix encoding

On input : (Vertices of are numbers ) 1. Nondeterministically guess a sequence

of numbers

2. Check that number

is a permutation: Every appears exactly once

3.Checkthat

, ,andthereisanedge from every to

4. Accept if all checks pass, otherwise, reject. 4/13/2020 CS332 ‐ Theory of Computation 14

An alternative characterization of

“Languages with polynomial‐time verifiers”

A verifier for a language is a deterministic algorithm such that iff there exists a string such that

accepts

Running time of a verifier is only measured in terms of

is a polynomial‐time verifier if it runs in time polynomial in on every input

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

4/13/2020

CS332 ‐ Theory of Computation 15

for some constant )

Certificate :

1. Check that number

is a permutation: Every appears exactly once

2.Checkthat

has a polynomial‐time verifier

Verifier :

On input : (Vertices of are numbers )

, ,andthereisanedge from every to

3. Accept if all checks pass, otherwise, reject. 4/13/2020 CS332 ‐ Theory of Computation 16

NP is the class of languages with polynomial‐ time verifiers

Theorem: A language iff there is a polynomial‐ time verifier for

Proof:

4/13/2020 CS332 ‐ Theory of Computation 17

4/13/2020 CS332 ‐ Theory of Computation 18