COM SCI 180 Lecture Notes - Lecture 14: Conjunctive Normal Form, Polynomial-Time Reduction, Vertex Cover
Polynomial-time Reduction
- Reducing solving one problem to the other
- X pY (X is polynomially easier than Y)
- We saw the examples
- Vertex Cover p independent set
- Independent Set p vertex cover
- Karp reduction
- The case where we use the black box only once
- the p relation is transitive
3SAT
- 3-satisfiability problem
- Input: A CNF formula (conjunctive normal form) with each clause having 3
literals
- Output: Yes if satisfiable, No if not
- CNF is a conjunction of clauses, clause is disjunction of literals
- i.e Φ = (X1 V X2) Λ (X2) Λ (X1) ⇒ V is AND, Λ is OR
- No combination of Xj being true or false could give us the true statement
overall
- Claim: 3SA≤ p independent-Set
- Karp reduction:
- Given input CNF, this input is satisfiable if the graph version of this
formula is solvable by the independent set problem. The graph version is
fed into the independent set problem as input.
- Three step process
- Need to find the transformation
- Prove →
- Prove ←
- Some guideline
- Reduction includes some “gadgets”, that translate CNF to graph language
CNF
Graphs
X1, X2 , …
variables
vertices
C1, C2, …
clauses
edges
- We need to pick one literal from each clause to evaluate to true
- Let Φ = C1 Λ C2 Λ C3 … where each C has less than 3 variables
- For each clause C we create one vertex for each literal vertices will be called V1
V2
- We label/annotate each vertex with the corresponding literal
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
Reducing solving one problem to the other. X (cid:3639)py (x is polynomially easier than y) The case where we use the black box only once the (cid:3639)p relation is transitive. Input: a cnf formula (conjunctive normal form) with each clause having (cid:3639) 3 literals. Output: yes if satisfiable, no if not. Cnf is a conjunction of clauses, clause is disjunction of literals i. e = (x1 v x2) (x2) (x1) v is and, is or. No combination of xj being true or false could give us the true statement overall. Given input cnf, this input is satisfiable if the graph version of this formula is solvable by the independent set problem. The graph version is fed into the independent set problem as input. Reduction includes some gadgets , that translate cnf to graph language. We need to pick one literal from each clause to evaluate to true. Let = c1 c2 c3 where each c has less than 3 variables.
