Intro to Complexity Theory

Computability theory (1930s - 1950s):

Is A decidable?
Complexity theory (1960s - present):
Is A decidable with restricted resources?
(time/memory/…)

Example: Let 𝐴 = a𝑘 b𝑘 𝑘 ≥ 0 .
Q: How many steps are needed to decide 𝐴?
Depends on the input.
We give an upper bound for all inputs of length 𝑛.
Called “worst-case complexity”.

2
P and N P
Example 13-2
▶ Given a sorted array A, write an algorithm in pseudocode that determines the
location of element x. Then, find the time complexity of that algorithm.
Example 13-2
▶ Given a sorted array A, write an algorithm in pseudocode that determines the
location of element x. Then, find the time complexity of that algorithm.

▶ INPUT: Array A, element x

low = 1
high = size(A)
While low <= high
mid = (low+high)/2
If A(mid) < x
low = mid + 1
ElseIf A(mid) > x
high = mid -1
Else
Return mid
End
End
Return NOT FOUND
Example 13-2
▶ Given a sorted array A, write an algorithm in pseudocode that determines the
location of element x. Then, find the time complexity of that algorithm.

▶ INPUT: Array A, element x

low = 1
high = size(A)
While low <= high
mid = (low+high)/2
If A(mid) < x
low = mid + 1
ElseIf A(mid) > x
high = mid -1
Else
Return mid
End
End
Return NOT FOUND
▶ O(log2 n)
Example 13-3
▶ The following program checks if all elements of the given array are distinct. It
returns FALSE if any two are the same. What is the time complexity?
INPUT: Array A
n = size(A)
For i = 1 to n - 1
For j = i + 1 to n
If A(i) == A(j)
Return FALSE
End
End
End
Return TRUE
Example 13-3
▶ The following program checks if all elements of the given array are distinct. It
returns FALSE if any two are the same. What is the time complexity?
INPUT: Array A
n = size(A)
For i = 1 to n - 1
For j = i + 1 to n
If A(i) == A(j)
Return FALSE
End
End
End
Return TRUE
▶ O(n2 )
Example 13-4
▶ Write an algorithm in pseudocode that determines if the element x occurs in a
given unsorted array A or not. What is the time complexity?
Example 13-4
▶ Write an algorithm in pseudocode that determines if the element x occurs in a
given unsorted array A or not. What is the time complexity?
▶ INPUT: Array A, element x
n = size(A)
For i = 1 to n
If x == A(i)
Return TRUE
End
End
Return FALSE
Example 13-4
▶ Write an algorithm in pseudocode that determines if the element x occurs in a
given unsorted array A or not. What is the time complexity?
▶ INPUT: Array A, element x
n = size(A)
For i = 1 to n
If x == A(i)
Return TRUE
End
End
Return FALSE
▶ O(n)
Example 13-5
▶ Write an algorithm in pseudocode that sorts a given array A. It should work by
finding the smallest element and placing it as the first in each iteration. What is
the time complexity?
Example 13-5
▶ Write an algorithm in pseudocode that sorts a given array A. It should work by
finding the smallest element and placing it as the first in each iteration. What is
the time complexity?
▶ INPUT: Array A
n = size(A)
For i = 1 to n
index = i
For j = i + 1 to n
If A(j) < A(index)
index = j
End
End
Swap(A(i), A(index))
End
Example 13-5
▶ Write an algorithm in pseudocode that sorts a given array A. It should work by
finding the smallest element and placing it as the first in each iteration. What is
the time complexity?
▶ INPUT: Array A
n = size(A)
For i = 1 to n
index = i
For j = i + 1 to n
If A(j) < A(index)
index = j
End
End
Swap(A(i), A(index))
End
▶ O(n2 )
Example 13-6
▶ Find the time complexity of the following algorithm based on input size n. You
may assume n is a power of 2 for simplicity.
INPUT: n
S = 0, k = 1
While k <= n
For j = 1 to n
S = S + 1
End
k = 2 * k
End
Example 13-6
▶ Find the time complexity of the following algorithm based on input size n. You
may assume n is a power of 2 for simplicity.
INPUT: n
S = 0, k = 1
While k <= n
For j = 1 to n
S = S + 1
End
k = 2 * k
End
▶ O(nlog2 n)
Example 13-7
▶ Find the time complexity of the following algorithm based on input size n.
INPUT: n
S = 0, k = 1
While k <= n
For j = 1 to k
S = S + 1
End
k = 2 * k
End
Example 13-7
▶ Find the time complexity of the following algorithm based on input size n.
INPUT: n
S = 0, k = 1
While k <= n
For j = 1 to k
S = S + 1
End
k = 2 * k
End
▶ O(n)
Example 13-8
▶ We know that Func1(n) is an algorithm of complexity O(n) and Func2(n) is an
algorithm of complexity O(n2 ). Find the complexity of the following algorithm
that uses these as subroutines:
INPUT: n
For i = 1 to 3n
Func1(i)
Func2(i)
End
For j = 1 to n
Func1(n)
End
Example 13-8
▶ We know that Func1(n) is an algorithm of complexity O(n) and Func2(n) is an
algorithm of complexity O(n2 ). Find the complexity of the following algorithm
that uses these as subroutines:
INPUT: n
For i = 1 to 3n
Func1(i)
Func2(i)
End
For j = 1 to n
Func1(n)
End
▶ O(n3 )
Example 13-9
▶ We are trying to crack a password of n digits using brute force method. How
many operations do we need if the characters used in the password are:
1. Decimal digits 0, 1, 2, . . . , 9?
2. Binary digits 0, 1?
Example 13-9
▶ We are trying to crack a password of n digits using brute force method. How
many operations do we need if the characters used in the password are:
1. Decimal digits 0, 1, 2, . . . , 9?
2. Binary digits 0, 1?
▶ O(10n )
Example 13-9
▶ We are trying to crack a password of n digits using brute force method. How
many operations do we need if the characters used in the password are:
1. Decimal digits 0, 1, 2, . . . , 9?
2. Binary digits 0, 1?
▶ O(10n )
▶ O(2n )
Example 13-10
▶ We are given a set of n elements and we have to print the list of all the subsets.
Assume printing a single subset is one operation (independent of number of
elements of the subset.) How many operations do we need?
Example 13-10
▶ We are given a set of n elements and we have to print the list of all the subsets.
Assume printing a single subset is one operation (independent of number of
elements of the subset.) How many operations do we need?
▶ O(2n )
Example 13-11
▶ Write an algorithm that checks whether a given undirected graph is connected.
Find the time complexity of the algorithm (assume the graph contains n vertices
and m edges.)
Example 13-11
▶ Write an algorithm that checks whether a given undirected graph is connected.
Find the time complexity of the algorithm (assume the graph contains n vertices
and m edges.)
▶ INPUT: Undirected Graph G
Create an empty stack S
Choose any vertex. Mark it and push to S
While S is not empty
Pop vertex v
For all unmarked neighbors u of v
Mark u and push u to S
End
End
For all vertices w of G
If w is not marked
Return FALSE
End
End
Return TRUE
Example 13-11
▶ Write an algorithm that checks whether a given undirected graph is connected.
Find the time complexity of the algorithm (assume the graph contains n vertices
and m edges.)
▶ INPUT: Undirected Graph G
Create an empty stack S
Choose any vertex. Mark it and push to S
While S is not empty
Pop vertex v
For all unmarked neighbors u of v
Mark u and push u to S
End
End
For all vertices w of G
If w is not marked
Return FALSE
End
End
Return TRUE
▶ Using adjacency matrix, O(n2 )
Example 13-11
▶ Write an algorithm that checks whether a given undirected graph is connected.
Find the time complexity of the algorithm (assume the graph contains n vertices
and m edges.)
▶ INPUT: Undirected Graph G
Create an empty stack S
Choose any vertex. Mark it and push to S
While S is not empty
Pop vertex v
For all unmarked neighbors u of v
Mark u and push u to S
End
End
For all vertices w of G
If w is not marked
Return FALSE
End
End
Return TRUE
▶ Using adjacency matrix, O(n2 )
▶ Using adjacency list, O(n + m)
Example 13-12
▶ You are given a directed graph with n vertices and m edges. Write an algorithm
that checks whether it contains a cycle.
Example 13-12
▶ You are given a directed graph with n vertices and m edges. Write an algorithm
that checks whether it contains a cycle.
▶ INPUT: Directed Graph G
Color all vertices white
For each vertex v of G
If v is white
DFS(G, v)
End
End
Return FALSE
Example 13-12
▶ DFS(G, u)
Color u gray
For all its children w
If w is gray
Return TRUE
ElseIf w is white
DFS(G, w)
End
End
Color u black
Example 13-12
▶ DFS(G, u)
Color u gray
For all its children w
If w is gray
Return TRUE
ElseIf w is white
DFS(G, w)
End
End
Color u black
▶ Using adjacency matrix, O(n2 )
Example 13-12
▶ DFS(G, u)
Color u gray
For all its children w
If w is gray
Return TRUE
ElseIf w is white
DFS(G, w)
End
End
Color u black
▶ Using adjacency matrix, O(n2 )
▶ Using adjacency list, O(n + m)
 The Complexity Class P
