P/NP

CSE 332 – Section 10

P/NP

An alternate diagram of P/NP

NP

NP Complete

NP Hard

Sorting

Shortest Path

Euler Path

Vertex Cover

Independent Set

Hamiltonian Path

Halting Problem

N x N Chess

If P = NP, everything in the green bubble is actually P!

P

One more diagram of P/NP

difficulty

NP-Complete

P

NP-Hard

NP-Intermediate

EXP

If P = NP, the gap between yellow and red lines collapse!

P, NP, NP-Complete

• Complexity Class:
• A set of decision problems categorized by an asymptotic upper bound on the fastest algorithm that solves them
• If a decision problem is solved by an algorithm that runs in O(n) time then it belongs to the complexity class for O(n) and O(n log n) and O(n^2), but not O(log n).
• Decision Problem:
• A problem where the output is True or False
• What does P stand for?
• What is NP stand for?
• What is the definition of P?
• What is the definition of NP?

Complexity Classes (Question 0)

• Complexity Class:
• A set of decision problems categorized by an asymptotic upper bound on the fastest algorithm with solves them
• If a decision problem is solved by an algorithm that runs in O(n) time then it belongs to the complexity class for O(n) and O(n log n) and O(n^2), but not O(log n).
• Decision Problem:
• A problem where the output is True or False
• What does P stand for?
• Polynomial Time
• What is NP stand for?
• Non-deterministic Polynomial Time
• What is the definition of P?
• The set of decision problems which have polynomial time algorithms to solve them (running time is O(n^p))
• What is the definition of NP?
• The set of decision problems which have polynomial time verifiers (can check answers in polynomial time)
• Equivalently, the set of decision problems which have polynomial time non-deterministic algorithms

Complexity Classes (Question 0)

P, NP, NP-Complete

• How would we show that a given decision problem belongs to the class P?
• How would we show that a given decision problem belongs to the class NP?

​

P & NP Membership (Question 1)

• How would we show that a given decision problem belongs to the class P?
• Show there exists a polynomial time algorithm which solves that problem.
• How would we show that a given decision problem belongs to the class NP?
• Show that there exists a polynomial time algorithm which verifies that problem.
• Note: you could also show a decision problem belongs to a subset of NP (e.g. P), but for today we want to practice writing verifiers!

​

​

P & NP Membership (Question 1)

• Consider the following problems:
• Problem A: Given a list of 2-dimensional points, return true or false to indicate whether some pair of points have a distance of less than 5.
• Problem B: Given a list of integers, return true or false to indicate whether any items are duplicated (so return true if some value appears at least twice, false if all are distinct).
• Problem C: Given a weighted graph, a pair of nodes X and Y, and a number k, return true or false to indicate whether there is a path from X to Y with a cost of at least k
• Show that A and B belong to P
• Show that A, B, and C belong to NP

​

​

P & NP Membership (Question 2)

P, NP, NP-Complete

• Given a list of 2-dimensional points, return true or false to indicate whether some pair of points have a distance of less than 5.

​

Algorithm: For each point, find its distance to every other point. If the distance is ever less than 5, return true. After doing this for all points, return false.

​

Running time: O(n^2)

​

Problem A is in P

P, NP, NP-Complete

• Given a list of 2-dimensional points, return true or false to indicate whether some pair of points have a distance of less than 5.

​

Verification Algorithm: Given a candidate pair of points, verify that those points are both in the list, then verify that their distance is less than 5.

​

Running time: O(n)

​

Problem A is in NP

P, NP, NP-Complete

• Given a list of integers, return true or false to indicate whether any items are duplicated (so return true if some value appears at least twice, false if all are distinct).

​

Algorithm: Sort the list, then check if any two neighboring items match.

​

Running time: O(n log n)

​

Problem B is in P

P, NP, NP-Complete

• Given a list of integers, return true or false to indicate whether any items are duplicated (so return true if some value appears at least twice, false if all are distinct).

​

Verification Algorithm: Given a candidate value, check that the value appears at least twice in the list.

​

Running time: O(n)

​

Problem B is in NP

P, NP, NP-Complete

