NP-Completeness ‘n’ Such

Matthew Andres Moreno

direct complaints to: Dr. Josh Nahum

CSE 431 Fall 2021

PREVIOUSLY ON

Wait what????

​

• Intuition: reductions are not symmetric
• “Reduced to” at least as hard as “reduced from”

• P (polynomial problems) are “easy” (rice parable)
• NP Problems are easy to check
• Decision problems with certificates that can be verified in polynomial time
• Not all NP Problems are “hard”
• For example, “Does there exist a number larger than 42?”
• Technique: reductions via Subway & Olive Garden

​

​

​

(direct all complaints to Dr. Josh Nahum)

EPISODE 6: Meet 3 Sat

“a problem only a mother mathematician could love”

​

3 Sat: Boolean Notation Refresher

∨ => “OR”

∧ => “AND”

¬ => “NOT”

∈ => “CONTAINED

WITHIN”

x₁ => variable

​

^^ can be �“TRUE” or “FALSE”

3 Sat: Boolean Notation Refresher

x₁ ∨ (x₂ ∧ x₃)

x₁ = FALSE

x₂ = FALSE

x₂ = TRUE

3 Sat: Boolean Notation Refresher

x₁ ∨ (x₂ ∧ x₃)

x₁ = FALSE

x₂ = FALSE

x₂ = TRUE

What does this evaluate to?

3-Sat intuition: basically, “You Pick n”™℠®©

“CARBS”

“CAFFEINE”

“SUGAR”

3 items

3-Sat intuition: basically, “You Pick n”™℠®©

3 items

“Menu 0”

“Menu 1”

“Menu 2”

“Menu n”

...

item a

item b

item c

3-Sat intuition: basically, “You Pick n”™℠®©

3 items

“Menu 0”

“Menu 1”

“Menu 2”

“Menu n”

...

item a

item b

item c

How to solve & what runtime?

3-Sat intuition: “You Pick n”™℠®© => “Panera-SAT”

3 items

“Menu 0”

“Menu 1”

“Menu 2”

“Menu n”

...

item a

item b

item c

NOT

NOT

NOT

NOT

3-Sat intuition: “You Pick n”™℠®© => “Panera-SAT”

3 items

“Menu 0”

“Menu 1”

“Menu 2”

“Menu n”

...

item a

item b

item c

NOT

NOT

NOT

NOT

3-Sat intuition: “You Pick n”™℠®© => “Panera-SAT”

“Menu 0”

“Menu 1”

“Menu 2”

“Menu n”

item a

item b

item c

NOT

NOT

NOT

NOT

∧

∧

∧

∧

...

3-Sat intuition: “You Pick n”™℠®© => “Panera-SAT”

“Menu 0”

“Menu 1”

“Menu 2”

“Menu n”

item a

item b

item c

NOT

NOT

∧

∧

∧

∧

...

∨

∨

​

​

∨

∨

​

​

NOT

∨

∨

​

​

NOT

3-Sat, more formally

x₁

x₃

¬x₁

​

∨

∨

​

​

∨

∨

​

​

x₄

x₁

x₃

​

∨

∨

​

​

∨

∨

​

​

x₃

¬x₂

¬x₄

​

∧

∧

∧

...

∧

x₁

¬x₃

x₂

​

clause 1

clause 2

clause 3

clause n

3-Sat, even more formally

∨

∨

​

​

b₁

b₂

b₃

​

∨

∨

​

​

a₁

a₂

a₃

​

∨

∨

​

​

a_i, b_i, … ∈ {x₁,x₂, … ,x_m,¬x₁,¬x₂, … ,¬x_m}

∧

∧

∧

...

∧

c₁

c₂

c₃

​

n₁

n₂

n₃

​

∨

∨

​

​

clause 1

clause 2

clause 3

clause n

3-Sat is a Decision Problem

• Decision: Does a set of values x₁,x₂, … ,x_m exist such that the 3-Sat expression can be True?
• aka such that at least one statement within each clause is true

​

​

3-Sat is a Decision Problem

• Decision: Does a set of values x₁,x₂, … ,x_m exist such that the 3-Sat expression can be True?
• aka such that at least one statement within each clause is true

​

​

(x₁∨x₂∨x₃) ∧ (¬x₁∨¬x₂∨¬x₃)