● The complexity class P (for polynomial
time) contains all problems that can be
solved in polynomial time.
● Formally:
P = { L | There is a polynomial-time
decider for L }
● Assuming the Cobham-Edmonds thesis, a
language is in P if it can be decided
efficiently.
What can't you do in polynomial time?
start How
How many
many simple
simple
paths
paths are
are there
there
from
from the
the start
start
node
node to
to the
the end
end
end node?
node?
, , ,
How
How many
many
subsets
subsets of
of this
this
set
set are
are there?
there?
 An Interesting Observation
● There are (at least) exponentially many
objects of each of the preceding types.
● However, each of those objects is not very
large.
● Each simple path has length no longer than the
number of nodes in the graph.
● Each subset of a set has no more elements than
the original set.
● This brings us to our next topic...
Example 13-13
▶ You are given a set of n positive integers. You have to find two distinct integers p,
q from this set such that p + q is as close as possible to 256. Show that this
problem is in P.
Example 13-13
▶ You are given a set of n positive integers. You have to find two distinct integers p,
q from this set such that p + q is as close as possible to 256. Show that this
problem is in P.
▶ INPUT: Integer array A, array size n
p = A(1), q = A(2)
For i=1 to n-1
For j=i+1 to n
If |A(i)+A(j)-256| < |p+q-256|
p = A(i), q = A(j)
End
End
End
Return p, q
Example 13-13
▶ You are given a set of n positive integers. You have to find two distinct integers p,
q from this set such that p + q is as close as possible to 256. Show that this
problem is in P.
▶ INPUT: Integer array A, array size n
p = A(1), q = A(2)
For i=1 to n-1
For j=i+1 to n
If |A(i)+A(j)-256| < |p+q-256|
p = A(i), q = A(j)
End
End
End
Return p, q
▶ O(n2 )
Example 13-14
▶ There are n students in a class. We want to find 3 stundes A, B, C such that the
couples A - B, A - C and B - C have been lab or project partners in some course.
Each student gives us a list of all students in the class he/she ever worked with.
Show that this problem is in P.
Example 13-14
▶ There are n students in a class. We want to find 3 stundes A, B, C such that the
couples A - B, A - C and B - C have been lab or project partners in some course.
Each student gives us a list of all students in the class he/she ever worked with.
Show that this problem is in P.
 
