Complexity NP-Complete Problems
2021-03-10 CSC373 Winter 2021 – Sam Toueg 1
Overview and Motivation
• Efficient algo: polynomial time in the size of its input • We have learned several methods to solve problems
with efficient algorithms:
Ø Divide-and-Conquer
Ø Greedy
Ø Dynamic Programming Ø Maximum Flow
Ø Linear Programming
• What if you must solve a problem where none of the above works, and you are not able to find an efficient algorithm?
• May be you are not alone in your…miseryJ
2021-03-10 CSC373 Winter 2021 – Sam Toueg 2
Overview and Motivation
• There is a large set of well-known problems (this set includes thousands of them!) such that:
Ø Very smart people have tried to solve efficiently and failed
Ø They have been trying for many years: some of these
problems are more than a century old!
Ø If you can solve any one of these problems in polynomial-
time, then you can solve all of them in polynomial-time Note: if you do so, you are smarter than hundreds of famous researchers
who have tried hard before you, and you get a 1,000,000$ prize (to be shared with me who told you about it).
• This is the set of NP-Complete problems
2021-03-10 CSC373 Winter 2021 – Sam Toueg 3
Overview and Motivation
• May be the problem that you are trying to solve efficiently is an NP-Complete problem!
• In the next lectures, we will learn how to recognize whether it is NP-Complete and how you could prove it
• To do so, we will:
Ø Informally define the set of NP-Complete problems
Ø Learn how to use a problem that was already proved to be NP-Complete (by someone elseJ) to prove that another problem (yours) is also NP-Complete
Ø Learn the key tool for doing this:
how to efficiently reduce a problem into another one
e.g, one already known to be NP-Complete e.g., “your” problem
2021-03-10 CSC373 Winter 2021 – Sam Toueg
4
Overview and Motivation
• So why is this stuff this useful?
• If you prove that the problem that you are trying to
solve is NP-Complete, it is probably a good idea to
ostop trying to solve it efficiently, and look for alternatives, like:
otry to find an approximate solution efficiently. We will later see how this could be done…
• It may even help you with your employer…
2021-03-10 CSC373 Winter 2021 – Sam Toueg 5
Your employer and You
I can’t find an efficient algorithm, I guess I am just too dumb.
2021-03-10 CSC373 Winter 2021 – Sam Toueg 6
Your employer and You
I can’t find an efficient algorithm, because no such algorithm is possible!
2021-03-10 CSC373 Winter 2021 – Sam Toueg 7
Your employer and You
I can’t find an efficient algorithm, but neither can all these famous people!
2021-03-10 CSC373 Winter 2021 – Sam Toueg 8
Does your boss really care why you cannot solve it?
2021-03-10 CSC373 Winter 2021 – Sam Toueg 9
Two examples
• To illustrate the key concepts, definitions, and techniques we will use two “decision’’ problems:
• A graph problem called Clique
• A boolean logic problem called SAT
• A decision problem is one with a yes-or-no answer
2021-03-10 CSC373 Winter 2021 – Sam Toueg 10
Clique
2021-03-10 CSC373 Winter 2021 – Sam Toueg 11
Clique
• Undirected graph ! = ($, &)
a
e
Clique of size 3: C={a,d,e} b
because ! has an edge
between every pair of nodes in C
dc
• Clique: Subset of nodes of ! that are completely connected by edges of !
2021-03-10 CSC373 Winter 2021 – Sam Toueg 12
Clique
• Undirected graph ! = ($, &)
a
e
Clique of size 4: C={a,b,c,e} b
because ! has an edge
between every pair of nodes in C
dc
• Clique: Subset of nodes of ! that are completely connected by edges of !
2021-03-10 CSC373 Winter 2021 – Sam Toueg 13
Clique Problem
• Input: Undirected graph ! = ($, &), integer (
• Question: Does ! have a clique of size (?
• Brute force algorithm:
Ø generate every subset ! of ” nodes of #
Ø check whether every pair of nodes of ! is connected by an edge in $
• But this algorithm is exponential…
• Is there a polynomial algorithm for this problem?
2021-03-10 CSC373 Winter 2021 – Sam Toueg 14
SAT and 3SAT
2021-03-10 CSC373 Winter 2021 – Sam Toueg 15
CNF Formulas
• Boolean formula in Conjunctive Normal Form (CNF)
Example:
a “clause’’
!=$̅∨$∨$ ∧$∨$̅∨$ ∧$̅∨$∨$ ∧$̅∨$̅∨$ !”#!”#!”$#$!
• A CNF formula consists of:
Ø Boolean variables %!, %”, … , %#
ØTheir negations %̅ ,%̅ ,…,%̅ !”#
Ø Literal l$ : a variable %$ or its negation %̅$
ØClause * = l! ∨ l” ∨ ⋯∨ l% is a disjunction of literals
ØCNF formula . = *! ∧ *” ∧ ⋯∧ *& is a conjunction of clauses o ‘CNF: Each clause have ‘ literals
o 3CNF example: see ! above
2021-03-10 CSC373 Winter 2021 – Sam Toueg 17
Satisfiability Problems
!=$̅∨$∨$ ∧$∨$̅∨$ ∧$̅∨$∨$ ∧$̅∨$̅∨$ !”#!”#!”$#$!
• A CNF formula ) is satisfiable if
Ø there is a truth assignment (True/False) to the variables %$ under which . evaluates to True
Ø i.e., under which every clause of ! has at least one literal that is True
• 3SAT Problem
Ø Input: a 3CNF formula . Ø Question: is . satisfiable?
2021-03-10 CSC373 Winter 2021 – Sam Toueg 18
Satisfiability Problems
!=$̅∨$∨$ ∧$∨$̅∨$ ∧$̅∨$∨$ ∧$̅∨$̅∨$ !”#!”#!”$#$!
• A CNF formula ) is satisfiable if
Ø there is a truth assignment (True/False) to the variables %$ under which . evaluates to True
Ø i.e., under which every clause of ! has at least one literal that is True
• 3SAT Problem
Ø Input: a 3CNF formula . Ø Question: is . satisfiable?
• Brute force algo: try all possible T/F assignments to the * variables +( of ).But this takes 2) time….
2021-03-10 CSC373 Winter 2021 – Sam Toueg 19
Satisfiability Problems
!=$̅∨$∨$ ∧$∨$̅∨$ ∧$̅∨$∨$ ∧$̅∨$̅∨$ !”#!”#!”$#$!
• A CNF formula ) is satisfiable if
Ø there is a truth assignment (True/False) to the variables %$ under which . evaluates to True
Ø i.e., under which every clause of ! has at least one literal that is True
• 3SAT Problem
Ø Input: a 3CNF formula . Ø Question: is . satisfiable?
• Brute force algo: try all possible T/F assignments to the * variables +( of ). But this takes 2) time….
2021-03-10 CSC373 Winter 2021 – Sam Toueg 20
Satisfiability Problems
!=$̅∨$∨$ ∧$∨$̅∨$ ∧$̅∨$∨$ ∧$̅∨$̅∨$ !”#!”#!”$#$!
• A CNF formula ) is satisfiable if
Ø there is a truth assignment (True/False) to the variables %$ under which . evaluates to True
Ø i.e., under which every clause of ! has at least one literal that is True
• 3SAT Problem
Ø Input: a 3CNF formula . Ø Question: is . satisfiable?
• Is there a polynomial algorithm for SAT or 3SAT?
2021-03-10 CSC373 Winter 2021 – Sam Toueg 21
Polynomial-Time Reductions reducing SAT to Clique
2021-03-10 CSC373 Winter 2021 – Sam Toueg 22
Reducing SAT to Clique
SAT Clique
• Input: a CNF formula !
• Question: is ! satisfiable?
• Input: A graph * = (,, .), an integer ‘
• Question: Does * have a clique of size ‘?
• SAT and Clique seem to be very different problems, but…
• SAT is “polynomially-reducible’’ to Clique, denoted SAT ≤’ Clique:
• We can transform any given CNF formula . (in polynomial time) into a graph and integer (1, “) such that:
. is satisfiable if and only if 1 has a clique of size ”
• So: If we can solve Clique in polynomial-time then we can also solve SAT in polynomial-time
2021-03-10 CSC373 Winter 2021 – Sam Toueg 23
Reducing SAT to Clique
SAT Clique
• Input: a CNF formula !
• Question: is ! satisfiable?
• Input: A graph * = (,, .), an integer ‘
• Question: Does * have a clique of size ‘?
• SAT and Clique seem to be very different problems, but…
• SAT is “polynomially-reducible’’ to Clique, denoted SAT ≤’ Clique:
• We can transform any given CNF formula . (in polynomial time) into a graph and integer (1, “) such that:
. is satisfiable if and only if 1 has a clique of size ”
• Contrapositive: If we can not solve SAT in polynomial-time then we can not solve Clique in polynomial-time
2021-03-10 CSC373 Winter 2021 – Sam Toueg 24
Clique Problem
Claim: SAT ≤0 Clique Proof:
• Given any CNF formula ) with ( clauses, • construct in polytime a graph ! = $, &
such that:
) is satisfiable if and only if ! has a clique of size (
How do we construct 1 from formula .?
2021-03-10 CSC373 Winter 2021 – Sam Toueg
27
Clique Problem
Claim: SAT ≤0 Clique
Proof (by exampleJ):
Given:CNFformula)= +∨10∨2 ∧ +̅∨2̅ ∧(1∨2̅) Question: is ) satisfiable?
Construct:Graph!= $,& asfollows:
Ø one node for every literal of every clause of .
Ø no edges between nodes in the same clause
Ø an edge between every pair of nodes representing literals that are compatible
( ∨ +* ∨ ,
(̅ + ∨∨ ,̅ ,̅
Show: φ is satisfiable ⇔ ! has a clique of size 3 2021-03-10 CSC373 Winter 2021 – Sam Toueg 28
Clique Problem
Claim: SAT ≤0 Clique
Proof (by exampleJ):
Given:CNFformula)= +∨10∨2 ∧ +̅∨2̅ ∧(1∨2̅) Question: is ) satisfiable?
Construct:Graph!= $,& asfollows:
Ø one node for every literal of every clause of .
Ø no edges between nodes in the same clause
Ø an edge between every pair of nodes representing literals that are compatible
( ∨ +* ∨ ,
(̅ + ∨∨ ,̅ ,̅
Suppose: φ is satisfiable
2021-03-10 CSC373 Winter 2021 – Sam Toueg 29
Clique Problem
Claim: SAT ≤0 Clique
Proof (by exampleJ):
Given:CNFformula)= +∨10∨2 ∧ +̅∨2̅ ∧(1∨2̅) Question: is ) satisfiable?
Construct:Graph!= $,& asfollows:
TTT
Ø one node for every literal of every clause of .
Ø no edges between nodes in the same clause
Ø an edge between every pair of nodes representing literals that are compatible
( ∨ +* ∨ ,
(̅ + ∨∨ ,̅ ,̅
Suppose: φ is satisfiable
2021-03-10 CSC373 Winter 2021 – Sam Toueg 30
Clique Problem
Claim: SAT ≤0 Clique
Proof (by exampleJ):
Given:CNFformula)= +∨10∨2 ∧ +̅∨2̅ ∧(1∨2̅) Question: is ) satisfiable?
Construct:Graph!= $,& asfollows:
TTT
Ø one node for every literal of every clause of .
Ø no edges between nodes in the same clause
Ø an edge between every pair of nodes representing literals that are compatible
( ∨ +* ∨ ,
(̅ + ∨∨ ,̅ ,̅
Suppose: φ is satisfiable
2021-03-10 CSC373 Winter 2021 – Sam Toueg 31
Clique Problem
Claim: SAT ≤0 Clique
Proof (by exampleJ):
Given:CNFformula)= +∨10∨2 ∧ +̅∨2̅ ∧(1∨2̅) Question: is ) satisfiable?
Construct:Graph!= $,& asfollows:
TTT
Ø one node for every literal of every clause of .
Ø no edges between nodes in the same clause
Ø an edge between every pair of nodes representing literals that are compatible
( ∨ +* ∨ ,
(̅ + ∨∨ ,̅ ,̅
Suppose: φ is satisfiable
2021-03-10 CSC373 Winter 2021 – Sam Toueg 32
Clique Problem
Claim: SAT ≤0 Clique
Proof (by exampleJ):
Given:CNFformula)= +∨10∨2 ∧ +̅∨2̅ ∧(1∨2̅) Question: is ) satisfiable?
Construct:Graph!= $,& asfollows:
TTT
Ø one node for every literal of every clause of .
Ø no edges between nodes in the same clause
Ø an edge between every pair of nodes representing literals that are compatible
( ∨ +* ∨ ,
(̅ + ∨∨ ,̅ ,̅
Suppose: φ is satisfiable
2021-03-10 CSC373 Winter 2021 – Sam Toueg 33
Clique Problem
Claim: SAT ≤0 Clique
Proof (by exampleJ):
Given:CNFformula)= +∨10∨2 ∧ +̅∨2̅ ∧(1∨2̅) Question: is ) satisfiable?
Construct:Graph!= $,& asfollows:
TTT
Ø one node for every literal of every clause of .
Ø no edges between nodes in the same clause
Ø an edge between every pair of nodes representing literals that are compatible
( ∨ +* ∨ ,
(̅ + ∨∨ ,̅ ,̅
Claim: φ is satisfiable ⇒ ! has a clique of size 3 2021-03-10 CSC373 Winter 2021 – Sam Toueg 34
Clique Problem
Claim: SAT ≤0 Clique
Proof (by exampleJ):
Given:CNFformula)= +∨10∨2 ∧ +̅∨2̅ ∧(1∨2̅) Question: is ) satisfiable?
Construct:Graph!= $,& asfollows:
Ø one node for every literal of every clause of .
Ø no edges between nodes in the same clause
Ø an edge between every pair of nodes representing literals that are compatible
( ∨ +* ∨ ,
(̅ + ∨∨ ,̅ ,̅
Now show: φ is satisfiable ⇐ ! has a clique of size 3 2021-03-10 CSC373 Winter 2021 – Sam Toueg 35
Clique Problem
Claim: SAT ≤0 Clique
Proof (by exampleJ):
Given:CNFformula)= +∨10∨2 ∧ +̅∨2̅ ∧(1∨2̅) Question: is ) satisfiable?
Construct:Graph!= $,& asfollows:
Ø one node for every literal of every clause of .
Ø no edges between nodes in the same clause
Ø an edge between every pair of nodes representing literals that are compatible
( ∨ +* ∨ ,
(̅ + ∨∨ ,̅ ,̅
Suppose: φ. is satisfiable ⇐ ! has a clique of size 3 2021-03-10 CSC373 Winter 2021 – Sam Toueg 36
Clique Problem
Claim: SAT ≤0 Clique
Proof (by exampleJ):
Given:CNFformula)= +∨10∨2 ∧ +̅∨2̅ ∧(1∨2̅) Question: is ) satisfiable?
Construct:Graph!= $,& asfollows:
Ø one node for every literal of every clause of .
Ø no edges between nodes in the same clause
Ø an edge between every pair of nodes representing literals that are compatible
( ∨ +* ∨ ,
(̅ + ∨∨ ,̅ ,̅
Suppose: φ. is satisfiable ⇐ ! has a clique of size 3 2021-03-10 CSC373 Winter 2021 – Sam Toueg 37
Clique Problem
Claim: SAT ≤0 Clique
Proof (by exampleJ):
Given:CNFformula)= +∨10∨2 ∧ +̅∨2̅ ∧(1∨2̅) Question: is ) satisfiable?
Construct:Graph!= $,& asfollows:
Ø one node for every literal of every clause of .
Ø no edges between nodes in the same clause
Ø an edge between every pair of nodes representing literals that are compatible
( ∨ +* ∨ ,
(̅ + ∨∨ ,̅ ,̅
Suppose: φ. is satisfiable ⇐ ! has a clique of size 3 2021-03-10 CSC373 Winter 2021 – Sam Toueg 38
Clique Problem
Claim: SAT ≤0 Clique
Proof (by exampleJ):
Given:CNFformula)= +∨10∨2 ∧ +̅∨2̅ ∧(1∨2̅) Question: is ) satisfiable?
Construct:Graph!= $,& asfollows:
Ø one node for every literal of every clause of .
Ø no edges between nodes in the same clause
Ø an edge between every pair of nodes representing literals that are compatible
( ∨ +* ∨ ,
(̅ + ∨∨ ,̅ ,̅
Suppose: φ. is satisfiable ⇐ ! has a clique of size 3 2021-03-10 CSC373 Winter 2021 – Sam Toueg 39
Clique Problem
Claim: SAT ≤0 Clique
Proof (by exampleJ):
Given:CNFformula)= +∨10∨2 ∧ +̅∨2̅ ∧(1∨2̅) Question: is ) satisfiable?
Construct:Graph!= $,& asfollows:
Ø one node for every literal of every clause of .
Ø no edges between nodes in the same clause
Ø an edge between every pair of nodes representing literals that are compatible
( ∨ +* ∨ ,
(̅ + ∨∨ ,̅ ,̅
Suppose: φ. is satisfiable ⇐ ! has a clique of size 3 2021-03-10 CSC373 Winter 2021 – Sam Toueg 40
Clique Problem
Claim: SAT ≤0 Clique
Proof (by exampleJ):
Given:CNFformula)= +∨10∨2 ∧ +̅∨2̅ ∧(1∨2̅) Question: is ) satisfiable?
Construct:Graph!= $,& asfollows:
Ø one node for every literal of every clause of .
Ø no edges between nodes in the same clause
Ø an edge between every pair of nodes representing literals that are compatible
( ∨ +* ∨ ,
(̅ + ∨∨ ,̅ ,̅
Suppose: φ. is satisfiable ⇐ ! has a clique of size 3 2021-03-10 CSC373 Winter 2021 – Sam Toueg 41
Clique Problem
Claim: SAT ≤0 Clique
Proof (by exampleJ):
Given:CNFformula)= +∨10∨2 ∧ +̅∨2̅ ∧(1∨2̅) Question: is ) satisfiable?
Construct:Graph!= $,& asfollows:
Ø one node for every literal of every clause of .
Ø no edges between nodes in the same clause
Ø an edge between every pair of nodes representing literals that are compatible
( ∨ +* ∨ ,
(̅ + ∨∨ ,̅ ,̅
Suppose: φ. is satisfiable ⇐ ! has a clique of size 3 2021-03-10 CSC373 Winter 2021 – Sam Toueg 42
Clique Problem
Claim: SAT ≤0 Clique
Proof (by exampleJ):
Given:CNFformula)= +∨10∨2 ∧ +̅∨2̅ ∧(1∨2̅) Question: is ) satisfiable?
Construct:Graph!= $,& asfollows:
TTT
Ø one node for every literal of every clause of .
Ø no edges between nodes in the same clause
Ø an edge between every pair of nodes representing literals that are compatible
( ∨ +* ∨ ,
(̅ + ∨∨ ,̅ ,̅
Suppose: φ. is satisfiable ⇐ ! has a clique of size 3 2021-03-10 CSC373 Winter 2021 – Sam Toueg 43
Clique Problem
Claim: SAT ≤0 Clique
Proof (by exampleJ):
Given:CNFformula)= +∨10∨2 ∧ +̅∨2̅ ∧(1∨2̅) Question: is ) satisfiable?
Construct:Graph!= $,& asfollows:
Ø one node for every literal of every clause of .
Ø no edges between nodes in the same clause
Ø an edge between every pair of nodes representing literals that are compatible
( ∨ +* ∨ ,
(̅ + ∨∨ ,̅ ,̅
We proved: φ is satisfiable ⇐ ! has a clique of size 3 2021-03-10 CSC373 Winter 2021 – Sam Toueg 44
Clique Problem
Claim: SAT ≤0 Clique
Proof (by exampleJ):
Given:CNFformula)= +∨10∨2 ∧ +̅∨2̅ ∧(1∨2̅) Question: is ) satisfiable?
Construct:Graph!= $,& asfollows:
Ø one node for every literal of every clause of .
Ø no edges between nodes in the same clause
Ø an edge between every pair of nodes representing literals that are compatible
( ∨ +* ∨ ,
(̅ + ∨∨ ,̅ ,̅
So: φ is satisfiable ⇔ ! has a clique of size 3
2021-03-10 CSC373 Winter 2021 – Sam Toueg 45
Decision Problems
2021-03-10 CSC373 Winter 2021 – Sam Toueg 46
Decision problems
• Problems with a yes-or-no answer to a question • For example:
Ø Clique, SAT, 3SAT
Ø Hamilton Cycle
oInput:Agraph*= ,,.
o Question: Does * have a cycle that traverses every node exactly once?
Ø Partition
o Input: A list 1 of integers
o Question: Can we partition 1 into two lists that sum the same?
2021-03-10 CSC373 Winter 2021 – Sam Toueg 47
Decision versus Optimization Problems
• Many (but not all) decision problems that we will consider have an optimization version, for example:
• Clique (decision problem)
Ø Input: Undirected graph 1 = (#, $), integer ” Ø Question: Does 1 have a clique of size “?
• An optimization version:
Ø Input: Undirected graph 1 = (#, $)
Ø Output: Maximum ” such that 1 have a clique of size “?
• Typically, an optimization version is at least as hard to solve as a decision version
• But sometimes not much harder…
Ø If can solve (decision) Clique in % time
Ø then can solve the optimization version in % log J time J 2021-03-10 CSC373 Winter 2021 – Sam Toueg 48
Decision versus Optimization Problems
• Clique (decision problem)
Ø Input: Undirected graph 1 = (#, $), integer ” Ø Question: Does 1 have a clique of size “?
• An optimization version:
Ø Input: Undirected graph 1 = (#, $)
Ø Output: Maximum ” such that 1 have a clique of size “?
• A harder (?) optimization version: Ø Input: Undirected graph 1 = (#, $) Ø Output: Maximum-size clique of 1
• Is this really much harder that the previous two problems? Think …J
2021-03-10 CSC373 Winter 2021 – Sam Toueg 49
Polynomial-time reductions
2021-03-10 CSC373 Winter 2021 – Sam Toueg 50
Polynomial-Time Reductions • Let R and S be two decision problems
• [Karp]: R is p-reducible to S, denoted R ≤0 S,
if we can transform any instance + of R in polynomial time into an instance 1 of S with the same answer, i.e.:
+ is a YES instance of R ⇔ 1 is a YES instance of S
• [Cook]: R is p-reducible to S, denoted R ≤0 S, if, given an oracle (subroutine) for solving S, we can solve R in polynomial time
Ø Note: To solve K using the oracle for L in polynomial time, we can call the oracle a polynomial number of times,
and do some additional polynomial-time computation
• Karp’s reduction is a restricted case of Cook’s reduction,
where the oracle for S is used only once
2021-03-10 CSC373 Winter 2021 – Sam Toueg 51
Polynomial-Time Reductions • Let R and S be two decision problems
• [Karp]: R is p-reducible to S, denoted R ≤0 S,
if we can transform any instance + of R in polynomial time into an instance 1 of S with the same answer, i.e.:
+ is a YES instance of R ⇔ 1 is a YES instance of S
• [Cook]: R is p-reducible to S, denoted R ≤0 S, if, given an oracle (subroutine) for solving S, we can solve R in polynomial time
Ø Note: To solve K using the oracle for L in polynomial time, we can call the oracle a polynomial number of times,
and do some additional polynomial-time computation
• Here will mostly see and use Karp’s type of reduction 2021-03-10 CSC373 Winter 2021 – Sam Toueg 52
Polynomial-Time Reductions
• [Karp]: R ≤0 S if we can transform any instance + of R,
in polynomial time, into an instance 1 of S such that: + is a YES instance of R ⇔ 1 is a YES instance of S
• Claim: If R ≤0 S and S can be solved in polynomial time, then R can also be solved in polynomial time
• Proof: To solve any instance + of R:
(a) transform % into an instance M of L with the same answer
(b) solve instance M of L and return the YES or NO answer Ø Both (a) and (b) take polynomial-time
• This claim also holds for Cook’s type of reduction! 2021-03-10 CSC373 Winter 2021 – Sam Toueg 53
Polynomial-Time Reductions
• Claim: If R ≤0 S and S can be solved in polynomial time,
then R can also be solved in polynomial time
• Using this claim to prove the hardness of a problem:
Ø Suppose a problem K is already known to be “hard’’ because K can not be solved in polynomial-time
Ø How can I prove that another problem L is also “hard’’, i.e., that L can not be solved in polynomial-time?
Ø One possible way: show that K ≤’ L
2021-03-10 CSC373 Winter 2021 – Sam Toueg 54