Chapter 11

Limitations of Algorithm Power

“Introduction to the Design and Analysis of Algorithms”

Anany Levitin, 3rd edition, Pearson Education, Inc.
1
 Lower Bounds
• Lower bound
– an estimate on a minimum amount of work needed to solve a given
problem.
– indicates the best possible efficiency any algorithm (for this problem)
can have.
• Lower bound can be
– an exact count (a minimum number of times a basic operation needs
to be executed).
– an efficiency class ()
2
 Lower Bounds
• Tight lower bound: there exists an algorithm with the same
efficiency as the lower bound.

Problem Lower bound Tightness

sorting (nlog n) yes
searching in a sorted array (log n) yes
element uniqueness (nlog n) yes
n-digit integer multiplication (n) unknown
multiplication of n-by-n matrices (n2) unknown

3
 Decision Trees
• Decision tree — a convenient model of algorithms involving
comparisons in which:
– internal nodes represent comparisons.
– leaves represent outcomes.
• Any comparison-based sorting algorithm can be represented
by a decision tree.
• Sorting algorithms that are comparison based:
– bubble-sort, selection-sort, insertion-sort, heap-sort, merge-sort,
quick-sort,…

4
 Decision Trees
• Decision tree for 3-element insertion sort:
abc
yes no
a<b

abc bac
yes no yes no
b< c a<c

a<b<c acb bca

b<a<c
yes no yes no
a<c b<c

a<c<b c<a<b b<c<a c<b<a

5
 Decision Trees and Sorting Algorithms
• Number of leaves (outcomes) is n!
• For any binary tree with n! leaves and height h,
h  log2n! 
• The number of comparisons in the worst case is  log2n! for
any comparison-based sorting algorithm.
• log2n!  n log2n (Stirling’s formula)
• This lower bound is tight (mergesort).
6
 Dealing with Hard Problems
• What to do when we find a problem that looks hard…

I couldn’t find a polynomial-time algorithm;

I guess I’m too dumb.
7
 Dealing with Hard Problems
• Sometimes we can prove a strong lower bound… (but not
usually)

I couldn’t find a polynomial-time algorithm,

because no such algorithm exists!
8
 Dealing with Hard Problems
• NP-completeness lets us show collectively that a problem is
hard.

I couldn’t find a polynomial-time algorithm,

but neither could all these other smart people.
9
 Problem Types: Optimization and Decision

• Optimization problem: find a solution that maximizes or

minimizes some objective function.
• Decision problem: answer yes/no to a question.
• Many problems have decision and optimization versions.
e.g.: Traveling salesman problem
– optimization: find Hamiltonian cycle of minimum length.
– decision: find Hamiltonian cycle of length  m.

10
 Class P
• Class P is a class of decision problems that can be solved in
polynomial time by algorithms.
• Examples:
– Searching
– Element uniqueness
– Graph connectivity
– Graph acyclicity

11
 Class NP
• A nondeterministic polynomial algorithm is an two-stage
procedure that takes as its input an instance I of a decision
problem:
– Nondeterministic (“guessing”) stage: A random string S is generated
that can be thought as a candidate solution to the given instance I.
– Deterministic (“verification”) stage: Check whether this candidate
solution is correct in polynomial time.
• Class NP is the class of decision problems that can be solved by
nondeterministic polynomial algorithms.
12
 Example
• CNF-sat Problem: Is a Boolean formula in its conjunctive normal form
(CNF) satisfiable, i.e., are there values of its variables that make it true?
• This problem is in NP.
• Nondeterministic algorithm:
– Guess truth assignment.
– Substitute the values into the CNF formula to see if it evaluates to true.
• Example:
(A + ¬B + ¬C) ∙ (A + B) ∙ (¬B + ¬D + E) ∙ (¬D + ¬E)

13
 Example
• A Boolean circuit is a circuit of AND, OR, and NOT gates.
• CIRCUIT-SAT problem is to determine if there is an assignment of 0’s and 1’s to a
circuit’s inputs so that the circuit outputs 1.
• This problem is in NP.
Inputs:
Logic Gates: 0 1 0
1
NOT 1
1
0 1 Output:

OR 1
0
1 0 1

AND

14
 What problems are in NP?
• All the problems in P can also be solved by nondeterministic
polynomial algorithms, so we have:
P  NP
• Open question: P = NP ?
• Most researchers believe that P and NP are different.

15
 NP-Complete Problems
• A decision problem D is NP-complete if it is as hard as any problem in
NP, i.e.,
– D is in NP.
– Every problem in NP is polynomially reducible to D.
• In 1971, Stephen Cook proved that CNF-sat is NP-complete.
• Other NP-complete problems can be obtained through polynomial-time
reductions from a known NP-complete problem.