n
▶ There are = O(n3 ) triples. We can check each one in O(n) operations by
3
going over lists. That makes O(n4 ) operations.
Example 13-15
▶ You are given a string of length n. You are also given a word (a second string) of
length k, where k ≤ n. You want to determine if the word occurs in the string.
Show that this problem is in P.
Example 13-15
▶ You are given a string of length n. You are also given a word (a second string) of
length k, where k ≤ n. You want to determine if the word occurs in the string.
Show that this problem is in P.
▶ INPUT: String A[n], Word B[k]
For i=1 to n-k+1
test = TRUE
For j=1 to k
If A[i+j-1] != B[j]
test = FALSE
Break
End
End
If test == TRUE
Return TRUE
End
End
Return FALSE
Example 13-15
▶ You are given a string of length n. You are also given a word (a second string) of
length k, where k ≤ n. You want to determine if the word occurs in the string.
Show that this problem is in P.
▶ INPUT: String A[n], Word B[k]
For i=1 to n-k+1
test = TRUE
For j=1 to k
If A[i+j-1] != B[j]
test = FALSE
Break
End
End
If test == TRUE
Return TRUE
End
End
Return FALSE
▶ O(n2 )
Example 13-16 (Euler Path Problem)
▶ An Euler path in a graph G is a path that goes through each edge once. For
example, consider the following graphs:

