Lecture 25: P vs NP

CSE 373: Data Structures and Algorithms

1

CSE 373 24WI

CSE 373 24WI

1

Warm Up

Suppose I have two algorithms, one that runs in O(n³) and the other that runs in O(2ⁿ) time. Based on the following times, how long do you expect it to take the second algorithm to run on n=100

Algorithm 1 O(n³):

• n=10, ~1 sec
• n=100, ~17 min

​

Algorithm 2 O(2ⁿ):

• n=10, ~1 sec
• n=100, ???

Answer the Warm Up:

pollev.com/hschafer

​

​

​

​

​

​

CSE 373 24WI

2

P vs. NP

P vs NP Explained (YouTube)

CSE 373 24WI

3

A brief history of computer science problem solving

• The field of “computer science” is the pursuit of determining how to use “computers” to help solve human problems

• 1843 the first “computer” is designed to solve Bernoulli's numbers, a very difficult calculation

Charles Babbage’s Analytical Engine designed in 1837

• 1943 the MARC II is designed to solve missile trajectory and other military calculations

• 1960s computers begin to become more generalized, researchers start looking for ways to use computers beyond basic math computations

• 1970s researchers are exploring what types of problems computers can help with, and finding themselves stuck and unsure if there exists a computer assisted solution or not…

Harvard MARC II - and the invention of the “bug”

Douglas Engelbart gives the “mother of all demos” 1968 and simultaneously invents the mouse, windows, hypertext, graphics, video conferencing and more

The Apple II is released in 1978, the first commercially successful personal computer (invented by Steve Wozniak in 1976)

CSE 373 24WI

4

1970s computer science research

• Researchers were collecting problems to solve
• Some problems resulted in algorithms that could “efficiently” find a solution
• When researchers were stuck on a problem they turned to “reductions” to see if they could apply a newly discovered algorithm to their own problem
• To help one another understand if they were working on an unsolved problem or not researchers started to categorize problems into complexity classes…
• Enter “complexity research”

* Computers and Intractability was published in 1979 it contained all known problems that reduced to one another. In 2006 it was found to be the most cited publication in computer science ever

CSE 373 24WI

5

“Efficiency”

So far you’ve only met problems that have an “efficient” solution

For our purposes “efficient” essentially means “can be executed by current day computers”

Formally we will consider any code that can run in polynomial or “P” time to be “efficient”

Are these algorithms always actually efficient?

Well… no

Your n¹⁰⁰⁰⁰ algorithm or 10000n³ algorithms probably aren’t going to finish anytime soon, but these edge cases are rare, and polynomial time is good as a low bar

CSE 373 24WI

6

“Efficiency” at scale

We have seen some inefficient algorithms

• Recursive backtracking (kⁿ where k represents number of choices)
• Recursive fibonacci (2ⁿ)

But as long as n is small we can still compute them

N³ solution where n= 100 takes ~3 hrs

2ⁿ solution where n = 10 takes ~milliseconds,

but 2ⁿ when n = 100 takes 300 quintillion years (longer than the age of the universe)

CSE 373 24WI

7

Running Times

Table from Rosen’s Discrete Mathematics textbook

How big of a problem can we solve for an algorithm with the given running times?

“*” means more than 10¹⁰⁰ years.

CSE 373 24WI

8

Aside: Decision Problems

Today’s goal is to break problems into solvable/not solvable categories

For today, we’re going to talk about decision problems.

• Problems that have a “yes” or “no” answer.

Why?

Theory reasons / how we translate problems for computer understanding

But it’s not too bad

• most problems can be rephrased as very similar decision problems

E.g. instead of “find the shortest path from s to t” ask,

• Is there a path from s to t length at most k?

CSE 373 24WI

9

NP Complexity Class

2-Coloring:

Can you color vertices of a graph red and blue so every edge has differently colored endpoints?

2-SAT:

Given a set of variables and a list of requirements:

(variable==[T/F] || variable==[T/F])

Find a setting of the variables to make every requirement true.

The spanning tree itself.

Verify by checking it really connects every vertex and its weight.

The assignment of variables.�Verify by checking each requirement.

The coloring.�Verify by checking each edge.

Decision Problems such that:

