Lecture 23: P v. NP

CSE 373: Data Structures and Algorithms

1

Announcements

EX 6 due Tomorrow

P4 due Wednesday

EC Survey 3 released later this evening

• due August 19th 11:59PM
• worth 1 point

​

UW Class Survey Out Now

• you should’ve gotten an email about it
• if >= 90% of class responds, everyone gets 5 extra credit points

CSE 373 21 SP – CHAMPION

2

tinyurl.com/Summer373L23

Warm Up

CSE 373 20 SP – CHAMPION & CHUN

3

Worst case runtime?

​

Best case runtime?

​

In-practice runtime?

​

Stable?

​

In-place?

No

Yes

Worst case runtime?

​

Best case runtime?

​

In-practice runtime?

​

Stable?

​

In-place?

Yes

Yes

Worst case runtime?

​

Best case runtime?

​

In-practice runtime?

​

Stable?

​

In-place?

No

Yes

Selection Sort

Insertion Sort

Heap Sort

0/1 Knapsack Problem

Given a set of objects which have both a value and a weight (v_i, w_i) what is the maximum value we can obtain by selecting a subset of these objects such that the sum of the weights does not exceed the knapsacks given capacity?

4

Problem Walk Through Video

Brute Force Recursive Solution

public int knapsack(int n, int cap, int[] w, int[] v) {

if (n == 0 || cap == 0) {

result = 0;

} else if (w[n] > cap) {

result = knapsack(n-1, cap, w, v);

} else {

int temp1 = knapsack(n-1, cap, w, v);

int temp2 = v[n] + knapsack(n-1, cap - w[n-1], w, v);

result = Math.max(temp1, temp2);

return result;

}

}

5

O(2ⁿ)

Recursive Solution is Exponential

6

Memoized DP Solution

public int knapsack(int n, int cap, int[] w, int[] v, int[][] memo) {

int result = memo[n][cap];

if (memo[n][cap] == NULL) {

if (n == 0 || cap == 0) {

result = 0;

} else if (w[n] > c) {

result = knapsack(n-1, cap);

} else {

int temp1 = knapsack(n-1, cap);

int temp2 = v[n] + knapsack(n-1, cap - w[n-1]);

result = Math.max(temp1, temp2);

memo[n][cap] = result;

}

}

return result;

}

7

O(n)

Administrivia

• Midterm Grades Posted!
• Design Creation + Design Review out of 61 points
• Regrade requests open Thur 5/26 @ 8am, close Wed 6/1 @ 11:59pm
• ​

CSE 373 WI19 - KASEY CHAMPION

8

The 2 Sat Solver

CSE 373 SP 18 - KASEY CHAMPION

9

Topological Sort

Perform a topological sort of the following DAG

CSE 373 19 SP - KASEY CHAMPION

10

A

B

C

E

D

If a vertex doesn’t have any edges going into it, we add it to the ordering

If the only incoming edges are from vertices already in the ordering, then add to ordering

0

1

2

1

1

A

C

B

D

E

0

1

0

0

0

​

Given: a directed graph G

Find: an ordering of the vertices so all edges go from left to right.

Topological Sort

​

A directed graph without any cycles.

Directed Acyclic Graph (DAG)

Strongly Connected Components

• Note: the direction of the edges matters!

​

CSE 373 19 SP - KASEY CHAMPION

11

D

B

C

A

E

Why Find SCCs?

• Graphs are useful because they encode relationships between arbitrary objects.
• We’ve found the strongly connected components of G.
• Let’s build a new graph out of them! Call it H
• Have a vertex for each of the strongly connected components
• Add an edge from component 1 to component 2 if there is an edge from a vertex inside 1 to one inside 2.

​

CSE 373 SP 18 - KASEY CHAMPION

12

D

C

F

B

E

A

K

J

1

3

4

2

Why Find SCCs?

​

​

​

​

​

​

