# CS代考计算机代写 AI 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

Mark Bun April 13, 2020

Goals of complexity theory

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

P ≈ Decision problems which can be solved efficiently

Can we exhibit general classes of problems which are either in

P or provably not in P?

Some problems provably require exponential time! (Chapter 9)

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

4/13/2020 CS332 – Theory of Computation 2

Nondeterministic Time and NP

4/13/2020 CS332 – Theory of Computation 3

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

Deterministic vs. nondeterministic time

Deterministic

Nondeterministic

𝒕𝒕(𝒏𝒏)

reject

accept

accept

accept or reject

reject

reject

4/13/2020

CS332 – Theory of Computation

5

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

CS332 – Theory of Computation 6

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

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 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/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𝑓𝑓∶ 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/13/2020 CS332 – Theory of Computation 10

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

Complexity class NP

Definition: NP is the class of languages decidable in

polynomial time on a nondeterministic TM

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

4/13/2020 CS332 – Theory of Computation 12

Hamiltonian Path

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

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

𝑠𝑠𝑡𝑡

4/13/2020 CS332 – Theory of Computation 13

𝐻𝐻𝐴𝐴𝑀𝑀𝐻𝐻𝐴𝐴𝐻𝐻𝐻𝐻 ∈ NP

The following nondeterministic algorithm accepts in time 𝑂𝑂 𝑛𝑛1.5 , 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/13/2020 CS332 – Theory of Computation 14

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

𝐻𝐻𝐴𝐴𝑀𝑀𝐻𝐻𝐴𝐴𝐻𝐻𝐻𝐻 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/13/2020 CS332 – Theory of Computation 16

NP is the class of languages with polynomial- time verifiers

Theorem: A language 𝐿𝐿 ∈ NP 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

Examples of NP languages: SAT

“Is there an assignment to the variables in a logical

formula that make it evaluate to true?”

• Boolean variable: Variable that can take on the value

true/false (encoded as 0/1)

• Boolean operations: ∧ AND , ∨ OR , ¬ (NOT)

• Boolean formula: Expression made of Boolean variables and operations. Ex: (𝑥𝑥 ∨ 𝑥𝑥 ) ∧ 𝑥𝑥

123

• An assignment of 0s and 1s to the variables satisfies a formula 𝜑𝜑 if it makes the formula evaluate to 1

• A formula 𝜑𝜑 is satisfiable if there exists an assignment that satisfies it

4/13/2020 CS332 – Theory of Computation 19

Examples of NP languages: SAT

Ex: (𝑥𝑥1 ∨ 𝑥𝑥2) ∧ 𝑥𝑥3 Satisfiable?

Ex: (𝑥𝑥1 ∨ 𝑥𝑥2) ∧ (𝑥𝑥1 ∨ 𝑥𝑥2) ∧ 𝑥𝑥2 Satisfiable? 𝑆𝑆𝐴𝐴𝐻𝐻 = { 𝜑𝜑 |𝜑𝜑 is a satisfiable formula}

Claim: 𝑆𝑆𝐴𝐴𝐻𝐻 ∈ NP

4/13/2020 CS332 – Theory of Computation 20

Examples of NP languages: TSP

“Given a list of cities and distances between them, is

there a ‘short’ tour of all of the cities?”

• A number of cities 𝑚𝑚

More precisely: Given

• A function 𝐷𝐷: {1, … , 𝑚𝑚} 2 → N giving the distance between each pair of cities

• A distance bound 𝐵𝐵

𝐻𝐻𝑆𝑆𝐻𝐻 = { 𝑚𝑚, 𝐷𝐷, 𝐵𝐵 |∃ a tour visiting every city

with length ≤ 𝐵𝐵}

4/13/2020 CS332 – Theory of Computation 21

P vs. NP

Question: Does P = NP?

Philosophically: Can every problem with an efficiently verifiable solution also be solved efficiently?

A central problem in mathematics and computer science

EXP

NP

EXP

P

P = NP

If P=NP

If P≠NP 4/13/2020

CS332 – Theory of Computation 22

A world where P = NP

• Many important decision problems can be solved in

polynomial time (𝐻𝐻𝐴𝐴𝑀𝑀𝐻𝐻𝐴𝐴𝐻𝐻𝐻𝐻, 𝑆𝑆𝐴𝐴𝐻𝐻, 𝐻𝐻𝑆𝑆𝐻𝐻, etc.)

• Many search problems can be solved in polynomial time

(e.g., given a natural number, find a prime factorization)

• Many optimization problems can be solved in polynomial time (e.g., find the lowest energy conformation of a protein)

4/13/2020 CS332 – Theory of Computation 23

A world where P = NP

• Secure cryptography becomes impossible

An NP search problem: Given a ciphertext 𝐶𝐶, find a plaintext 𝑚𝑚 and encryption key 𝑘𝑘 that would encrypt to 𝐶𝐶

• AI / machine learning become easy: Identifying a consistent classification rule is an NP search problem

• Finding mathematical proofs becomes easy: NP search problem: Given a mathematical statement 𝑆𝑆 and length bound 𝑘𝑘, is there a proof of 𝑆𝑆 with length at most 𝑘𝑘?

General consensus: P ≠ NP

4/13/2020 CS332 – Theory of Computation 24

NP Completeness

4/13/2020 CS332 – Theory of Computation 25

What about a world where P ≠ NP Believe this to be true, but very far from proving it

P ≠ NP implies that there is a problem in NP which cannot be solved in polynomial time, but it might not be a useful one

Question: What would P ≠ NP allow us to conclude about problems we care about?

Idea: Identify the “hardest” problems in NP Find𝐿𝐿∈NPsuchthat𝐿𝐿∈P iff P=NP

4/13/2020 CS332 – Theory of Computation 26

Recall: Mapping reducibility

A function 𝑓𝑓: Σ∗ → Σ∗ is computable if there is a TM 𝑀𝑀 which, given as input any 𝑤𝑤 ∈ Σ∗, halts with only 𝑓𝑓(𝑤𝑤) on its tape.

Definition:

Definition:

Language 𝐴𝐴 is mapping reducible to language 𝐵𝐵, written

𝐴𝐴 ≤m 𝐵𝐵

if there is a computable function 𝑓𝑓: Σ∗ → Σ∗ such that for

all strings 𝑤𝑤 ∈ Σ∗, we have 𝑤𝑤 ∈ 𝐴𝐴 ⟺ 𝑓𝑓(𝑤𝑤) ∈ 𝐵𝐵

4/13/2020 CS332 – Theory of Computation 27

Polynomial-time reducibility

A function 𝑓𝑓: Σ∗ → Σ∗ is polynomial-time computable if there is a polynomial-time TM 𝑀𝑀 which, given as input any 𝑤𝑤 ∈ Σ∗, halts with only 𝑓𝑓(𝑤𝑤) on its tape.

Definition:

Definition:

Language 𝐴𝐴 is polynomial-time mapping reducible to

language 𝐵𝐵, written

if there is a polynomial-time computable function 𝑓𝑓: Σ∗ → Σ∗

𝐴𝐴 ≤p 𝐵𝐵

such that for all strings 𝑤𝑤 ∈ Σ∗, we have 𝑤𝑤 ∈ 𝐴𝐴 ⟺ 𝑓𝑓(𝑤𝑤) ∈ 𝐵𝐵 4/13/2020 CS332 – Theory of Computation 28

Implications of poly-time reducibility

Theorem:If𝐴𝐴≤p 𝐵𝐵and𝐵𝐵∈𝐻𝐻,then𝐴𝐴∈𝐻𝐻 Proof:

4/13/2020 CS332 – Theory of Computation 29