NP NP-Complete
poly-time D

16
 NP-Complete Problems
• Known problems:
– Circuit-SAT, CNF-SAT
– 3CNF-SAT(3SAT)
– Clique
– Subset-Sum
– Vertex Cover
– Hamiltonian cycle
– Traveling salesman
– 0/1 knapsack problem
– graph coloring
– etc.

17
 3CNF-SAT
• 3CNF-SAT (3SAT) problem: a Boolean formula S that is in
Conjunctive Normal Form (CNF) with each clause in S having
exactly three literals is satisfiable.
• e.g., (a+b+¬d)∙(¬a+¬c+e)∙(¬b+d+e)∙(a+¬c+¬e)
• 3CNF-SAT is in NP.
• CNF-SAT problem can be reduced to this problem in polynomial
time.

18
 Vertex Cover
• A vertex cover of graph G is a subset W of vertices, such that, for
every edge (a, b) in the graph, a is in W or b is in W.
• Each vertex “covers” its incident edges.
• A vertex cover covers all the edges of the graph.
• VERTEX-COVER problem: Given a graph G and an integer K, does G
have a vertex cover of size at most K?
• VERTEX-COVER is in NP: Non-deterministically choose a subset W and
verify that the size of W is at most K and every edge is covered by W.
19
 Vertex-Cover
• Reducing 3CNF-SAT to VERTEX-COVER.
– Let S be a Boolean formula in CNF with each clause having 3
literals.
– For each variable a, create a vertex for a and ¬a, and connect
these two:
a ¬a

– For each clause, (e.g., (¬a+b+c)), create a triangle and connect

these three vertices. b

¬a c 20
 Vertex Cover
• Completing the construction
• Connect each literal in a clause triangle to its copy in a variable pair.
• e.g., a clause (¬a+b+c)
a ¬a b ¬b c ¬c

• Let n=# of variables.

• Let m=# of clauses.
• Set K=n+2m.
21
 Vertex Cover
• Example: (a + b + c) ∙ (¬a + b + ¬c) ∙ (¬b + ¬c + ¬d)
– n = 4; m = 3;
• This graph has a vertex cover of size K = 4 + 6 = 10 if and only if the formula is
satisfiable.
a ¬a b ¬b c ¬c d ¬d

12 22 32

11 13 21 23 31 33
22
 Example: (a+b+c)(¬a+b+¬c)(¬b+¬c+¬d) = true

when a = true, b = true, c = false, d = false

a ¬a b ¬b c ¬c d ¬d

12 22 32

11 13 21 23 31 33

23
 Clique
• A clique of a graph G is a subset C of vertices that are fully-connected
(every pair of vertices in C has an edge in G).
• CLIQUE problem: Given a graph G and an integer K, is there a clique in G
of size at least K?
• CLIQUE is in NP: non-deterministically choose a subset C and check that
the size of C is at least K and every pair of vertices in C has an edge in G.

24
 Example

This graph has

a clique of size 5.

25
 CLIQUE
• Reducing from VERTEX-COVER.
• A graph G has a vertex cover of size K if and only if its complement has a clique
of size n-K.
– The complement of a graph G contains exactly those edges that are not in G.

G G’
26
 CLIQUE is NP-Complete
• Clique is in NP.
• Vertex Cover can be reduced to Clique in polynomial time.
• Therefore Clique is NP-complete.

27
 Some Other NP-Complete Problems

• SUBSET-SUM: Given a set of integers and a distinguished integer K, is

there a subset of integers that sum to K?
– NP-complete by reduction from VERTEX-COVER.
• 0/1 Knapsack: Given a collection of items with weights and values, is
there a subset of weights at most W and value at least K?
– NP-complete by reduction from SUBSET-SUM.

28
 Some Other NP-Complete Problems

• Hamiltonian-Cycle: Given a graph G, is there a cycle in G that visits each

vertex exactly once?
– NP-complete by reduction from VERTEX-COVER.
• Traveling Salesman Problem: Given a complete weighted graph G, is
there a cycle that visits each vertex and has a total cost at most K?
– NP-complete by reduction from Hamiltonian-Cycle.

29
 NP-Complete Problems
• The NP-complete problems are the hardest problem in class
NP.
• If we could solve just one NP-complete problem in polynomial
time, then every problem in NP can be solved in polynomial
time.
• That is, if an NP-complete problem is solvable in polynomial
time, then P = NP.

30
 Millennium Prize
• In 1998, the Clay Mathematics Institute (CMI) announced that
$1,000,000 will be awarded to whoever solves the P vs NP
problem.
• [Link]

31