Complexity NP-Complete Problems
2021-03-15 CSC373 Winter 2021 – Sam Toueg 1
Recall: 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 is “polynomially-reducible’’ to Clique, denoted SAT ≤! Clique: • We can transform any given CNF formula 𝜑 (in polynomial time)
into a graph and integer (𝐺, 𝑘) such that: • So:
Ø If we can solve Clique in polynomial-time then we can also solve SAT in polynomial-time
Ø If we can not solve SAT in polynomial-time
then we can not solve Clique in polynomial-time
𝜑 is satisfiable if and only if 𝐺 has a clique of size 𝑘
2021-03-15 CSC373 Winter 2021 – Sam Toueg 2
Clique Problem
Claim: SAT ≤* Clique
Proof (by exampleJ):
Given:CNFformula𝜑= 𝑥∨𝑦&∨𝑧 ∧ 𝑥̅∨𝑧̅ ∧(𝑦∨𝑧̅)
Question: is 𝜑 satisfiable?
Constructgraph𝐺= 𝑉,𝐸 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-15 CSC373 Winter 2021 – Sam Toueg 3
Clique Problem
Claim: SAT ≤* Clique
Proof (by exampleJ):
Given:CNFformula𝜑= 𝑥∨𝑦&∨𝑧 ∧ 𝑥̅∨𝑧̅ ∧(𝑦∨𝑧̅)
Question: is 𝜑 satisfiable?
Constructgraph𝐺= 𝑉,𝐸 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-15 CSC373 Winter 2021 – Sam Toueg 4
Clique Problem
Claim: SAT ≤* Clique
Proof (by exampleJ):
Given:CNFformula𝜑= 𝑥∨𝑦&∨𝑧 ∧ 𝑥̅∨𝑧̅ ∧(𝑦∨𝑧̅)
Question: is 𝜑 satisfiable?
Constructgraph𝐺= 𝑉,𝐸 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-15 CSC373 Winter 2021 – Sam Toueg 5
Clique Problem
Claim: SAT ≤* Clique
Proof (by exampleJ):
Given:CNFformula𝜑= 𝑥∨𝑦&∨𝑧 ∧ 𝑥̅∨𝑧̅ ∧(𝑦∨𝑧̅)
Question: is 𝜑 satisfiable?
Constructgraph𝐺= 𝑉,𝐸 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-15 CSC373 Winter 2021 – Sam Toueg 6
Clique Problem
Claim: SAT ≤* Clique
Proof (by exampleJ):
Given:CNFformula𝜑= 𝑥∨𝑦&∨𝑧 ∧ 𝑥̅∨𝑧̅ ∧(𝑦∨𝑧̅)
Question: is 𝜑 satisfiable?
Constructgraph𝐺= 𝑉,𝐸 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-15 CSC373 Winter 2021 – Sam Toueg 7
Clique Problem
Claim: SAT ≤* Clique
Proof (by exampleJ):
Given:CNFformula𝜑= 𝑥∨𝑦&∨𝑧 ∧ 𝑥̅∨𝑧̅ ∧(𝑦∨𝑧̅)
Question: is 𝜑 satisfiable?
Constructgraph𝐺= 𝑉,𝐸 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-15 CSC373 Winter 2021 – Sam Toueg 8
Clique Problem
Claim: SAT ≤* Clique
Proof (by exampleJ):
Given:CNFformula𝜑= 𝑥∨𝑦&∨𝑧 ∧ 𝑥̅∨𝑧̅ ∧(𝑦∨𝑧̅)
Question: is 𝜑 satisfiable?
Constructgraph𝐺= 𝑉,𝐸 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-15 CSC373 Winter 2021 – Sam Toueg 9
Clique Problem
Claim: SAT ≤* Clique
Proof (by exampleJ):
TTT
Constructgraph𝐺= 𝑉,𝐸 asfollows:
Given:CNFformula𝜑= 𝑥∨𝑦&∨𝑧 ∧ 𝑥̅∨𝑧̅ ∧(𝑦∨𝑧̅)
Question: is 𝜑 satisfiable?
Ø 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-15 CSC373 Winter 2021 – Sam Toueg 10
Clique Problem
Claim: SAT ≤* Clique
Proof (by exampleJ):
Given:CNFformula𝜑= 𝑥∨𝑦&∨𝑧 ∧ 𝑥̅∨𝑧̅ ∧(𝑦∨𝑧̅)
Question: is 𝜑 satisfiable?
Constructgraph𝐺= 𝑉,𝐸 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-15 CSC373 Winter 2021 – Sam Toueg 11
Polynomial-Time Reductions • Let 𝐴 and 𝐵 be two decision problems
• Karp : 𝐴 ≤* 𝐵 if we can transform in polynomial time any instance 𝑥 of 𝐴 into an instance 𝑦 of 𝐵 such that:
• 𝐴 ≤* 𝐵 implies:
Ø If we can solve 𝐵 in polynomial-time
then we can also solve 𝐴 in polynomial-time Ø If we can not solve 𝐴 in polynomial-time
then we can not solve 𝐵 in polynomial-time
2021-03-15 CSC373 Winter 2021 – Sam Toueg 12
𝑥 is a YES instance of 𝐴 ⇔ 𝑦 is a YES instance of 𝐵
Efficient Verifiers
2021-03-15 CSC373 Winter 2021 – Sam Toueg 13
Efficient Verifiers
• Intuitively: A decision problem 𝑃 has an efficient verifier if every YES instance 𝑥 of 𝑃 has a short “justification’’ that can be used to efficiently verify that 𝑥 is indeed a YES instance of 𝑃
• Clique
Ø Input: Undirected graph 𝐺 = (𝑉, 𝐸), integer 𝑘 Ø Question: Does 𝐺 have a clique of size 𝑘?
• If someone claims that 𝐺 has a clique of size 𝑘:
o they can give a set of nodes 𝐶 (which is allegedly a clique of size 𝑘 of 𝐺)
as a “justification”, and
o there is a verifier algorithm that can check, in polynomial-time
(in the size of 𝐺 and 𝐶), whether the given 𝐶 is indeed a 𝑘-clique of 𝐺.
The verifier does so by checking whether:
(a) 𝐶 is indeed a set of 𝑘 nodes of 𝐺, and
(b) 𝐺 has an edge between every pair of nodes in 𝐶
2021-03-15 CSC373 Winter 2021 – Sam Toueg 14
Efficient Verifiers
• Intuitively: A decision problem 𝑃 has an efficient verifier if every YES instance 𝑥 of 𝑃 has a short “justification’’ that can be used to efficiently verify that 𝑥 is indeed a YES instance of 𝑃
• SAT
Ø Input: a CNF formula 𝜑
Ø Question: Is 𝜑 satisfiable?
• If someone claims that 𝜑 is satisfiable
Ø they can give a specific truth assignment to the variables of 𝜑 that
allegedly makes 𝜑 True, as a “justification”
Ø a verifier algorithm can then check, in polynomial-time
in the size of 𝜑, whether 𝜑 is indeed True under the given truth assignment
2021-03-15 CSC373 Winter 2021 – Sam Toueg 15
Efficient Verifier (a more precise definition)
A decision problem 𝑃 has an efficient verifier if there is a
polynomial-time “verifier’’ algorithm 𝐴(-,-) such that: • For all YES instances 𝑥 of 𝑃:
there is a “justification’’ 𝑦, of polynomial size in the size of 𝑥, such that running 𝐴 on (𝑥,𝑦) returns “YES”
• For all NO instances 𝑥 of 𝑃:
running 𝐴 on (𝑥,𝑦) returns “NO” on every 𝑦
A “justification” is also called “witness”, “certificate” or “advice”
2021-03-15 CSC373 Winter 2021 – Sam Toueg 16
Efficient Verifiers
• Any decision problem that can be solved by
a polynomial- time algorithm has an efficient verifier: one that does not need the help of a “justification”!
• Example: Minimum Spanning Tree (decision version)
Ø Input: Graph 𝐺 = (𝑉, 𝐸), with edge weights 𝑤(), and integer 𝑊 Ø Question: Does 𝐺 have an MST with cost at most 𝑊?
Verifier algorithm:
Ø Run Kruskal’s algorithm to find the cost of an MST of 𝐺 (this takes polynomial-time)
Ø return YES if this cost is at most 𝑊, and returns NO otherwise
Ø This verifier does not need to be given an “alleged” MST of 𝐺
of cost at most 𝑊 to return YES or NO to the problem’s question! 2021-03-15 CSC373 Winter 2021 – Sam Toueg 18
Efficient Verifiers
• Some decision problems may not have an efficient verifier
• Consider the ”negation” (complement) of Clique
• Clique-Freedom:
Ø Input: Graph 𝐺 = (𝑉, 𝐸), and integer 𝑘
Ø Question: Does 𝐺 not have a clique of size 𝑘? If a graph 𝐺 does not have a clique of size 𝑘,
is there always a short, easy-to-verify ”justification”?
It is not known whether Clique-Freedom has an efficient verifier!
2021-03-15 CSC373 Winter 2021 – Sam Toueg 19
Efficient Verifiers
• Some decision problems may not have an efficient verifier
• Consider the ”negation” (complement) of SAT
• UNSAT:
Ø Input: a CNF formula 𝜑
Ø Question: is 𝜑 not satisfiable? If a formula 𝜑 is not satisfiable,
is there always a short, easy-to-verify ”justification”?
It is not known whether UNSAT or Clique-Freedom have efficient verifiers!
2021-03-15 CSC373 Winter 2021 – Sam Toueg 20
Efficient Verifiers
• Some decision problems may not have an efficient verifier • TAUTOLOGY:
Ø Input: a CNF formula 𝜑
Ø Question: is it the case that all truth assignments satisfy 𝜑?
If a formula 𝜑 is a tautology,
is there always a short, easy-to-verify ”justification”?
It is not known whether TAUTOLOGY has an efficient verifier!
2021-03-15 CSC373 Winter 2021 – Sam Toueg 21
Efficient Verifiers
• Some decision problems do not have an efficient verifier • Consider the Turing Machine Halting Problem
Ø Input: a Turing Machine M
Ø Question: If M is started on an empty input, does it ever halt?
• This famous problem is known to be undecidable So it certainly does not have an efficient verifierJ
2021-03-15 CSC373 Winter 2021 – Sam Toueg 22
We can now (finally!) define PandNP
and NP-Completeness
2021-03-15 CSC373 Winter 2021 – Sam Toueg 23
P and NP Problems
• Efficient/efficiently = polynomial-time in the input size
• NP = {Decision problems that have efficient verifiers}
• NP includes SAT, 3SAT, Clique, etc…
• P= {Decision problems that can be solved efficiently} • As we noted before, any problem that can be solved
efficiently has (by definition) an efficient verifier, so:
P ⊆ NP
2021-03-15 CSC373 Winter 2021 – Sam Toueg 25
NP-Hard and NP-Complete Problems • A problem 𝑃 is NP-Hard if
every problem 𝑃, in NP is p-reducible to 𝑃, that is: ∀𝑃, ∈ NP: 𝑃, ≤* 𝑃
Ø Intuitively, 𝑃 is at least as hard to solve as any problem in NP (including SAT, 3SAT, Clique, etc…) because if you can solve 𝑃 in polynomial time
then you can solve every other problem in NP also in polynomial time
• A problem 𝑃 is NP-Complete if it is NP and it is NP-Hard Ø Intuitively, 𝑃 is hardest among all the problems in NP
• A priori, it is not clear that an NP-Complete problem actually exists
2021-03-15 CSC373 Winter 2021 – Sam Toueg 26
NP-Hard and NP-Complete Problems
• Cook-Levin Theorem: SAT is NP-Complete!
• Proof:
(a) SAT is in NP (because it has an efficient verifier) (b) SAT is NP-Hard: ∀𝑃 ∈ NP, 𝑃 ≤! SAT
The proof of part (b) is given in CSC463; if we have time, we will give the general idea later…
• Corollary:
(a) if SAT ∉ P then P ≠ NP (b) if SAT ∈ P then P = NP
SAT ∈ P iff P = NP
2021-03-15 CSC373 Winter 2021 – Sam Toueg 27
NP-Hard and NP-Complete Problems
• Cook-Levin Theorem: SAT is NP-Complete
• Corollary: SAT ∈ P iff P = NP
• That is: we can solve SAT in polynomial time, iff we can also solve every problem in NP in polynomial time.
• But there are thousands of well-studied problems in NP that have no known polynomial-time solutions despite repeated attempts, over decades, by very smart people!
• This is why most people believe that SAT (or any other NP- Complete problem) does not have a polynomial-time algorithm, i.e., that SAT ∉ P and P ≠ NP
• But nobody actually knows whether P = NP or P ≠ NP 2021-03-15 CSC373 Winter 2021 – Sam Toueg 28
𝑃 = 𝑁𝑃?
• Lance Fortnow in his article on P and NP in Communications of the ACM, Sept 2009
“The P versus NP problem has gone from an interesting problem related to logic to perhaps the most fundamental and important mathematical question of our time, whose importance only grows as computers become more powerful and widespread.”
2C0SC213-7033W-15inter 2021 – Sam Toueg 29
Millenium Problems
• Award of $1,000,000 for each problem by Clay Math institute
1. Birch and Swinnerton-Dyer Conjecture
2. Hodge Conjecture
3. Navier-Stokes Equations
4. P=NP?
5. Poincare Conjecture (Solved)1
6. Riemann Hypothesis
7. Yang-Mills Theory
1Solved by Grigori Perelman (2003): Prize unclaimed
Claim: Worth >> $1M
2C0SC213-7033W-15inter 2021 – Sam Toueg
30
And now back to Clique!
• SAT is NP-Complete, but what about Clique?
• Theorem: Clique is NP-Complete • Proof:
(1) Clique is in NP (bcs it has an efficient verifier)
(2) Clique is NP-Hard because
• By Cook-Levin, SAT is NP-Hard: ∀𝑃 ∈ NP: 𝑃 ≤! SAT
• We previously proved: SAT ≤! Clique
• By chaining the two results: ∀𝑃 ∈ NP: 𝑃 ≤! Clique
• Note: we proved that Clique is NP-Hard by p-reducing a known NP-Hard problem to it!
2021-03-15 CSC373 Winter 2021 – Sam Toueg 31
Proving a problem to be NP-Complete
• If you suspect a problem 𝑃 cannot be solved efficiently:
Ø See if 𝑃 is one of the known NP-Complete problem (there are thousands of them!); if this search fails,
Ø Try to prove 𝑃 is NP-Complete, by showing that:
(a) 𝑃 is in NP (that is, it has an efficient verifier)
(b) Some known NP-Complete problem 𝑃′ is p-reducible to 𝑃
• We will do many reductions to:
Ø Expand your list of known NP-Complete problems Ø Help you gain experience on reductions
2021-03-15 CSC373 Winter 2021 – Sam Toueg 32