• That’s awful meta. Why?
• This new graph summarizes reachability information of the original graph.
• I can get from A (of G) in 1 to F (of G) in 3 if and only if I can get from 1 to 3 in H.

CSE 373 SP 18 - KASEY CHAMPION

13

D

C

F

B

E

A

K

J

1

3

4

2

Why Must H Be a DAG?

• H is always a DAG (i.e. it has no cycles). Do you see why?

​

• If there were a cycle, I could get from component 1 to component 2 and back, but then they’re actually the same component!

CSE 373 SP 18 - KASEY CHAMPION

14

Takeaways

• Finding SCCs lets you collapse your graph to the meta-structure.�If (and only if) your graph is a DAG, you can find a topological sort of your graph.

​

• Both of these algorithms run in linear time.
• Just about everything you could want to do with your graph will take at least as long.
• You should think of these as “almost free” preprocessing of your graph.
• Your other graph algorithms only need to work on
• topologically sorted graphs and
• strongly connected graphs.

​

CSE 373 SP 18 - KASEY CHAMPION

15

A Longer Example

• The best way to really see why this is useful is to do a bunch of examples.
• We don’t have time. The second best way is to see one example right now...
• This problem doesn’t look like it has anything to do with graphs
• no maps
• no roads
• no social media friendships
• Nonetheless, a graph representation is the best one.
• I don’t expect you to remember the details of this algorithm.
• I just want you to see
• graphs can show up anywhere.
• SCCs and Topological Sort are useful algorithms.

CSE 373 SP 18 - KASEY CHAMPION

16

Example Problem: Final Review

• We have a long list of types of problems we might want to put on the final.
• Heap insertion problem, big-O problems, finding closed forms of recurrences, graph modeling…
• What if we let the students choose the topics?
• To try to make you all happy, we might ask for your preferences. Each of you gives us two preferences of the form “I [do/don’t] want a [] problem on the exam” *
• We’ll assume you’ll be happy if you get at least one of your two preferences.

CSE 373 SP 18 - KASEY CHAMPION

17

*This is NOT how Kasey is making the final ;)

Review Creation: Take 1

CSE 373 SP 18 - KASEY CHAMPION

18

Review Creation: Take 2

Each student introduces new relationships for data:

• Let’s say your preferences are represented by this table:�

CSE 373 SP 18 - KASEY CHAMPION

19

If we don’t include a big-O proof, can you still be happy?

If we do include a recurrence can you still be happy?

​

Yes! Big-O

NO recurrence

Yes! recurrence

NO Graph

NO Big-O

Yes!�Graph

NO Heaps

Yes! Heaps

Review Creation: Take 2

• Hey we made a graph!
• What do the edges mean?
• Each edge goes from something making someone unhappy, to the only thing that could make them happy.
• We need to avoid an edge that goes TRUE THING 🡪 FALSE THING

CSE 373 SP 18 - KASEY CHAMPION

20

NO recurrence

NO Big-O

True

False

• We need to avoid an edge that goes TRUE THING 🡪 FALSE THING
• Let’s think about a single SCC of the graph.

​

​

​

​

​

​

• Can we have a true and false statement in the same SCC?
• What happens now that Yes B and NO B are in the same SCC?

​

CSE 373 SP 18 - KASEY CHAMPION

21

Final Creation: SCCs

• The vertices of a SCC must either be all true or all false.
• Algorithm Step 1: Run SCC on the graph. Check that each question-type-pair are in different SCC.
• Now what? Every SCC gets the same value.
• Treat it as a single object!
• We want to avoid edges from true things to false things.
• “Trues” seem more useful for us at the end.
• Is there some way to start from the end?

YES! Topological Sort

CSE 373 SP 18 - KASEY CHAMPION

22

CSE 373 SP 18 - KASEY CHAMPION

23

NO F

Yes�F

Yes�H

Yes�G

NO H

NO G

CSE 373 SP 18 - KASEY CHAMPION

24

NO F

Yes�F

Yes�H

Yes�G

NO H