A solution for the left graph is 1 - 3 - 5 - 2 - 4 - 1 - 2 - 3. There are other

solutions. Note that all such paths either start with 1 and end with 3 or vice
versa. There is no solution for the right one. Is Euler path problem in P?
Example 13-16 (Euler Path Problem)
▶ An Euler path in a graph G is a path that goes through each edge once. For
example, consider the following graphs:

A solution for the left graph is 1 - 3 - 5 - 2 - 4 - 1 - 2 - 3. There are other

solutions. Note that all such paths either start with 1 and end with 3 or vice
versa. There is no solution for the right one. Is Euler path problem in P?
▶ We can easily prove that a graph G contains an Euler path from vertex s to a
different vertex t if and only if:
Example 13-16 (Euler Path Problem)
▶ An Euler path in a graph G is a path that goes through each edge once. For
example, consider the following graphs:

A solution for the left graph is 1 - 3 - 5 - 2 - 4 - 1 - 2 - 3. There are other

solutions. Note that all such paths either start with 1 and end with 3 or vice
versa. There is no solution for the right one. Is Euler path problem in P?
▶ We can easily prove that a graph G contains an Euler path from vertex s to a
different vertex t if and only if:
▶ G is connected,
Example 13-16 (Euler Path Problem)
▶ An Euler path in a graph G is a path that goes through each edge once. For
example, consider the following graphs:

A solution for the left graph is 1 - 3 - 5 - 2 - 4 - 1 - 2 - 3. There are other

solutions. Note that all such paths either start with 1 and end with 3 or vice
versa. There is no solution for the right one. Is Euler path problem in P?
▶ We can easily prove that a graph G contains an Euler path from vertex s to a
different vertex t if and only if:
▶ G is connected,
▶ s and t have odd degree,
Example 13-16 (Euler Path Problem)
▶ An Euler path in a graph G is a path that goes through each edge once. For
example, consider the following graphs:

A solution for the left graph is 1 - 3 - 5 - 2 - 4 - 1 - 2 - 3. There are other

solutions. Note that all such paths either start with 1 and end with 3 or vice
versa. There is no solution for the right one. Is Euler path problem in P?
▶ We can easily prove that a graph G contains an Euler path from vertex s to a
different vertex t if and only if:
▶ G is connected,
▶ s and t have odd degree,
▶ all other vertices of G have even degree.
Example 13-17 (Hamiltonian Path Problem)
▶ A Hamiltonian path in a graph G is a path that goes through each vertex once.
For example, consider the following graphs:

A solution for the left graph is 1 - 2 - 3 - 6 - 5 - 4. There is no solution for the

right one. Is Hamiltonian path problem in P?
Example 13-17 (Hamiltonian Path Problem)
▶ A Hamiltonian path in a graph G is a path that goes through each vertex once.
For example, consider the following graphs:

A solution for the left graph is 1 - 2 - 3 - 6 - 5 - 4. There is no solution for the

right one. Is Hamiltonian path problem in P?
▶ We don’t know; we can try all possible arrangements of vertices and check if there
is such a path. This is a brute-force approach.
n vertices − > n! possible orderings. This is clearly not a polynomial. Actually, it
is even worse than exponential.
Example 13-18 (Shortest Path Problem)

▶
Example 13-18 (Shortest Path Problem)

▶
▶ For a graph with n vertices and adjacency matrix representation, the complexity
will be O(n2 ). Is the Shortest Path Problem in P? Yes.
NP
NP
What if you need to search a large
space for a single object?
Verifiers – Again
7 6 1

3 5 2

3 1 5 9 7

6 5 3 8 9

1 2

8 2 1 5 4

1 3 2 7 8

5 7 4

4 8 7

Does this Sudoku problem

have a solution?
Verifiers – Again
2 5 7 9 6 4 1 8 3