• If the answer is YES, you can prove the answer is yes by
• A given “proof” or a “certificate” can be verified in polynomial time
• Puzzle problems where a given answer can be either confirmed or rejected
• When calculating the shortest path, you can review the path and confirm it is shortest.
• When calculating the minimum spanning tree, you can review the tree and confirm all vertices are connected and the sum of edges are minimized

Light Spanning Tree:

IS there a spanning tree of graph G of weight at most k?

CSE 373 24WI

10

Pop Quiz: Math race

This Side

What are the two prime factors of 6497?

What’s 31 * 17?

This Side

In P and NP*

In NP but is it in P too?*

* Technically not phrased as decision problems, but can be easily changed to equivalent decision problems

CSE 373 24WI

11

P vs. NP, the conundrum

Does being able to quickly validate a correct solution also mean you can quickly find a correct solution?

​

Are P and NP the same complexity class?

That is, can every problem that can be verified in polynomial time also be solved in polynomial time.

P vs. NP

No one knows the answer to this question.

Introduced in 1971, it instantly became the biggest open problem in Computer Science…

CSE 373 24WI

12

P vs NP

P problems

problems with an efficient solution

NP problems

problems with an efficient solution verification

Satisfiability (SAT)

Travelling salesman (hamiltonian circuit)

finding primes

Job scheduling

Database problems

multiplication

sorting

Can we PROVE that all problems with an efficiently verifiable solution can be solved efficiently?

sudoku

Did I make the best chess move possible?

Will all NP problems be discovered to also be in P?