NO G

CSE 373 SP 18 - KASEY CHAMPION

25

NO F

Yes�F

Yes�H

Yes�G

NO H

NO G

1

6

5

2

3

4

CSE 373 SP 18 - KASEY CHAMPION

26

NO F

Yes�F

Yes�H

Yes�G

NO H

NO G

1

6

5

2

3

4

True

False

True

False

True

False

Making the Final

• Algorithm:�Make the requirements graph.
• Find the SCCs.
• If any SCC has including and not including a problem, we can’t make the final.
• Run topological sort on the graph of SCC.
• Starting from the end:
• if everything in a component is unassigned, set them to true, and set their opposites to false.
• This works!!
• How fast is it?
• O(Q + S). That’s a HUGE improvement.

CSE 373 SP 18 - KASEY CHAMPION

27

Some More Context

• The Final Making Problem was a type of “Satisfiability” problem.
• We had a bunch of variables (include/exclude this question), and needed to satisfy everything in a list of requirements.

​

​

​

​

​

​

• The algorithm we just made for Final Creation works for any 2-SAT problem.

​

​

​

CSE 373 SP 18 - KASEY CHAMPION

28

Reductions

CSE 373 SP 18 - KASEY CHAMPION

29

2-Coloring

• Can these graphs be 2-colored? If so find a 2-coloring. If not try to explain why one doesn’t exist.

CSE 373 SP 18 - KASEY CHAMPION

30

B

D

E

A

C

2-Coloring

2-Coloring

• Can these graphs be 2-colored? If so find a 2-coloring. If not try to explain why one doesn’t exist.

CSE 373 SP 18 - KASEY CHAMPION

31

B

D

E

A

C

What are we doing?

• To wrap up the course we want to take a big step back.
• This whole quarter we’ve been taking problems and solving them faster.
• We want to spend the last few lectures going over more ideas on how to solve problems faster, and why we don’t expect to solve everything extremely quickly.

​

• We’re going to
• Recall reductions – Robbie’s favorite idea in algorithm design.
• Classify problems into those we can solve in a reasonable amount of time, and those we can’t.
• Explain the biggest open problem in Computer Science

CSE 373 SP 18 - KASEY CHAMPION

32

Reductions: Take 2

• You already do this all the time.
• In Homework 3, you reduced implementing a hashset to implementing a hashmap.
• Any time you use a library, you’re reducing your problem to the one the library solves.

​

​

Using an algorithm for Problem B to solve Problem A.

Reduction (informally)

Weighted Graphs: A Reduction

CSE 373 SP 18 - KASEY CHAMPION

14

Reductions

• It might not be too surprising that we can solve one shortest path problem with the algorithm for another shortest path problem.
• The real power of reductions is that you can sometimes reduce a problem to another one that looks very very different.
• We’re going to reduce a graph problem to 2-SAT.

CSE 373 SP 18 - KASEY CHAMPION

35

2-Coloring

2-Coloring

• Why would we want to 2-color a graph?
• We need to divide the vertices into two sets, and edges represent vertices that can’t be together.
• You can modify BFS to come up with a 2-coloring (or determine none exists)
• This is a good exercise!
• But coming up with a whole new idea sounds like work.
• And we already came up with that cool 2-SAT algorithm.
• Maybe we can be lazy and just use that!
• Let’s reduce 2-Coloring to 2-SAT!

CSE 373 SP 18 - KASEY CHAMPION

36

Use our 2-SAT algorithm

to solve 2-Coloring

A Reduction

• We need to describe 2 steps
• 1. How to turn a graph for a 2-color problem into an input to 2-SAT
• 2. How to turn the ANSWER for that 2-SAT input into the answer for the original 2-coloring problem.
• How can I describe a two coloring of my graph?
• Have a variable for each vertex – is it red?
• How do I make sure every edge has different colors? I need one red endpoint and one blue one, so this better be true to have an edge from v1 to v2:
• (v1IsRed || v2isRed) && (!v1IsRed || !v2IsRed)

