Complexity NP-Complete Problems
2021-03-24 CSC373 Winter 2021 – Sam Toueg 79
Some NP-Complete Problems and
Reduction Techniques
2021-03-24 CSC373 Winter 2021 – Sam Toueg 80
NP-Complete problems and Reductions so far…
Ø SAT
Ø Clique
Ø Independent Set Ø Vertex Cover
Ø Set Cover
Ø IP Feasibility
Ø Coloring
Ø Exact Set Cover
[Cook-Levin Theorem] [SAT ≤? Clique]
[Clique ≤? Independent Set] [Independent Set ≤? Vertex Cover] [Vertex Cover ≤? Set Cover]
[3SAT ≤? IP Feasibility]
[3SAT ≤? Coloring]
[Coloring ≤? Exact Set Cover]
2021-03-24
CSC373 Winter 2021 – Sam Toueg 81
Subset Sum
2021-03-24 CSC373 Winter 2021 – Sam Toueg 82
Subset Sum
• Problem
Ø Input: Set of integers ! = {^W, … , ^3}, integer `
Ø Question: Is there a subset of ! that adds up to exactly `?
• Example
Ø ! = {1, 4, 16, 64, 256, 1040, 1041, 1093, 1284, 1344}
` = 3754
Ø Is there a subset of ! that adds up to 3754?
ØYes!
o 1 + 16 + 64 + 256 + 1040 + 1093 + 1284 = 3754
Claim: Subset Sum is NP-Complete
2021-03-24 CSC373 Winter 2021 – Sam Toueg 83
Subset Sum
• Claim: Subset Sum is in NP Because:
Ø Given a subset !Xof ! that allegedly sums to `
it is easy to verify (in polynomial time in the size of !) whether the elements of !′ indeed sum to `
2021-03-24 CSC373 Winter 2021 – Sam Toueg 84
Subset Sum
• Claim: 3SAT ≤! Subset Sum
Ø Given a 3CNF formula T,
construct an instance (!, `) of Subset Sum such that: T is satisfiable iff ! has a subset that sums to `
Ø How? Build a table as we will show in the next slide: o One column for each variable and each clause of F
o One row for each literal l in F :
• has1initsvariablecolumnand
• has1inthecolumnofeveryclausewhereliterallappears
o Each row represents a decimal number in #
o Intuitively: row (i.e., decimal number) selected = literal set to TRUE
o “Dummy” rows: to make the sum in a clause column 4 if and only if at least one literal is set to TRUE
2021-03-24 CSC373 Winter 2021 – Sam Toueg 85
Subset Sum
• Claim: 3SAT ≤! Subset Sum literals
F = B# ∧ B$ ∧ B%
variables
clauses
2021-03-24 CSC373 Winter 2021 – Sam Toueg
86
Subset Sum
• Claim: 3SAT ≤! Subset Sum literals
F = B# ∧ B$ ∧ B%
variables
clauses
2021-03-24 CSC373 Winter 2021 – Sam Toueg
87
Subset Sum
• Claim: 3SAT ≤! Subset Sum F = B# ∧ B$ ∧ B%
Truth assignment x=T y=T z=T does not satisfy ‘# so
does not satisfy :
220
2021-03-24 CSC373 Winter 2021 – Sam Toueg 88
Tosatisfy:: ≥1≥1≥1
Note : ≤3≤3≤3
Subset Sum
• Claim: 3SAT ≤! Subset Sum F = B# ∧ B$ ∧ B%
Truth assignment x=T y=F z=T satisfies ‘! , ‘” and ‘# so satisfies :
131
2021-03-24 CSC373 Winter 2021 – Sam Toueg
89
Subset Sum
• Claim: 3SAT ≤! Subset Sum F = B# ∧ B$ ∧ B%
• A truth assignment satisfies 9 iff each column:$ ,:” and:* sumsto1,2,or3
• ButwewanttosetonesumW!
• How?
• A small trickJ
2021-03-24
CSC373 Winter 2021 – Sam Toueg
333
111 222
90
Subset Sum
• There is a truth assignment that satisfies 9 iff
• there is a selection of rows
• (each one representing a decimal number)
• thatsumstoW=111444
• (in decimal notation) • Claim: 3SAT ≤! Subset Sum
F = B# ∧ B$ ∧ B%
2021-03-24 CSC373 Winter 2021 – Sam Toueg
91
Partition
2021-03-24 CSC373 Winter 2021 – Sam Toueg 95
Partition
• Problem
Ø Input: Multiset of integers !
Ø Question: Can we partition ! into two subsets that have the same sum?
• Example
Ø ! = {7,1,5,12,5,1,3,9,3,2}
Ø Can we partition ! into some c and d with the same sum?
2021-03-24 CSC373 Winter 2021 – Sam Toueg 96
Partition
• Problem
Ø Input: Multiset of integers !
Ø Question: Can we partition ! into two subsets that have the same sum?
• Example
Ø ! = {7,1,5,12,5,1,3,9,3,2}
Ø Can we partition ! into some c and d with the same sum? ØYes!
Ø c={1,5,5,1,3,9} and d={7,12,3,2}
Ø Each sums to 24
2021-03-24 CSC373 Winter 2021 – Sam Toueg 97
Partition
Claim: Partition is NP-Complete
•
Partition is in NP
Because:
Ø Given any partition c and d of a multiset !, we can verify in polynomial time whether the sum of the integers in c and d is the same
Subset Sum ≤!Partition Because: (proof in the next slide…)
•
2021-03-24 CSC373 Winter 2021 – Sam Toueg 98
Partition
• Claim: Subset Sum ≤! Partition
Ø Given a set ! of integers and an integer ,
[Subset Sum: Is there a subset of ! that sums to ,? ]
Ø Construct the following instance the Partition problem:
o Compute the sum R of the integers in # oBuild#& =#∪{27−R}
o Note:
(1) the integer 27 − R may already be in the set #,
so it may appear more than once in the multiset #& (2)Thesumoftheintegersin#& isR+ 27−R =27
2021-03-24 CSC373 Winter 2021 – Sam Toueg 99
Ø Claim: # has a subset that sums to 7 if and only if the multiset #& can be partition into two sets S and T each summing to 7
Partition
Recap from previous slide:
ØGivenaset!ofintegersandsomeinteger,; ! =g ØBuildmultiset!X =!∪{2,−g},so !′ =2,
Ø Claim: ! has a subset that sums to , if and only if
!X can be partitioned into some c and d each summing to ,
Ø Proof:
o Suppose some subset P ⊆ ! sums to ,. Then !X can be
partitioned into c = P and d = !′ − c each summing to ,
o Suppose !X can be partitioned into c and d each summing to ,.
The integer 2, − g added to build !′ from ! is in c or d
but cannot be in both. Wlog, say it is in c. So d is a subset of !. By assumption d sums to ,. So ! has a subset that sums to ,
2021-03-24 CSC373 Winter 2021 – Sam Toueg 100
Complexity NP-Complete Problems
2021-03-24 CSC373 Winter 2021 – Sam Toueg 1
2021-0C3S-2C4373 Winter 2021 – Sam Toueg
2
CSC373 Winter 2020
3SAT
SAT
Subset sum
Vertex Cover
Independent Set
Clique
Partition
⋮⋮
2C0SC213-7033W-24inter 2021 – Sam Toueg
3
Cook-Levin Theorem
• We did not prove “the first NP-completeness” result namely:
• Theorem: SAT is NP-complete
Ø To prove this, must directly show that
every problem in NP is p-reducible to SAT
Ø To do it, need the concept of Turing Machines
Ø Take CSC463!
2021-03-24 CSC373CSWC3in7t3erW2i0n2te1r-2S0a2m0 Toueg 4
NP versus co-NP
2021-03-24 CSC373 Winter 2021 – Sam Toueg 17
NP versus co-NP – Some examples Example: SAT ∈ NP
Input: a CNF formula ! Question: is ! satisfiable?
Short justification for “YES”: some truth assignment that satisfies ! Is there a short justification for “NO”?
Example: UNSAT ∈ co-NP Input: a CNF formula !
Question: is ! not satisfiable?
Short justification for “NO”: some truth assignment that satisfies ! Is there a short justification for “YES”?
2021-03-24 CSC373 Winter 2021 – Sam Toueg 18
NP vs co-NP
• Complements of each other
Ø NP = efficient verifier (short proof) for YES instances
Ø co-NP = efficient verifier (short proof) for NO instances
Ø If a problem “Does there exist…?” is in NP,
Ø then its complement “Does there not exist…?” is in co-NP, and vice-versa
• Examples:
Ø SAT is in NP (“∃ truth assignment satisfying “?”)
Ø UNSAT is in co-NP (“∄ truth assignment satisfying “?”)
2021-03-24 CSC373 Winter 2021 – Sam Toueg 23
Complexity
2021-03-24 CSC373 Winter 2021 – Sam Toueg 1
By Behnam Esfahbod, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=3532181
NP vs co-NP – Major open questions
• Is NP = co-NP?
• NP ∩ co-NP: set of problems that have an
efficient verifier for both YES and NO instances
• Clearly, P ⊆ NP ∩ co-NP
Ø Because problems in P can be solved in poly-time without any justification or witness
• Is P ⊂ NP ∩ co-NP? That is:
• Is there a problem that is in NP ∩ co-NP but not in P
2021-03-24 CSC373 Winter 2021 – Sam Toueg 27
NP ∩ co-NP
• Linear programming
Ø [Gale–Kuhn–Tucker 1948]: LP is in NP ∩ co-NP
2021-03-24 CSC373 Winter 2021 – Sam Toueg 28
NP ∩ co-NP
• Linear programming
Ø But later, we found out:
Ø [Khachiyan 1979]: LP is in P
2021-03-24 CSC373 Winter 2021 – Sam Toueg 29
NP ∩ co-NP
• Primality testing (“Is $ a prime?”) Ø [Pratt 1975]: PRIMES is in NP ∩ co-NP
o A short NO proof is easy, but a short YES proof relies on some interesting math
2021-03-24
CSC373 Winter 2021 – Sam Toueg 30
NP ∩ co-NP
• Primality testing (“Is $ a prime?”)
Ø But later we found out:
Ø [Agrawal–Kayal–Saxena 2004]: PRIMES is in P o Milestone result!
2021-03-24 CSC373 Winter 2021 – Sam Toueg 31
NP ∩ co-NP
• Factoring (“Does $ have a factor ≤ &?”) Ø FACTOR is in NP ∩ co-NP
o Short YES proof: Just present the factor
o Short NO proof:
• Presenttheentireprimefactorizationof#
• Run AKS algorithm to check that each factor is indeed a prime • Verifythatnoneofthefactorsis≤%
2021-03-24 CSC373 Winter 2021 – Sam Toueg 32
NP ∩ co-NP
• Factoring (“Does $ have a factor ≤ &?”) Ø Major open question: Is FACTOR in P?
o Basis of several cryptographic procedures
Ø Challenge: Factor the following number.
74037563479561712828046796097429573142593188889231289
08493623263897276503402826627689199641962511784399589
43305021275853701189680982867331732731089309005525051
16877063299072396380786710086096962537934650563796359
RSA-704
($30,000 prize if you can factor it)
2021-03-24
CSC373 Winter 2021 – Sam Toueg 33