• Given a weighted graph, a pair of nodes X and Y, and a number k, return true or false to indicate whether there is a path from X to Y with a cost of at least k

​

Verification Algorithm: Given a candidate path, check that it is a valid path (all adjacent nodes in the path form edges in the graph), and check that the sum of those edge weights is at least the value k.

​

Running time: O(V + E)

​

Problem C is in NP

P, NP, NP-Complete

• What is the definition of NP-Hard?

​

• What is the definition of NP-Complete?

​

NP-Hard, NP-Complete (Question 3)

P, NP, NP-Complete

• What is the definition of NP-Hard?
• The decision problems that are “at least as hard” as any in NP
• The set of decision problems for which there exists a polynomial time reduction from every NP problem to it
• What is the definition of NP-Complete?
• The intersection of NP and NP-Hard

NP-Hard, NP-Complete

P, NP, NP-Complete

• How do you show that a decision problem belongs to NP-Hard

​

• How do you show that a decision problem belongs to NP-Complete

​

NP-Hard, NP-Complete (Question 4)

P, NP, NP-Complete

• How do you show that a decision problem belongs to NP-Hard
• Reduce a preexisting NP-Hard problem to it
• How do you show that a decision problem belongs to NP-Complete
• Show that it belongs to NP and NP-Hard
• Find a polynomial time verification algorithm and reduce preexisting NP-Hard problem to it

NP-Hard, NP-Complete

P, NP, NP-Complete

• A reduction from problem A to problem B is a way of solving A using B as a subroutine
• Plugging in any algorithm for B finishes an algorithm for A
• A polynomial time reduction is a reduction which requires only a polynomial amount of additional work (ignoring the running time of the algorithm for B, the running time is polynomial)
• Plugging in a polynomial time algorithm for B finishes a polynomial time algorithm for A
• Most Importantly:
• If there is a polynomial time reduction from A to B, then if B has a polynomial time solution, then A does as well.
• If A is NP-Hard, since every NP problem reduces to it in polynomial time, reducing A to B means solving B in polynomial time allows us to solve EVERY NP problem in polynomial time

Reduction

Reductions Visual

Reduction

n^p work to relate Problem A input

to Problem B input

n^p work to relate Problem B output to Problem A output

Solution for A

Solution for B

“A polynomial time reduces to B”

P, NP, NP-Complete

Sorting Problem:

• Is the given list of numbers sorted?

​

Min Hamiltonian Path Problem:

• Does there exist a Hamiltonian path whose total weight is ≤ c?

​

We want to reduce Sorting Problem to Min Hamiltonian Path Problem

Example: Hamiltonian Sort

P, NP, NP-Complete

• A Hamiltonian Path in a graph is a path that:
• visits every vertex exactly once
• Optimization version:
• Find the minimum cost Hamiltonian path
• Known NP-hard problem

Example: Hamiltonian Sort

P, NP, NP-Complete

• Given numbers: a1, a2, a3, ..., an
• Create points in the plane Pi = (ai, 0)
• Build a complete graph
• cost(i,j) = Euclidean distance = |ai − aj|
• Let c = max - min. If path cost ≤ c, then given list is sorted.

Example: Construct Graph

P2

P1

P3

distance(P2, P3) = | a3-a2 |

distance(P2, P1)

distance(P1, P3)

P, NP, NP-Complete

• L1 = [1, 4, 2, 7]
• P1 = (1,0), (4,0), (2,0), (7,0)

Example: Create Vertices

(1, 0)

(2, 0)

(7, 0)

(4, 0)

P, NP, NP-Complete

• L1 = [1, 4, 2, 7]
• P1 = (1,0), (4,0), (2,0), (7,0)

Example: Construct Edges

(1, 0)

(2, 0)

(7, 0)

(4, 0)

6

1

3

2

3

5

P, NP, NP-Complete

• L1 = [1, 4, 2, 7]
• P1 = (1,0), (4,0), (2,0), (7,0)
• c = Max - Min = 7 - 1 = 6
• Path Cost of (1,0) → (4,0) → (2,0) → (7,0) = 3+2+5 = 10 > 6
• Since the given path is not ≤ c, L1 is not sorted

Example: Compute path