CSE 373 SP 18 - KASEY CHAMPION

37

CSE 373 SP 18 - KASEY CHAMPION

38

AisRed = True

BisRed = False

CisRed = True

DisRed = False

EisRed = True

(AisRed||BisRed)&&(!AisRed||!BisRed)

(AisRed||DisRed)&&(!AisRed||!DisRed)

(BisRed||CisRed)&&(!BisRed||!CisRed)

(BisRed||EisRed)&&(!BisRed||!EisRed)

(DisRed||EisRed)&&(!DisRed||!EisRed)

​

​

P vs. NP

CSE 373 SP 18 - KASEY CHAMPION

39

P vs NP Explained (YouTube)

Efficient

CSE 373 - 18AU

40

Decision Problems

CSE 373 - 18AU

41

Running Times

CSE 373 WI19 - KASEY CHAMPION

42

P Complexity Class

​

​

​

​

​

​

​

CSE 373 WI19 - KASEY CHAMPION

43

The decision version of all problems we’ve solved in this class are in P.

​

P is an example of a “complexity class”

A set of problems that can be solved under some limitations (e.g. with some amount of memory or in some amount of time).

NP Complexity Class

CSE 373 19 SP - KASEY CHAMPION

44

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.

​

The set of all decision problems such that if the answer is YES, there is a proof of that which can be verified in polynomial time.

NP (stands for “nondeterministic polynomial”)

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
• What certificate would be convenient for short paths?
• The path itself. Easy to check the path is really in the graph and really short.

P vs. NP

• Does being able to quickly validate a correct solution also mean you can quickly find a correct solution?
• ​
• No one knows the answer to this question.
• In fact, it’s the biggest open problem in Computer Science.

CSE 373 WI19 - KASEY CHAMPION

45

​

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

Hard Problems

CSE 373 WI19 - KASEY CHAMPION

46

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?

CSE 373 WI19 - KASEY CHAMPION

47

​

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

NP-complete

NP-Completeness

• An NP-complete problem does exist!

CSE 373 WI19 - KASEY CHAMPION

48

​

3-SAT is NP-complete

Cook-Levin Theorem (1971)

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

2-SAT vs. 3-SAT

CSE 373 WI19 - KASEY CHAMPION

49

https://www.youtube.com/watch?v=SAXGKCnOuP8

2-SAT vs. 3-SAT

CSE 373 WI19 - KASEY CHAMPION

50

2-SAT vs. 3-SAT

CSE 373 WI19 - KASEY CHAMPION

51

Can we do the same for 3-SAT?

NO recurrence

NO Big-O

NP-Complete Problems

• But Wait! There’s more!

CSE 373 WI19 - KASEY CHAMPION

52

​

A lot of problems are NP-complete

Karp’s Theorem (1972)

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 WI19 - KASEY CHAMPION

53

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.

CSE 373 WI19 - KASEY CHAMPION

54

Examples

CSE 373 WI19 - KASEY CHAMPION

55

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.

Examples

CSE 373 WI19 - KASEY CHAMPION

56

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

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

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 WI19 - KASEY CHAMPION

57

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.

CSE 373 WI19 - KASEY CHAMPION

58

​

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.

Why should you care about P vs. NP

CSE 373 WI19 - KASEY CHAMPION

59

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 5 remaining problems they listed)

To get a Turing Award

​

Why should you care about P vs. NP

CSE 373 WI19 - KASEY CHAMPION

60

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 5 remaining problems they listed)

To get a Turing Award the Turing Award renamed after you.

​

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 WI19 - KASEY CHAMPION

61

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.

​

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

CSE 373 WI19 - KASEY CHAMPION

62

CSE 373 WI19 - KASEY CHAMPION

63

Why Should You Care if P≠NP?

CSE 373 WI19 - KASEY CHAMPION

64

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 will learn a lot about computation along the way.

​

Why Should You Care if P≠NP?