4 9 1 8 7 3 6 5 2

3 8 6 1 2 5 9 4 7

6 4 5 7 3 2 8 1 9

7 1 9 5 4 8 3 2 6

8 3 2 6 1 9 5 7 4

1 6 3 2 5 7 4 9 8

5 7 8 4 9 6 2 3 1

9 2 4 3 8 1 7 6 5

Does this Sudoku problem

have a solution?
 Verifiers – Again

4 3 11 4
9 9 2
7 13 5 6 1 12 7
2 8 0 10

Is there an ascending subsequence of

length at least 7?
 Verifiers – Again

4 3 11 4
9 9 2
7 13 5 6 1 12 7
2 8 0 10

Is there an ascending subsequence of

length at least 7?
 Verifiers – Again

Is there a simple path that goes

through every node exactly once?
 Verifiers – Again

2 4

1 6

5 3
Is there a simple path that goes
through every node exactly once?
 Verifiers
● Recall that a verifier for L is a TM V
such that
● V halts on all inputs.
● w∈L iff ∃c ∈ Σ*. V accepts ⟨w, c⟩.
 Polynomial-Time Verifiers
● A polynomial-time verifier for L is a
TM V such that
● V halts on all inputs.
● w∈L iff ∃c ∈ Σ*. V accepts ⟨w, c⟩.
● V's runtime is a polynomial in |w| (that is, V's
runtime is O(|w|k) for some integer k)
 The Complexity Class NP
●
The complexity class NP (nondeterministic
polynomial time) contains all problems that can be
verified in polynomial time.
● Formally:
NP = { L | There is a polynomial-time
verifier for L }
●
The name NP comes from another way of
characterizing NP. If you introduce nondeterministic
Turing machines and appropriately define
“polynomial time,” then NP is the set of problems
that an NTM can solve in polynomial time.
Example 13-19 (Coloring Problem)
▶ Given a graph with n vertices and an integer k, is there a way to color the vertices
with k colors such that adjacent vertices are colored differently? Is this problem in
N P?
Example 13-19 (Coloring Problem)
▶ Given a graph with n vertices and an integer k, is there a way to color the vertices
with k colors such that adjacent vertices are colored differently? Is this problem in
N P?
▶ For i=1 to n-1
For j=i+1 to n
If vertices i-j are connected
If Color(i) == Color(j)
Return REJECT
End
End
End
End
Return ACCEPT
Example 13-19 (Coloring Problem)
▶ Given a graph with n vertices and an integer k, is there a way to color the vertices
with k colors such that adjacent vertices are colored differently? Is this problem in
N P?
▶ For i=1 to n-1
For j=i+1 to n
If vertices i-j are connected
If Color(i) == Color(j)
Return REJECT
End
End
End
End
Return ACCEPT
▶ The algorithm takes O(n2 ) time, i.e. polynomial time. Therefore, coloring
problem is in N P.
Example 13-20 (Minimum Spanning Tree Problem)
▶ A minimum spanning tree for a weighted, connected, undirected graph G is a
subgraph that connects all vertices and has minimum weight. For example,

Given a weighted graph G and a number W, is there a tree with weight≤W? Is

the MST problem in N P?
Example 13-20 (Minimum Spanning Tree Problem)
▶ A minimum spanning tree for a weighted, connected, undirected graph G is a
subgraph that connects all vertices and has minimum weight. For example,

Given a weighted graph G and a number W, is there a tree with weight≤W? Is

the MST problem in N P?
▶ We can check each edge in O(1) (or O(n)) steps. Then we will add edge weights
and compare to W. We also have to check that the resulting graph is connected.
Or we should check if there is a cycle. These conditions are equivalent. All of this
is polynomial, so the problem is in N P.
Example 13-21 (Vertex Cover Problem)
▶ Given a graph and an integer k, is there a collection of k vertices such that each
edge is connected to one of the vertices in the collection? For example, for the
following graph, a 3-cover exists: v1 , v4 , v7 . But there is no 2-cover. Is this
problem in N P?
Example 13-21 (Vertex Cover Problem)
▶ INPUT: A graph G with n vertices, m edges. A list of k vertices.
For i=1 to k
Mark all edges of $v_i$.
End
For i=1 to m
If $E_i$ is unmarked
Return REJECT
End
End
Return ACCEPT
Example 13-21 (Vertex Cover Problem)
▶ INPUT: A graph G with n vertices, m edges. A list of k vertices.
For i=1 to k
Mark all edges of $v_i$.
End
For i=1 to m
If $E_i$ is unmarked
Return REJECT
End
End
Return ACCEPT
▶ The complexity of the verifying algorithm is O(n2 ). Therefore Vertex Cover
Problem is in N P.
 The
