COMP3630/6360: Theory of Computation Semester 1, 2022
The Australian National University
Time Complexity
Copyright By PowCoder代写 加微信 powcoder
This lecture covers Chapter 10 of HMU: Time Complexity
NP-Hardness of CNFSAT NP-Hardness of 3SAT More NP-Hard Problems
Additional Reading: Chapter 10 of HMU.
Cook’s Theorem (SAT is NP-Complete)
Cook’s theorem gives a “generic reduction” for every problem in NP to SAT. So SAT is as hard as any other problem in NP—it’s NP-complete.
So, SAT is the granddaddy of all NP-complete problems.
Many people have worked on the SAT problem, and there are now very efficient
solvers (SAT solvers) for it.
People frequently translate NP-complete problems to propositional logic, and then attack them with these general solvers!
CSAT is a special case of SAT.
CSAT = { ⟨φ⟩ | φ is a satisfiable cnf formula }
where a Boolean formula is in cnf (for conjunctive normal form) if it is (also) generated by the grammar
φ → (c) | (c) ∧ φ c → l | l ∨ c
l → p | ¬p p → x | y | . . .
We call cs clauses, ls literals, and ps propositions.
Example 10.1
(x ∨z)∧(y ∨z) is a cnf for the Boolean formula (x ∧y)∨z.
CSAT is NP-Complete
Clearly CSAT is in NP because we can use the same certificate for φ in cnf as we would for the same φ in SAT.
Giving a P reduction from SAT to CSAT is tricky.
A straight-forward translation of Boolean formulae into equivalent cnf may result in an exponential blow-up, meaning that this approach is useless.
Instead, we recall a reduction f won’t have to preserve satisfaction:
∀π(π|=φ ⇔ π|=f(φ))
but merely satisfiability
∃π(π |= φ) ⇔ ∃π(π |= f(φ)) meaning that we’re free to choose different πs for the two sides.
CSAT is NP-Hard
The translation from Boolean formulae to cnf proceeds in two steps which are both in P.
1 Translate to nnf (negation normal form) by pushing all negation symbols down to
propositions. (This is still satisfaction-preserving.)
2 Translate from nnf to cnf. (This merely preserves satisfiability.)
Pushing Down ¬
We use de Morgan’s laws and the law of double negation to rewrite left-hand-sides to right-hand-sides:
¬(φ∧ψ) ⇔ ¬(φ)∨¬(ψ) ¬(φ∨ψ) ⇔ ¬(φ)∧¬(ψ)
¬(¬(φ)) ⇔ φ
Example 10.2
¬((¬(x ∨y))∧(¬x ∨y)) ⇔ ¬(¬(x ∨y))∨¬(¬x ∨y) ⇔ x ∨ y ∨ ¬(¬x ∨ y)
⇔ x ∨y ∨¬(¬x)∧¬y ⇔ x ∨ y ∨ x ∧ ¬y
Pushing Down ¬ cont.
Theorem 10.3
Every Boolean formula φ is equivalent to a Boolean formula ψ in nnf. Moreover, |ψ| is linear in |φ| and ψ can be constructed from φ in P.
by induction on the number n of Boolean operators (∧, ∨, ¬) in φ we may show that there is an equivalent ψ in nnf with at most 2n − 1 operators.
nnf −→ cnf
Theorem 10.4
There is a constant c such that every nnf φ has a cnf ψ such that:
1 ψ consists of at most |φ| clauses.
2 ψ is constructable from φ in time at most c|φ|2.
3 π |= φ iff there exists an extension π′ of π satisfying π′ |= ψ, for all interpretations π of the propositions in φ.
by induction on |φ|.
nnf −→ cnf cont.
Example 10.5
Consider x ∧ ¬y ∨ ¬x ∧ (y ∨ z). An equisatisfiable cnf is (u∨x)∧(u∨¬y)∧(¬u∨¬x)∧(¬u∨v ∨y)∧(¬u∨¬v ∨z).
3SAT is a special case of CSAT.
3SAT = { ⟨φ⟩ | φ is a satisfiable 3cnf formula }
where a Boolean formula is in 3cnf (for 3 literal conjunctive normal form) if it is (also) generated by the grammar
φ → (c) | (c) ∧ φ c → l ∨ l ∨ l
l → p | ¬p p → x | y | . . .
Example 10.6
(x ∨y ∨z)∧(x ∨y ∨¬z)∧(x ∨¬y ∨z)∧(x ∨¬y ∨¬z) is a 3cnf for the Boolean formula x.
3SAT is NP-Complete
Clearly 3SAT is in NP because we can use the same certificate for φ in 3cnf as we would for the same φ in SAT (or CSAT).
Sipser prefers to adapt his NP-hardness proof for SAT to 3SAT over giving a P reduction from SAT to 3SAT.
We P reduce from CSAT to 3SAT instead, by translating arbitrary clauses into clauses with exactly three literals.
Proof detail: how to transform a cnf φ = ni=1 ci into an equisatisfiable 3cnf. We transform each clause ci = ki li,j depending on the number ki of literals in it. (We omit
subscript i.)
Case k = 1
(l1) is replaced by
(l1 ∨u∨v)∧(l1 ∨u∨¬v)∧(l1 ∨¬u∨v)∧(l1 ∨¬u∨¬v)
for some fresh propositions u,v. (l1 ∨l2) is replaced by
(l1 ∨l2 ∨u)∧(l1 ∨l2 ∨¬u)
for some fresh proposition u. is 3cnf already.
(kj=1 lj ) is replaced by
(l1 ∨l2 ∨u1)∧ (lj+2 ∨¬uj ∨uj+1)∧(¬uk−3 ∨lk−1 ∨lk)
for some k − 3 fresh propositions u1, . . . , uk−3.
Case k = 2
Case k = 3 Case k > 3
CLIQUE is NP-Complete
Let Gisundirectedgraph CLIQUE = ⟨G,k⟩ with k-clique
We show NP-completeness on the whiteboard.
HAMPATH is NP-Complete
Recall that Directed graph G has a HAMPATH = ⟨G,s,t⟩ Hamiltonian path from s to t
We already know that HAMPATH is in NP. We show NP-hardness by proving 3SAT ≤P HAMPATH on the whiteboard.
Node Cover
Given an undirected graph G, a node cover of G is a set C of vertices such that: for every edge between v1 and v2, one of v1 or v2 is in C.
The Node Cover Problem is the problem of deciding whether a graph G has a node cover with k or fewer nodes:
NC={⟨G,k}|Ghasnodecoverofsize ≤k}
Independent Set
Given an undirected graph G, a independent set of G is a set C of vertices such that: no to vertices v1 and v2 ∈ C are connected by an edge.
The Independent Set Problem is the problem of deciding whether a graph G has an independent set with k or or more nodes:
IS = {⟨G,k} | G has independent set of size ≥ k}
Node Cover vs Independent Set
Q. How are node cover and independent set related?
Node Cover vs Independent Set II
Theorem. A graph G with n vertices has a node cover of size k iff it has an independent set of size n − k. Indeed, Node Cover is polytime reducible to independent set.
Corollary. If Node Cover is in NP, then so is independent set. Theorem. Node Cover is in NP (whiteboard).
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com