Satisfiable?

3-Sat is a Decision Problem

• Decision: Does a set of values x₁,x₂, … ,x_m exist such that the 3-Sat expression can be True?
• aka such that at least one statement within each clause is true

​

​

(x₁∨x₁∨x₁) ∧ (¬x₁∨¬x₁∨¬x₁)

Satisfiable?

3-Sat is a Decision Problem

• Decision: Does a set of values x₁,x₂, … ,x_m exist such that the 3-Sat expression can be True?
• aka such that at least one statement within each clause is true

​

​

(x₁∨x₁∨x₁) ∧ (¬x₁∨¬x₁∨¬x₁)

Satisfiable?

3-Sat is a Decision Problem

• Decision: Does a set of values x₁,x₂, … ,x_m exist such that the 3-Sat expression can be True?
• aka such that at least one statement within each clause is true

​

​

What does a certificate look like for 3 sat?

3-Sat is a Decision Problem

• Decision: Does a set of values x₁,x₂, … ,x_m exist such that the 3-Sat expression can be True?
• aka such that at least one statement within each clause is true

​

​

How long does it take to verify a 3 sat certificate?

3-Sat is a Decision Problem

• Decision: Does a set of values x₁,x₂, … ,x_m exist such that the 3-Sat expression can be True?
• aka such that at least one statement within each clause is true

​

​

Is 3 sat a NP problem?

Why is 3-Sat Hard? https://math.stackexchange.com/a/1445847

Why is 3-Sat Hard? https://math.stackexchange.com/a/1445847

OR

Why is 3-Sat Hard? https://math.stackexchange.com/a/1445847

Why is 3-Sat Hard? https://math.stackexchange.com/a/1445847

✅ blue hand

✅ blue hand

✅ blue hand

Why is 3-Sat Hard? https://math.stackexchange.com/a/1445847

✅ blue hand

✅ blue hand

✅ blue hand

n bears, how many possibilities?

Why is 3-Sat Hard? https://math.stackexchange.com/a/1445847

Clause a

Clause b

Clause n

...

😭

😭

Why is 3-Sat Hard? https://math.stackexchange.com/a/1445847

Clause a

Clause b

Clause n

...

😭

😭

Why is 3-Sat Hard? https://math.stackexchange.com/a/1445847

x₁ x₂ x₃ …. x_m

¬ ¬ ¬ ¬

Clause a

Clause b

Clause n

...

EPISODE 6: Meet Integer Programming

“another problem only a mother mathematician could love”

​

ig: @marioparty

ig: @marioparty

Objective: Maximize

ig: @marioparty

Objective: Maximize

