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

BU CS 332 – Theory of Computation

Lecture 21:

• NP‐Completeness

• Cook‐Levin Theorem • Reductions

Reading:

Sipser Ch 7.3‐7.5

Mark Bun April 15, 2020

Last time: Two equivalent definitions of

1) is the class of languages decidable in polynomial time on a nondeterministic TM

2) A polynomial‐time verifier for a language is a

deterministic

iff there exists a string

‐time algorithm such that such that accepts

Theorem: A language verifier for

iff there is a polynomial‐time

4/15/2020

CS332 ‐ Theory of Computation 2

Examples of languages: SAT

“Is there an assignment to the variables in a logical

formula that make it evaluate to ?”

• Boolean variable: Variable that can take on the value / (encoded as 0/1)

• Boolean operations:

• Boolean formula: Expression made of Boolean variables

and operations. Ex:

• 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/15/2020 CS332 ‐ Theory of Computation 3

Examples of

languages: SAT

Ex: Ex:

Satisfiable? Satisfiable?

Claim:

4/15/2020

CS332 ‐ Theory of Computation

4

Examples of languages: TSP

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

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

More precisely: Given

• A number of cities

• A function giving the distance between each pair of cities

• A distance bound

4/15/2020 CS332 ‐ Theory of Computation 5

EXP

NP

EXP

vs.

Question: Does ?

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

A central problem in mathematics and computer science

P

P = NP

If PNP 4/15/2020

If P=NP

CS332 ‐ Theory of Computation 6

A world where

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

A world where

• 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:

4/15/2020 CS332 ‐ Theory of Computation

8

NP‐Completeness

4/15/2020 CS332 ‐ Theory of Computation 9

What about a world where

Believe this to be true, but very far from proving it

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

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

Idea: Identify the “hardest” problems in NP Find such that iff

4/15/2020 CS332 ‐ Theory of Computation 10

Recall: Mapping reducibility

Definition:

A function ∗ ∗ is computable if there is a TM which, given as input any ∗, halts with only on its tape.

Definition:

Language is mapping reducible to language , written

if there is a computable function such that for all strings ∗, we have

∗∗

4/15/2020 CS332 ‐ Theory of Computation 11

Polynomial‐time reducibility

Definition:

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:

Language is polynomial‐time reducible to language

,

written

if there is a polynomial‐time computable function

such that for all strings ∗, we have 4/15/2020 CS332 ‐ Theory of Computation

12

∗∗

Implications of poly‐time reducibility

Theorem: If

and then

Proof: Let decide in poly time:

in poly time, and let be a poly‐ time reduction from to . The following TM decides

4/15/2020

CS332 ‐ Theory of Computation 13

NP‐completeness

Definition: A language is NP‐complete if 1) and

4/15/2020

CS332 ‐ Theory of Computation 14

2) Every language is poly‐time reducible to , i.e., (“ is NP‐hard”)

Implications of NP‐completeness

Theorem: Suppose Then

is NP‐complete. iff

Proof:

4/15/2020

CS332 ‐ Theory of Computation 15

Implications of NP‐completeness

Theorem: Suppose Then

is NP‐complete. iff

Consequences of

being NP‐complete:

1) 2) 3)

If you want to show If you want to show If you already believe

, you just have to show , you just have to show

4/15/2020 CS332 ‐ Theory of Computation 16

, then you believe

Cook‐Levin Theorem and NP‐Complete Problems

4/15/2020 CS332 ‐ Theory of Computation 17

Cook‐Levin Theorem

Theorem: (Boolean satisfiability) is NP‐complete Proof: Already know . Need to show every

problem in reduces to (later?)

Stephen A. Cook (1971)

Leonid Levin (1973)

4/15/2020 CS332 ‐ Theory of Computation

18

New NP‐complete problems from old

Lemma: If and , then (poly‐time reducibility is transitive)

Theorem: If language , then

and for some NP‐complete is also NP‐complete

4/15/2020

CS332 ‐ Theory of Computation 19

New NP‐complete problems from old

All problems below are NP‐complete and hence poly‐time reduce to one another!

4/15/2020

CS332 ‐ Theory of Computation

20

INDEPENDENT SET

DIR-HAM-CYCLE

GRAPH 3-COLOR

SUBSET-SUM

VERTEX COVER

HAM-CYCLE

PLANAR 3-COLOR

SCHEDULING

SET COVER

TSP

SAT 3SAT

by definition of NP‐completeness

(3‐CNF Satisfiability)

Definition(s):

• A literal either a variable of its negation ,

• A clause is a disjunction (OR) of literals Ex.

• A 3‐CNF is a conjunction (AND) of clauses where each

clause contains exactly 3 literals Ex. …

4/15/2020 CS332 ‐ Theory of Computation 21

is NP‐complete

Theorem: is NP‐complete Proof idea: 1) is in NP (why?)

2) Show that

Idea of reduction: Given a poly‐time algorithm converting an arbitrary formula into a 3CNF such that is satisfiable iff is satisfiable

4/15/2020 CS332 ‐ Theory of Computation

22