Most Important Question
in
Theoretical Computer Science
What is the connection between P and NP?
 P = { L | There is a polynomial-time
decider for L }

NP = { L | There is a polynomial-time
verifier for L }

P ⊆ NP
Which Picture is Correct?

P NP
Which Picture is Correct?

P NP
Does P = NP?
 P ≟ NP
● The P ≟ NP question is the most important question in
theoretical computer science.
● With the verifier definition of NP, one way of phrasing
this question is
If a solution to a problem can be checked efficiently,
can that problem be solved efficiently?
● An answer either way will give fundamental insights
into the nature of computation.
 Why This Matters
● The following problems are known to be efficiently
verifiable, but have no known efficient solutions:
● Determining whether an electrical grid can be built to link up
some number of houses for some price (Steiner tree problem).
● Determining whether a simple DNA strand exists that multiple
gene sequences could be a part of (shortest common
supersequence).
● Determining the best way to assign hardware resources in a
compiler (optimal register allocation).
● Determining the best way to distribute tasks to multiple
workers to minimize completion time (job scheduling).
● And many more.
● If P = NP, all of these problems have efficient solutions.
● If P ≠ NP, none of these problems have efficient solutions.
 Why This Matters
● If P = NP:
● A huge number of seemingly difficult problems
could be solved efficiently.
● Our capacity to solve many problems will scale
well with the size of the problems we want to
solve.
● If P ≠ NP:
● Enormous computational power would be required
to solve many seemingly easy tasks.
● Our capacity to solve problems will fail to keep up
with our curiosity.
 The Million-Dollar Question

The Clay Mathematics Institute has offered

a $1,000,000 prize to anyone who proves
or disproves P = NP.
 The Million-Dollar Question

The Clay Mathematics Institute has offered

a $1,000,000 prize to anyone who proves
or disproves P = NP.
Reducibility
 Polynomial-Time Reductions
● Let A and B be languages.
● A polynomial-time reduction from A to
B is a function f : Σ* → Σ* such that
● ∀w ∈ Σ*. (w ∈ A ↔ f(w) ∈ B)
● The function f can be computed in
polynomial time.
● What does this mean?
 Polynomial-Time Reductions
● If f is a polynomial-time reduction from A
to B, then
∀w ∈ Σ*. (w ∈ A ↔ f(w) ∈ B)
● If you want to know whether w ∈ A,
you can instead ask whether f(w) ∈ B.
● Every w ∈ A maps to some f(w) ∈ B.
● Every w ∉ A maps to some f(w) ∉ B.
 Polynomial-Time Reductions
● If f is a polynomial-time reduction from A
to B, then
∀w ∈ Σ*. (w ∈ A ↔ f(w) ∈ B)

Σ* Σ*
 Polynomial-Time Reductions
● If f is a polynomial-time reduction from A
to B, then
∀w ∈ Σ*. (w ∈ A ↔ f(w) ∈ B)

Σ*
A Σ*
 Polynomial-Time Reductions
● If f is a polynomial-time reduction from A
to B, then
∀w ∈ Σ*. (w ∈ A ↔ f(w) ∈ B)

A B

Σ*
A B Σ*
 Polynomial-Time Reductions
● If f is a polynomial-time reduction from A
to B, then
∀w ∈ Σ*. (w ∈ A ↔ f(w) ∈ B)

f(w)
A B
f(w)
Σ*
A B Σ*
 Reductions, Programmatically
● Suppose we have a solver for problem B that's
defined in terms of problem A in this specific
way:
boolean solveProblemA(input) {
return solveProblemB(transform(input));
}
● The reduction from A to B is the function
transform in the above setup: it maps “yes”
answers to A to “yes” answers to B and “no”
answers to A to “no” answers to B.
 Reducibility among Problems