maze solvers (dijkstra's)

MSTs

knapsack

Graph coloring

Protein folding

2SAT

Graph 2 Color

EXP problems

problems with bounded by an exponential computation or verification

CSE 373 24WI

13

Searching for a solution to P v NP

CSE 373 24WI

14

Hard Problems

Let’s say we want to prove that every problem in NP can actually be solved efficiently.

We might want to start with a really hard problem in NP.

What is the hardest problem in NP?

What does it mean to be a hard problem?

Reductions are a good definition:

• If A reduces to B then “A ≤ B” (in terms of difficulty)
• Once you have an algorithm for B, you have one for A automatically from the reduction!

​

Does there exist an algorithm that all NP problems reduce to?

CSE 373 24WI

15

NP-Completeness

An NP-complete problem is a “hardest” problem in NP.

If you have an algorithm to solve an NP-complete problem, you have an algorithm for every problem in NP.

An NP-complete problem is a universal language for encoding “I’ll know it when I see it” problems.

​

Does one of these exist?

​

The problem B is NP-complete if B is in NP and �for all problems A in NP, A reduces to B.

NP-complete

CSE 373 24WI

16

NP Completeness

NP problems

problems with an efficient solution verification

Travelling salesman (hamiltonian circuit)

Job scheduling

Database problems

sudoku

Did I make the best chess move possible?

knapsack

Protein folding

NP complete problems

NP problems that all reduce to one another

reduction

Graph coloring

Satisfiability (SAT)

CSE 373 24WI

17

NP-Completeness

An NP-complete problem does exist!

​

3-SAT is NP-complete

Cook-Levin Theorem (1971)

This sentence (and the proof of it) won Cook the Turing Award.

CSE 373 24WI

18

Boolean Satisfiability (all variables are booleans)

CSE 373 24WI

19

2-SAT vs. 3-SAT

Recursive Backtracking can solve 2-SAT (just try all variable settings) in O(2ⁿ S) time

But there exists a really clever graph reduction optimization that reduces the solution time to O(n + S) time > 2-SAT can be solved in Polynomial time!

​

In fact you can use automated “sat solvers” to solve any problem you can reduce to 2-SAT Modern SAT solvers: fast, neat and underused (part 1 of N) (Article)

CSE 373 24WI

20

3-SAT is “

Can we do the same for 3-SAT?

• Not yet… the only solution we have to 3-SAT runs in O(3ⁿ S)

​

Since 3-SAT is generalized boolean logic- can it be reduced to another problem that CAN be solved in P time?

​

Researchers start trying to reduce their problems to 3-SAT and…

CSE 373 24WI

21

NP-Complete Problems

They discover over a 100 problems are ALSO NP-Complete!

​

A lot of problems are NP-complete

Karp’s Theorem (1972)

CSE 373 24WI

22

NP-Complete Problems

But Wait! There’s more!

By 1979, at least 300 problems had been proven NP-complete.�

Garey and Johnson put a list of all the NP-complete problems they could find in this textbook.

Took almost 100 pages to just list them all.

​

No one has made a comprehensive list since.

CSE 373 24WI

23

NP-Complete Problems

But Wait! There’s more!

​

In the last month, mathematicians and computer scientists have put papers on the arXiv claiming to show (at least) 25 more problems are NP-complete.

​

There are literally thousands of NP-complete problems known.

And some of them look weirdly similar to problems we’ve already studied.

Wikipedia List of NP Complete Problems

CSE 373 24WI

24

Examples

In P

NP-Complete

There are literally thousands of NP-complete problems.

And some of them look weirdly similar to problems we do know efficient algorithms for.

CSE 373 24WI

25

Examples

The electric company just needs a greedy algorithm to lay its wires.

Amazon doesn’t know a way to optimally route its delivery trucks.

In P

NP-Complete

CSE 373 24WI

26

Dealing with NP-Completeness

Option 1: Maybe it’s a special case we understand

Maybe you don’t need to solve the general problem, just a special case

​

Option 2: Maybe it’s a special case we don’t understand (yet)

There are algorithms that are known to run quickly on “nice” instances. Maybe your problem has one of those.

One approach: Turn your problem into a SAT instance, find a solver and cross your fingers.

​

CSE 373 24WI

27

Dealing with NP-Completeness

Option 3: Approximation Algorithms

You might not be able to get an exact answer, but you might be able to get close.

​

Given a weighted graph, find a tour (a walk that visits every vertex and returns to its start) of weight at most k.

Optimization version of Traveling Salesperson

Algorithm:

Find a minimum spanning tree.

Have the tour follow the visitation order of a DFS of the spanning tree.

Theorem: This tour is at most twice as long as the best one.

CSE 373 24WI

28

Why should you care about P vs. NP

Most computer scientists are convinced that P≠NP.

Why should you care about this problem?

It’s your chance for:

• $1,000,000. The Clay Mathematics Institute will give $1,000,000 to whoever solves P vs. NP
• (or any of the 6 remaining Millenium Prize Problems)
• To get a Turing Award

​

Most computer scientists are convinced that P≠NP.

Why should you care about this problem?

It’s your chance for:

• $1,000,000. The Clay Mathematics Institute will give $1,000,000 to whoever solves P vs. NP
• (or any of the 6 remaining Millenium Prize Problems)
• To get a Turing Award the Turing Award named after you

​

CSE 373 24WI

29

Why Should You Care if P=NP?

Suppose P=NP.

Specifically that we found a genuinely in-practice efficient algorithm for an NP-complete problem. What would you do?

• $1,000,000 from the Clay Math Institute obviously, but what’s next?

​

CSE 373 24WI

30

Why Should You Care if P=NP?

We found a genuinely in-practice efficient algorithm for an NP-complete problem. What would you do?

• Another $5,000,000 from the Clay Math Institute
• Put mathematicians out of work.
• Decrypt (essentially) all current internet communication.
• No more secure online shopping or online banking or online messaging…or online anything.
• Cure cancer with efficient protein folding

​

A world where P=NP is a very very different place from the world we live in now.

CSE 373 24WI

31

Why Should You Care if P≠NP?

We already expect P ≠ NP. Why should you care when we finally prove it?

P ≠ NP says something fundamental about the universe.

For some questions there is not a clever way to find the right answer

• Even though you’ll know it when you see it
• Some problems require “creative leaps” to find a solution that cannot be programmed

There is actually a way to obscure information, so it cannot be found quickly no matter how clever you are.

CSE 373 24WI

32

Why Should You Care if P≠NP?

To prove P≠NP we need to better understand the differences between problems:

• Why do some problems allow easy solutions and others don’t?
• What is the structure of these problems?

We don’t care about P vs NP just because it has a huge effect about what the world looks like.

We care about P vs NP because it shows there is still plenty to learn about the very nature of computing and problem solving.

​

CSE 373 24WI

33

Why Should You Care if P≠NP?

“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” -Scott Aaronson, MIT complexity researcher

CSE 373 24WI

34

Questions?

CSE 373 24WI

35