CS21 Decidability and Tractability
Lecture 22 February 26, 2024
• NP-complete problems: independent set, vertex cover, clique…
• NP-complete problems: Hamilton path and cycle,Traveling Salesperson Problem
Copyright By PowCoder代写 加微信 powcoder
• NP-complete problems: Subset Sum
• NP-complete problems: NAE-3-SAT, max cut
February 26, 2024 CS21 Lecture 22 2
SUBSET-SUM is NP-complete
Theorem: the following language is NP-
SUBSET-SUM = {(S = {a1, a2, a3, …, ak}, B) :
polynomially large B • Proof: (unless we want to
our reduction had better produce super-
there is a subset of S that sums to B}
– Part 1: SUBSET-SUM ∈ NP. Proof? – Part 2: SUBSET-SUM is NP-hard.
• reduce from?
February 26, 2024 CS21 Lecture 22 3
prove P=NP)
SUBSET-SUM is NP-complete • We are reducing from the language:
3SAT = { φ : φ is a 3-CNF formula that has a satisfying assignment }
to the language:
SUBSET-SUM = {(S = {a1, a2, a3, …, ak}, B) : there is a subset of S that sums to B}
February 26, 2024 CS21 Lecture 22 4
SUBSET-SUM is NP-complete • φ=(x1∨x2 ∨¬x3)∧(¬x1 ∨x4 ∨x3)∧…∧(…)
• Need integers to play the role of truth assignments
• For each variable xi include two integers in our set S:
– xiTRUE and xiFALSE
• set B so that exactly one must be in sum February 26, 2024 CS21 Lecture 22 5
SUBSET-SUM is NP-complete
x1TRUE x1FALSE x2TRUE x2FALSE
=1000…0 • every choice of one =1000…0 from each =0100…0 (xiTRUE,xiFALSE) pair
=0100…0 sums to B
• every subset that
… xmTRUE
sums to B must choose one from each (xiTRUE,xiFALSE) pair
=0000…1 xmFALSE =0000…1 B =1111…1
February 26, 2024 CS21 Lecture 22 6
SUBSET-SUM is NP-complete
• φ=(x1∨x2 ∨¬x3)∧(¬x1 ∨x4 ∨x3)∧…∧(…)
• Need to force subset to “choose” at least
one true literal from each clause
– add more digits
– one digit for each clause
– set B to force each clause to be satisfied.
February 26, 2024 CS21 Lecture 22 7
SUBSET-SUM is NP-complete
• φ=(x1∨x2 ∨¬x3)∧(¬x1 ∨x4 ∨x3)∧…∧(…)
x3FALSE …:
B =1111…1? ? ?
clause 1 clause 2 clause 3
: clause k
=1000…01 =1000…00 =0100…01 =0100…00 =0010…00 =0010…01 …
February 26, 2024 CS21 Lecture 22
SUBSET-SUM is NP-complete
–B=1111…1? ? ? ?
– if clause i is satisfied sum might be 1, 2, or 3
in corresponding column.
– want ? to “mean” ≥ 1
– solution: set ? = 3
– add two “filler” elements for each clause i: –FILL1i =0000…0 0…010…0 –FILL2i =0000…0 0…010…0
column for clause i
February 26, 2024 CS21 Lecture 22 9
SUBSET-SUM is NP-complete
• Reduction: m variables, k clauses – for each variable xi:
• xiTRUE has ones in positions k + i and {j : clause j includes literal xi}
• xiFALSE has ones in positions k + i and {j : clause j includes literal ¬xi}
– for each clause i:
• FILL1i and FILL2i have one in position i
– bound B has 3 in positions 1…k and 1 in positions k+1…k+m
February 26, 2024 CS21 Lecture 22 10
SUBSET-SUM is NP-complete
• Reduction computable in poly-time? • YES maps to YES?
– choose one from each (xiTRUE,xiFALSE) pair corresponding to a satisfying assignment
– choose 0, 1, or 2 of filler elements for each
clause i depending on whether it has 3, 2, or 1
true literals
– first m digits add to 1; last k digits add to 3
February 26, 2024 CS21 Lecture 22 11
SUBSET-SUM is NP-complete
• NO maps to NO?
– at most 5 ones in each column, so no carries to worry about
– first m digits of B force subset to choose exactly one from each (xiTRUE,xiFALSE) pair
– last k digits of B require at least one true literal per clause, since can only sum to 2 using filler elements
– resulting assignment must satisfy φ
February 26, 2024 CS21 Lecture 22 12
• GivengraphG=(V,E)
– acutisasubsetS⊆V
– anedge(x,y)crossesthecutifx∈Sandy∈V–Sor
x∈V–S andy∈S – search problem:
find cut maximizing number of edges crossing the cut
February 26, 2024 CS21 Lecture 22 13
• GivengraphG=(V,E)
– acutisasubsetS⊆V
– anedge(x,y)crossesthecutifx∈Sandy∈V–Sor
x∈V–S andy∈S – search problem:
find cut maximizing number of edges crossing the cut
February 26, 2024 CS21 Lecture 22 14
Theorem: the following language is NP- complete:
MAX CUT = {(G = (V, E), k) : there is a cut S ⊆ V with at least k edges crossing it}
– Part 1: MAX CUT ∈ NP. Proof? – Part 2: MAX CUT is NP-hard.
• reduce from?
February 26, 2024 CS21 Lecture 22 15
Not-All-Equal 3SAT
(x1∨x2 ∨¬x3)∧(¬x1 ∨x4 ∨x3)∧…∧(…) Theorem: the following language is NP-
NAE3SAT = {φ : φ is a 3-CNF formula for which there exists a truth assignment in which every clause has at least 1 true literal and at least 1 false literal}
– Part 1: NAE3SAT ∈ NP. Proof?
– Part 2: NAE3SAT is NP-hard. Reduce from?
February 26, 2024 CS21 Lecture 22 16
NAE3SAT is NP-complete
• We are reducing from the language: CIRCUIT-SAT = {C : C is a Boolean circuit for which there exists a satisfying truth assignment}
to the language:
NAE3SAT = {φ : φ is a 3-CNF formula for which there exists a truth assignment in which every clause has at least 1 true literal and at least 1 false literal}
February 26, 2024 CS21 Lecture 22 17
NAE3SAT is NP-complete
• Recall reduction to 3SAT
– variables x1, x2, …,xn, gates g1, g2, …, gm – produce clauses:
∨ gi z1 z2
• (¬z1 ∨ gi)
•(¬z2 ∨gi) ¬gi
• (¬z ∨ ¬gi)
•(¬z1 ∨¬z2 ∨gi)
CS21 Lecture 22
output gate gm: •(gm)
February 26, 2024
•(¬gi ∨z1 ∨z2) • (¬gi ∨ z1)
• (¬gi ∨ z2)
not all true in a satisfying assignment
NAE3SAT is NP-complete
• Recall reduction to 3SAT
– variables x1, x2, …,xn, gates g1, g2, …, gm – produce clauses:
∨ gi z1 z2
•(¬z1 ∨gi∨w)
•(¬z2 ∨gi ∨w) ¬gi
•(gi ∨z∨w)
• (¬z ∨ ¬gi ∨ w)
•(¬z1 ∨¬z2 ∨gi)
CS21 Lecture 22
output gate gm: •(gm∨w)
February 26, 2024
•(¬gi ∨z1 ∨z2) •(¬gi ∨z1 ∨w) •(¬gi ∨z2 ∨w)
NAE3SAT is NP-complete
• Does the reduction run in polynomial time?
• YES maps to YES
– already know how to get a satisfying assignment to the BLUE variables
•(¬z1 ∨gi∨w) •(¬z2 ∨gi ∨w) •(¬gi ∨z1 ∨z2) •(¬gi ∨z1 ∨w) •(¬gi ∨z2 ∨w) •(¬z1 ∨¬z2 ∨gi) •(gi ∨z∨w)
• (¬z ∨ ¬gi ∨ w) • (gm ∨ w)
– set w = FALSE February 26, 2024
CS21 Lecture 22
NAE3SAT is NP-complete
• NO maps to NO
– given NAE assignment A
– complement A’ is a NAE assignment
– A or A’ has w = FALSE
– must have TRUE BLUE variable in every clause
– we know this implies C satisfiable
February 26, 2024 CS21 Lecture 22
•(¬z1 ∨gi∨w)
• (¬z2 ∨ gi ∨ w) •(¬gi ∨z1 ∨z2)
• (¬gi ∨ z1 ∨ w) •(¬gi ∨z2 ∨w) •(¬z1 ∨¬z2 ∨gi) •(gi ∨z∨w)
• (¬z ∨ ¬gi ∨ w) • (gm ∨ w)
• GivengraphG=(V,E)
– acutisasubsetS⊆V
– anedge(x,y)crossesthecutifx∈Sandy∈V–Sor
x∈V–S andy∈S – search problem:
find cut maximizing number of edges crossing the cut
February 26, 2024 CS21 Lecture 22 22
• GivengraphG=(V,E)
– acutisasubsetS⊆V
– anedge(x,y)crossesthecutifx∈Sandy∈V–Sor
x∈V–S andy∈S – search problem:
find cut maximizing number of edges crossing the cut
February 26, 2024 CS21 Lecture 22 23
Theorem: the following language is NP- complete:
MAX CUT = {(G = (V, E), k) : there is a cut S ⊆ V with at least k edges crossing it}
– Part 1: MAX CUT ∈ NP. Proof? – Part 2: MAX CUT is NP-hard.
• reduce from?
February 26, 2024 CS21 Lecture 22 24
MAX CUT is NP-complete • We are reducing from the language:
NAE3SAT = {φ : φ is a 3-CNF formula for which there exists a truth assignment in which every clause has at least 1 true literal and at least 1 false literal}
to the language:
MAX CUT = {(G = (V, E), k) : there is a cut S ⊆ V with at least k edges crossing it}
February 26, 2024 CS21 Lecture 22 25
MAX CUT is NP-complete
• Thereduction:
– given instance of NAE3SAT (n nodes, m clauses):
(x1 ∨x2∨¬x3)∧(¬x1 ∨x4∨x5)∧…∧(¬x2 ∨x3∨x3 ) – produce graph G = (V, E) with node for each literal
x1 February 26, 2024
• parallel edges for each 2-clause
CS21 Lecture 22
• triangle for each
MAX CUT is NP-complete
• triangle for each
– if cut selects TRUE literals, each clause contributes 2 if NAE, and < 2 otherwise
– need to penalize cuts that correspond to inconsistent truth assignments
– add ni parallel edges from xi to ¬xi (ni = # occurrences) (repeat variable in 2-clause to make 3-clause for this calculation)
February 26, 2024 CS21 Lecture 22 27
• parallel edges for each 2-clause
• triangle for each 3-clause
• parallel edges for each 2- clause
• ni parallel edges from xi to ¬xi • set k = 5m
MAX CUT is NP-complete
• YESmapstoYES
– take cut to be TRUE literals in a NAE truth
assignment
– contribution from clause gadgets: 2m
– contribution from (xi, ¬xi) parallel edges: 3m
February 26, 2024 CS21 Lecture 22 28
• triangle for each 3-clause
• parallel edges for each 2- clause
• ni parallel edges from xi to ¬xi • set k = 5m
MAX CUT is NP-complete
• NOmapstoNO
– Claim: if cut has xi, ¬xi on same side, then can move
one to opposite side without decreasing # edges
crossing cut
– contribution from (xi, ¬xi) parallel edges: 3m – contribution from clause gadgets must be 2m – conclude: there is a NAE assignment
February 26, 2024 CS21 Lecture 22 29
MAX CUT is NP-complete
Claim: if cut has xi, ¬xi on same side, then can move one to opposite side without decreasing #
edges crossing cut
ni ... a+b≤2ni xi
February 26, 2024
CS21 Lecture 22
a+ni ≥a+bor b + ni ≥ a + b
• Is NP closed under complement?
Can we transform this machine:
x∉L qaccept
February 26, 2024
into a machine with this behavior?
CS21 Lecture 22 31
• language L is in coNP iff its complement (co-L) is in NP
• it is believed that NP ≠ coNP
• note: P = NP implies NP = coNP
– proving NP ≠ coNP would prove P ≠ NP – another major open problem...
February 26, 2024 CS21 Lecture 22 32
• canonical coNP-complete language:
UNSAT = {φ : φ is an unsatisfiable 3-CNF formula}
February 26, 2024 CS21 Lecture 22 33
coNP • another example
3-DNF-TAUTOLOGY = {φ : φ is a 3-DNF formula and for all x, φ(x) =1}
• another example:
EQUIV-CIRCUIT = {(C1, C2) : C1 and C2 are Boolean circuits and for all x, C1(x) = C2(x)}
February 26, 2024 CS21 Lecture 22 34
Disjunctive Normal Form = OR of ANDs
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com