● Suppose that A and B are languages
where there's a polynomial-time
reduction from A to B.
● We'll denote this by writing
A ≤p B
● You can read this aloud as “A polynomial-
time reduces to B” or “A poly-time
reduces to B.”
 Two Key Theorems
● Theorem 1: If A ≤p B and B ∈ P, then A ∈ P.
● Theorem 2: If A ≤p B and B ∈ NP, then A ∈ NP.
● Intuitively, if A ≤p B, then A is “not harder than”
B and B is “at least as hard as” A.
● Proof idea: For (1), show that applying the
reduction from A to B and solving B solves A in
polynomial time. For (2), show that applying the
reduction from A to B lets us use a verifier for B
to verify answers to A.
 Reducibility, Summarized
● A polynomial-time reduction is a way of
transforming inputs to problem A into inputs to
problem B that preserves the correct answer.
● If there is a polynomial-time reduction from A
to B, we denote this by writing A ≤p B.
● Two major theorems:
● Theorem: If B ∈ P and A ≤p B, then A ∈ P.
● Theorem: If B ∈ NP and A ≤p B, then A ∈ NP.
NP-Hardness and NP-Completeness
 Polynomial-Time Reductions
● If A ≤P B and B ∈ P, then A ∈ P.
If L1 ≤P L2 and L2 ∈ NP, then L1 ∈ NP.

P
 Polynomial-Time Reductions
● If A ≤P B and B ∈ P, then A ∈ P.
If L1 ≤P L2 and L2 ∈ NP, then L1 ∈ NP.

P
 Polynomial-Time Reductions
● If A ≤P B and B ∈ P, then A ∈ P.
If L1 ≤P L2 and L2 ∈ NP, then L1 ∈ NP.

P
 Polynomial-Time Reductions
● If A ≤P B and B ∈ P, then A ∈ P.
● If A ≤P B and B ∈ NP, then A ∈ NP.

P
 Polynomial-Time Reductions
● If A ≤P B and B ∈ P, then A ∈ P.
● If A ≤P B and B ∈ NP, then A ∈ NP.

P NP
 Polynomial-Time Reductions
● If A ≤P B and B ∈ P, then A ∈ P.
● If A ≤P B and B ∈ NP, then A ∈ NP.

P NP
 Polynomial-Time Reductions
● If A ≤P B and B ∈ P, then A ∈ P.
● If A ≤P B and B ∈ NP, then A ∈ NP.

P NP
 NP-Hardness
● A language L is called NP-hard if for every A ∈ NP, we have
A ≤P L.

A language in L is called NP-complete iff L is NP-hard and

L ∈ NP.
The class NPC is the set of NP-complete problems.

NP

P
 NP-Hardness
● A language L is called NP-hard if for every A ∈ NP, we have
A ≤P L.

A language in L is called NP-complete iff L is NP-hard and

L ∈ NP.
The class NPC is the set of NP-complete problems.

NP NP-Hard

P
 NP-Hardness
● A language L is called NP-hard if for every A ∈ NP, we have
A ≤P L.

A language in L is called NP-complete iff L is NP-hard and

L ∈ NP.
The class NPC is the set of NP-complete problems.

NP NP-Hard

P
 NP-Hardness
● A language L is called NP-hard if for every A ∈ NP, we have
A ≤P L.
Intuitively:
Intuitively: LLhas
has to
to be
be at
atleast
leastas
as
A language in L ishard NP-complete
calledas every iff
problem L is
inNP-hard
NP, and
since
L ∈ NP. hard as every problem in NP, since
an
analgorithm
algorithmforforLLcan
canbe beused
usedto to
The class NPC is the set of NP-complete problems.
decide
decideall
allproblems
problems inNP.
in NP.

NP NP-Hard

P
 NP-Hardness
● A language L is called NP-hard if for every A ∈ NP, we have
A ≤P L.

A language in L is called NP-complete iff L is NP-hard and

L ∈ NP.
The class NPC is the set of NP-complete problems.

NP NP-Hard

P
 NP-Hardness