constraint :’(

ig: @marioparty

decision problem

constraint :’(

Objective: Maximize

ig: @marioparty

decision problem

constraint :’(

Objective: Maximize

Skrt skrt

ig: @marioparty

decision problem

constraint :’(

Objective: Maximize

Constraint

x ≥ 1

y ≥ 0

x + y ≤ 3

Objective

2y

Threshold

3

x and y must be integers, constraints must be ≤ or ≥

ig: @marioparty

decision problem

constraint :’(

Objective: Maximize

Constraint

x ≥ 1

y ≥ 0

x + y ≤ 3

Objective

2y

Threshold

3

x and y must be integers

Mario Brah’s chomped?

ig: @marioparty

decision problem

constraint :’(

Objective: Maximize

Constraint

x ≥ 1

y ≥ 0

x + y ≤ 3

Objective

2y

Threshold

3

x and y must be integers

What is the certificate?

ig: @marioparty

decision problem

constraint :’(

Objective: Maximize

Constraint

x ≥ 1

y ≥ 0

x + y ≤ 3

Objective

2y

Threshold

3

x and y must be integers

Runtime to verify?

ig: @marioparty

decision problem

constraint :’(

Objective: Maximize

Constraint

x ≥ 1

y ≥ 0

x + y ≤ 3

Objective

2y

Threshold

3

x and y must be integers

Integer programming in NP?

Why is integer programming hard?

EPISODE 6: In Which (To No One’s Surprise) We Reduce 3 Sat to Integer Programming

Next Up: Someting More Hardcore

Integer Programming=>

Reduction

In

Return

Conversion

Out

3 Sat =>

Next Up: Someting More Hardcore

Step 1: Converting Booleans to Integers

• Use 0 for “FALSE” and 1 for “TRUE”
• Allow integer variables to only be 0 or 1

​

• constraint: 0 ≤ v_i ≤ 1

Step 1: Converting Booleans to Integers

Use 0 for “FALSE” and 1 for “TRUE”

Allow integer variables to only be 0 or 1

What two constraints on v_i?

Step 1: Converting Booleans to Integers

• Use 0 for “FALSE” and 1 for “TRUE”
• Allow integer variables to only be 0 or 1

​

• constraint: 0 ≤ v_i ≤ 1

​

Step 2: How to Represent Negation?

• We have variables v_i but we also need ¬v_i’s
• Idea: for each v_i make a corresponding u_i
• u_i represents ¬v_i
• Need exactly one of u_i and v_i to be “TRUE”
• Constraint: u_i + v_i = 1

Step 2: How to Represent Negation?

• We have variables v_i but we also need ¬v_i’s
• Idea: for each v_i make a corresponding u_i
• u_i represents ¬v_i
• Need exactly one of u_i and v_i to be “TRUE”
• Constraint: u_i + v_i = 1

How to represent constraint w/ ≤ and ≥?

Step 2: How to Represent Negation?

• We have variables v_i but we also need ¬v_i’s
• Idea: for each v_i make a corresponding u_i
• u_i represents ¬v_i
• Need exactly one of u_i and v_i to be “TRUE”
• Constraint: 1 ≤ u_i + v_i ≤ 1

Step 3: Enforcing Clause Satisfaction

• Example Clause C: (v₁∨¬v₂∨v₃)
• Each clause needs at least one “TRUE”

Step 3: Enforcing Clause Satisfaction

• Example Clause C: (v₁∨¬v₂∨v₃)
• Each clause needs at least one “TRUE”

How to enforce at least one “TRUE” in integer programming analog?

Step 3: Enforcing Clause Satisfaction

• Example Clause C: (v₁∨¬v₂∨v₃)
• Each clause needs at least one “TRUE”
• Integer Programming constraint:

​

v₁+u₂+v₃ ≥ 1

Step 3: Enforcing Clause Satisfaction

• Example Clause C: (v₁∨¬v₂∨v₃)
• Each clause needs at least one “TRUE”
• Integer Programming constraint:

​

c₁+c₂+c₃ ≥ 1

Step 4: ∧’s between clauses?

• Example Clause C_i: (v₁∨¬v₂∨v₃) ✅

​

• 3SAT: C₁ ∧ C₂∧ … ∧C_n

Step 4: ∧’s between clauses?

• Example Clause C_i: (v₁∨¬v₂∨v₃) ✅

​

• 3SAT: C₁ ∧ C₂∧ … ∧C_n

Is 3SAT solved?

Constraint

0 ≤ v_i ≤ 1

​

Constraint

0 ≤ v_i ≤ 1

1 ≤ u_i + v_i ≤ 1

​

Constraint

0 ≤ v_i ≤ 1

​

1 ≤ u_i + v_i ≤ 1

​

c₁+c₂+c₃≥ 1

Constraint

0 ≤ v_i ≤ 1

​

1 ≤ u_i + v_i ≤ 1

​

c₁+c₂+c₃≥ 1

​

Objective

​

doesn’t matter

Threshold

​

doesn’t matter

if satisfied, then 3SAT satisfied

Constraint

0 ≤ v_i ≤ 1

1 ≤ u_i + v_i ≤ 1

c₁+c₂+c₃≥ 1

Objective

​

doesn’t matter

Threshold

​

doesn’t matter

there’s no chance chain chomp can get Mario if it can’t satisfy constraints…

if satisfied, then 3SAT satisfied

Constraint

0 ≤ v_i ≤ 1

1 ≤ u_i + v_i ≤ 1

c₁+c₂+c₃≥ 1

Objective

​

42

Threshold

​

42

there’s no chance Chain Chomp can get Mario if it can’t satisfy constraints…

if Chain Chomp satisfies constraints let it get Mario automatically.

if satisfied, then 3SAT satisfied

Integer Programming=>

Reduction

In

Return

Conversion

Out

3 Sat =>

Integer Programming=>

Reduction

In

Return

Conversion

Out

3 Sat =>

What does this tell us about integer programming relative to 3 SAT?

EPISODE 6: Cook-Levin Theorem

Every problem in NP is just SAT in disguise

No problem in NP is harder than SAT

Every problem in NP is just SAT in disguise

Cook-Levin Theorem

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

*bonk

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

yeeeeees

Cook-Levin Theorem (Hurr Durr Edition)

*bonk

:( :( :(

NP

home

work

:( :( :(

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

Mr. Baxter

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

Mr. Baxter

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

but

mooooooooooooom

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

that’ll take

exponential time :( :(

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

~~ skreert

vroooom

vroom

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

An answer that will open the lock

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

p

o

p

An answer that will open the lock

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

p

o

p

An answer that will open the lock

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

p

o

p

An answer that will open the lock

What else did Doge Jr. just find???

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

p

o

p

ANY ANSWER THAT OPENS THE LOCK IS ALSO AN ANSWER TO THE NP HOMEWORK!!!!!!!

An answer that will open the lock

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

instead of solving the NP problem, Doge Jr. can inspect the lock’s mechanism

&

reverse engineer a correct solution that will open the lock

p

o

p

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

any problem in NP

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

any problem in NP

its polynomial time verifier

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

any problem in NP

its polynomial time verifier

certificate

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

any problem in NP

its polynomial time verifier

certificate

(opens for correct certificates)

…

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

any problem in NP

its polynomial time verifier

certificate

(opens for correct certificates)

SAT!?!?!!!1!

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

any problem in NP

its polynomial time verifier

certificate

(opens for correct certificates)

SAT!?!?!!!1!

Hence, solving SAT can “unlock” any NP problem

Cook-Levin Theorem (Hurr Durr Edition)

one small detail, how big of a SAT?

SAT

Cook-Levin Theorem (Hurr Durr Edition)

one small detail, how big of a SAT?

SAT

SAT

??????

VS.

??????

Cook-Levin Theorem (Hurr Durr Edition)

one small detail, how big of a SAT?

SAT

SAT size in P

SAT

SAT size bigger than P

??????

VS.

??????

Cook-Levin Theorem (Hurr Durr Edition)

polynomial

verifier

Cook-Levin Theorem (Hurr Durr Edition)

n^k time

polynomial

verifier

Cook-Levin Theorem (Hurr Durr Edition)

n^k time

n^k memory

polynomial

verifier

Cook-Levin Theorem (Hurr Durr Edition)

n^k time

n^k memory

. STATE at Time 0 .

polynomial

verifier

Cook-Levin Theorem (Hurr Durr Edition)

n^k time

n^k memory

OR!

AND!

. STATE at Time 0 .

polynomial

verifier

Cook-Levin Theorem (Hurr Durr Edition)

n^k time

n^k memory

OR!

AND!

. STATE at Time 0 .

polynomial

verifier

NOT!

STATE at Time 0

. STATE at Time 1 .

Cook-Levin Theorem (Hurr Durr Edition)

n^k time

n^k memory

OR!

AND!

. STATE at Time 0 .

polynomial

verifier

NOT!

STATE at Time 0

. STATE at Time 1 .

OR!

AND!

NOT!

OR!

AND!

NOT!

. STATE at Time 2 .

…

Cook-Levin Theorem (Hurr Durr Edition)

n^k time

n^k memory

OR!

AND!

. STATE at Time 0 .

polynomial

verifier

NOT!

STATE at Time 0

. STATE at Time 1 .

OR!

AND!

NOT!

OR!

AND!

NOT!

. STATE at Time 2 .

…

OR!

AND!

NOT!

. STATE at Time n^k .

Cook-Levin Theorem (Hurr Durr Edition)

n^k time

n^k memory

OR!

AND!

. STATE at Time 0 .

polynomial

verifier

NOT!

STATE at Time 0

. STATE at Time 1 .

OR!

AND!

NOT!

OR!

AND!

NOT!

. STATE at Time 2 .

…

OR!

AND!

NOT!

. STATE at Time n^k .

~ n^k x n^k OR’s AND’s & NOT’S

Cook-Levin Theorem (Hurr Durr Edition)

n^k time

n^k memory

OR!

AND!

. STATE at Time 0 .

polynomial

verifier

NOT!

STATE at Time 0

. STATE at Time 1 .

OR!

AND!

NOT!

OR!

AND!

NOT!

. STATE at Time 2 .

…

OR!

AND!

NOT!

. STATE at Time n^k .

~ n^k x n^k OR’s AND’s & NOT’S

~ n^2k OR’s AND’s & NOT’S

Cook-Levin Theorem (Hurr Durr Edition)

n^k time

n^k memory

OR!

AND!

. STATE at Time 0 .

polynomial

verifier

NOT!

STATE at Time 0

. STATE at Time 1 .

OR!

AND!

NOT!

OR!

AND!

NOT!

. STATE at Time 2 .

…

OR!

AND!

NOT!

. STATE at Time n^k .

~ n^k x n^k OR’s AND’s & NOT’S

~ n^2k OR’s AND’s & NOT’S

n^2k still polynomial…

so we have a reasonable sized SAT lock mechanism!

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

p

o

p

instead of solving the NP problem, Doge Jr. can inspect the lock’s mechanism

&

reverse engineer a correct SAT solution that will open the lock

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

p

o

p

* oh and the SAT mechanism isn’t redic big

instead of solving the NP problem, Doge Jr. can inspect the lock’s mechanism

&

reverse engineer a correct SAT solution that will open the lock*

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

p

o

p

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

p

o

p

No problem in NP is harder than SAT

​

​

Cook-Levin Theorem (Hurr Durr Edition)

:( :( :(

NP

home

work

:( :( :(

p

o

p

No problem in NP is harder than SAT

​

(because we can just reverse engineer the

verifier instead of doing our NP homework)

EPISODE 6: NP Completeness

NP

. SAT .

Cook-levin theorem

NP

. SAT .

Cook-levin theorem

No problem in NP is harder than SAT

The Adventures of Reduction-Doo

The Adventures of Reduction-Doo

… and many more!

The Adventures of Reduction-Doo

… and many more!

AT LEAST

AS HARD AS SAT

AT LEAST

AS HARD AS SAT

AT LEAST

AS HARD AS SAT

​

monkeys

in a barrel

reductions

monkeys

in a barrel

NP

. SAT .

🤠

NP

. SAT .

REDUCTION

🤠

NP

. SAT .

REDUCTION

🤠

NP

. SAT .

REDUCTION

NP

. SAT .

REDUCTION

NP

. SAT .

NP-Complete

REDUCTION

NP

. SAT .

NP-Complete

REDUCTION

NP

. SAT .

🤠

NP-Complete

😴

😳

NP

. SAT .

🤠

NP-Complete

😴

😳

P

NP

. SAT .

🤠

NP-Complete

😴

😳

P

0w0-TIME

NP

. SAT .

🤠

NP-Complete

😴

😳

P

0w0-TIME

SORTING

NP

. SAT .

🤠

NP-Complete

😴

😳

P

0w0-TIME

SORTING

NP

. SAT .

🤠

NP-Complete

😴

😳

P

0w0-TIME

BEST CHESS MOVE

SORTING

NP

. 3 SAT .

🤠

NP-Complete

😴

😳

P

0w0-TIME

SORTING

CHESS

NP

. SAT .

🤠

NP-Complete

😴

😳

P

0w0-TIME

SORTING

CHESS

INTEGER PROGRAMMING

NP

. SAT .

🤠

NP-Complete

😴

😳

P

0w0-TIME

SORTING

CHESS

INT PROGRAM

NP

. SAT .

🤠

NP-Complete

😴

😳

P

0w0-TIME

SORTING

CHESS

INT PROGRAM

SHORTEST GRAPH PATH

​

(DJIEKSTRA)

NP

. SAT .

🤠

NP-Complete

😴

😳

P

0w0-TIME

SORTING

CHESS

INT PROGRAM

DJIEKSTRA’S

Last Piece of Vocab:

Last Piece of Vocab:

NP-Complete

+

0w0-TIME

Last Piece of Vocab:

NP-Complete

+

0w0-TIME

=

NP-HARD

​

NP-HARD

NP-HARD

How to Prove Something’s NP-Complete

NP-HARD

How to Prove Something’s NP-Complete

NP-HARD

• Attach monkey

How to Prove Something’s NP-Complete

NP-HARD

• Attach monkey

=> NP-HARD

How to Prove Something’s NP-Complete

NP-HARD

• Attach monkey

=> NP-HARD

How to Prove Something’s NP-Complete

NP-HARD

• Attach monkey

=> NP-HARD

What else?

How to Prove Something’s NP-Complete

NP-HARD

• Attach monkey

=> NP-HARD

How to Prove Something’s NP-Complete

NP-HARD

• Attach monkey

=> NP-HARD

Our monkey could be in 0w0-TIME !!!!!

How to Prove Something’s NP-Complete

NP-HARD

• Attach monkey

=> NP-HARD

2. Polynomial Certificate Checker

How to Prove Something’s NP-Complete

NP-HARD

• Attach monkey

=> NP-HARD

=> in NP

2. Polynomial Certificate Checker

EPISODE 7: P ?= NP

NP

. 3 SAT .

🤠

NP-Complete

😴

😳

P

0w0-TIME

NP

. 3 SAT .

🤠

NP-Complete

😴

😳

P

0w0-TIME

NP

. 3 SAT .

🤠

NP-Complete

😴

😳

P

0w0-TIME

NP

. 3 SAT .

🤠

NP-Complete

😴

😳

P

0w0-TIME

NP

. 3 SAT .

🤠

NP-Complete

😴

😳

P

0w0-TIME

What does this mean about sat?

Reduction

In

Return

Conversion

Out

Sat =>

in P

Solvable in Polynomial Time=>

Reduction

In

Return

Conversion

Out

Sat =>

in P

Solvable in Polynomial Time=>

Reduction

In

Return

Conversion

Out

Sat =>

in P

Solvable in Polynomial Time=>

Solvable in Polynomial Time=>

Reduction

In

Return

Conversion

Out

Sat =>

in P

Solvable in Polynomial Time=>

Solvable in Polynomial Time=>

Reduction

In

Return

Conversion

Out

Sat =>

in P

Solvable in Polynomial Time=>

Solvable in Polynomial Time=>

Reduction

In

Return

Conversion

Out

Sat =>

in P

Solvable in Polynomial Time=>

Why is there a flaming 0w0 on this slide?

Solvable in Polynomial Time=>

Reduction

In

Return

Conversion

Out

Sat =>

in P

Solvable in Polynomial Time=>

Why is there a flaming 0w0 on this slide?

Cook-levin theorem

No problem in NP is harder than SAT

Cook-levin theorem

No problem in NP is harder than SAT

Sat is solvable in polynomial time

Cook-levin theorem

Sat is solvable in polynomial time

all of NP is solvable in polynomial time

No problem in NP is harder than SAT

Solvable in Polynomial Time=>

Reduction

in P

all of NP is solvable in polynomial time

Solvable in Polynomial Time=>

Reduction

in P

all of NP is solvable in polynomial time

P = NP

Solvable in Polynomial Time=>

Reduction

in P

all of NP is solvable in polynomial time

P = NP

Solvable in Polynomial Time=>

Reduction

in P

all of NP is solvable in polynomial time

P = NP

Solvable in Polynomial Time=>

Reduction

in P

P = NP -> all of NP is no longer hopelessly hard

1 MILLION DOLLARS

CURE CANCER

BREAK ENCRYPTION

BEAT CANDY CRUSH

etc etc

(or maybe

not)

P ?= NP

????????????????????????????????????????????????????????????????????????????

Does verifiable polynomial time imply solvable in polynomial time?

​

If P=NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it's found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss; everyone who could recognize a good investment strategy would be Warren Buffett.

– Scott Aaronson – Michael Scott

​

Wait what????

• 3SAT is like “Panera You Pick n”
• Integer programming is like Chain Chomp
• We reduced 3SAT to integer programming
• Integer programming is at least as hard as 3SAT
• Cook Levin Theorem
• Doge Jr. using SAT to reverse engineer the lock to any NP problem
• No problem is harder than just picking its SAT lock
• NP-Complete
• Using a barrel of reductions from SAT to other problems
• P?=NP
• Reducing any NP-Complete problem to polynomial time reduces all NP-Complete problems
• Does verifiable polynomial time imply solvable in polynomial time?