(1, 0)

(2, 0)

(7, 0)

(4, 0)

6

1

3

2

3

5

P, NP, NP-Complete

• L2 = [1, 2, 4, 7]
• P2 = (1,0), (2,0), (4,0), (7,0)
• c = Max - Min = 7 - 1 = 6
• Path Cost of (1,0) → (2,0) → (4,0) → (7,0) = 1+2+3 = 6
• Since the given path ≤ c, L2 is sorted

Example: Sorted List

(1, 0)

(2, 0)

(7, 0)

(4, 0)

6

1

3

2

3

5

P, NP, NP-Complete

• Reduction direction:
• Sorting Problem → Min Hamiltonian Path Problem

​

• If one could solve Min Hamiltonian Path, one could solve the sorting problem. Thus:
• Sorting Problem ≤ Hamiltonian Path Problem

​

Example: Compare difficulty

P, NP, NP-Complete

• Given there is a polynomial time reduction from A to B, then if B has a polynomial time solution, then A does as well.
• To solve A: convert A’s input to B, Solve B, convert answer back to one for A
• Because of the reduction, a polynomial time algorithm for B is the only missing piece of a polynomial time algorithm for A
• If A is NP-Hard, since every NP problem reduces to it in polynomial time, a polynomial time algorithm for solving A finishes polynomial time algorithms for ALL of NP.
• So if B has a polynomial time algorithm, then so does every choice for A, and therefore all of NP does as well.

​

Reductions and NP-Hard

P, NP, NP-Complete

• If some problem A is NP-Complete then:
• Because A belongs to NP, if there does not exist a polynomial time algorithm for A then we can conclude P does not equal NP (A is a counterexample to P = NP)
• Because A belongs to NP-hard, if there does exist a polynomial time algorithm for A then we can solve EVERY NP problem in polynomial time, and so P = NP. (because of previous slide)
• Answering the question “can A be solved in polynomial time?” gives us the answer for the entirety of P=NP

NP-Complete

P, NP, NP-Complete

1. If A polynomial-time reduces to B and B is NP-Hard then A is NP-Hard.
2. If B is NP-Hard and there exists a polynomial time algorithm for B, then P=NP
3. If B is NP-Hard and there does not exist a polynomial time algorithm for B, then P does not equal NP
4. If A reduces to B in polynomial time, and B reduces to C in polynomial time, and A is NP-Hard, then C is NP-Hard.
5. If A reduces to B in polynomial time, and B reduces to C in polynomial time, and A is NP-Complete, then C is NP-Complete.
6. If A reduces to B in polynomial time, and B reduces to C in polynomial time, and A is in EXP, then C is EXP.
7. If A reduces to B in polynomial time, and B reduces to C in polynomial time, and A is in P, then C is P.
8. If A reduces to B in polynomial time, and B reduces to C in polynomial time, and A is in NP, and C is in P, then P=NP
9. If A reduces to B in polynomial time, and B reduces to C in polynomial time, and A is in NP-Hard, and C is in P, then P=NP

Practice - True/False

P, NP, NP-Complete

1. If A polynomial-time reduces to B and B is NP-Hard then A is NP-Hard.
2. If B is NP-Hard and there exists a polynomial time algorithm for B, then P=NP.
3. If B is NP-Hard and there does not exist a polynomial time algorithm for B, then P does not equal NP.
4. If A reduces to B in polynomial time, and B reduces to C in polynomial time, and A is NP-Hard, then C is NP-Hard.
5. If A reduces to B in polynomial time, and B reduces to C in polynomial time, and A is NP-Complete, then C is NP-Complete.
6. If A reduces to B in polynomial time, and B reduces to C in polynomial time, and A is in EXP, then C is EXP.
7. If A reduces to B in polynomial time, and B reduces to C in polynomial time, and A is in P, then C is P.
8. If A reduces to B in polynomial time, and B reduces to C in polynomial time, and A is in NP, and C is in P, then P=NP.
9. If A reduces to B in polynomial time, and B reduces to C in polynomial time, and A is in NP-Hard, and C is in P, then P=NP.

Practice - True/False

False

True

False

True

False

False

False

False

True

Thank You!