● A language L is called NP-hard if for every A ∈ NP, we have
A ≤P L.
What's
A language in L is called NP-complete iff L in
in here?
is NP-hard
What's and
here?
L ∈ NP.
The class NPC is the set of NP-complete problems.

NP NP-Hard

P
 NP-Hardness
● A language L is called NP-hard if for every A ∈ NP, we have
A ≤P L.
● A language in L is called NP-complete if L is NP-hard and
L ∈ NP.
● The class NPC is the set of NP-complete problems.

NP NP-Hard

P
 NP-Hardness
● A language L is called NP-hard if for every A ∈ NP, we have
A ≤P L.
● A language in L is called NP-complete if L is NP-hard and
L ∈ NP.
● The class NPC is the set of NP-complete problems.

NP NP-Hard
NPC
P
 A Feel for NP-Completeness
● If a problem is NP-complete, then under the
assumption that P ≠ NP, there cannot be an
efficient algorithm for it.
● In a sense, NP-complete problems are the
hardest problems in NP.
● All known NP-complete problems are
enormously hard to solve:
● All known algorithms for NP-complete problems
run in worst-case exponential time.
● Most algorithms for NP-complete problems are
infeasible for reasonably-sized inputs.
 NP-Completeness
Theorem: Let A and B be languages. If
A ≤P B and A is NP-hard, then B is NP-hard.
Theorem: Let A and B be languages where
A ∈ NPC and B ∈ NP. If A ≤P B, then
B ∈ NPC.

NP
P
NPC
Sample NP-Complete Problems
● Given a graph, is that graph 3-colorable?
● Given a graph, does that graph contain a Hamiltonian
path?
● Given a set of cities and a set of substation locations,
can you provide power to all the cities using at most k
substations?
● Given a set of jobs and workers who can perform those
tasks in parallel, can you complete all the jobs in at
most T units of time?
● Given a set of numbers S, can you split S into two
disjoint sets with the same sum?
● And many, many more!
 A Feel for NP-Completeness
● There are NP-complete problems in
● formal logic (SAT),
● graph theory (3-colorability),
● operations research (job scheduling),
● number theory (partition problem),
● and basically everywhere.
● You will undoubtedly encounter NP-
complete problems in the real world.
SAT (Boolean Satisfiability Problem)
◼ the first problem that was shown to be
NP-Complete
◼ A given boolean expression,
determining if there exists a truth
assignment to its variables for which the
expression is true is defined as the
satisfiability problem.

3
 SAT
• We’ve tested all possible
assignments.
• There are 5 satisfying truth
assignments for the
expression
and hence it is satisfiable
But the expression is false for all possible truth assignments
and hence it is unsatisfiable.

This takes
If there are n variables in the boolean expression, then the truth table method
would take time to determine if there is a truth assignment that makes
the expression true.
4
3-CNF (conjuction normal form)
◼ (x1 AND x2 AND x3) OR (NOT x1 AND
NOT x2 AND NOT x3)
◼ To be satisfiable, all X1,X2, X3 must be
true or all of them must be false.

3SAT means there are three literals in every clause

5
 A 3-coloring of a graph is a way of coloring its
nodes one of three colors such that no two connected
nodes have the same color.
 The 3-Coloring Problem
● The 3-coloring problem is
Given an undirected graph G,
is there a legal 3-coloring of its
nodes?
● As a formal language:
3COLOR = { ⟨G⟩ | G is an undirected
graph with a legal 3-coloring. }
● This problem is known to be NP-complete
by a reduction from 3SAT.
 3COLOR ∈ NP
● We can prove that 3COLOR ∈ NP by
designing a polynomial-time
nondeterministic TM for 3COLOR.
● M = “On input ⟨G⟩:
● Nondeterministically guess an assignment
of colors to the nodes.
● Deterministically check whether it is a 3-
coloring.
● If so, accept; otherwise reject.”
 A Note on Terminology
● Although 3COLOR and 3SAT both have “3” in
their names, the two are very different
problems.
● 3SAT means “there are three literals in every
clause.” However, each literal can take on only
one of two different values.
● 3COLOR means “every node can take on one of
three different colors.”
● Key difference:
● In 3SAT variables have two choices of value.
● In 3COLOR nodes have three choices of value.