CS代写 Analysis of Algorithms, I

Analysis of Algorithms, I
CSOR W4231.002

Computer Science Department

Columbia University
Satisfiability problems: SAT, 3SAT, Circuit-SAT

1 Complexity classes The class NP
The class of NP-complete problems
2 Satisfiability: a fundamental NP-complete problem
3 The art of proving NP-completeness Circuit-SAT ≤P SAT
3SAT ≤P IS(D)

Diagram of a reduction X ≤P Y
X, Y are computational problems; R is a polynomial time transformation from input x to y so that x, y are equivalent
Algorithm for X
We used reductions
􏰈 as a means to design efficient algorithms
􏰈 for arguing about the relative hardness of problems
Reduction R
Algorithm for Y

Decision versions of optimization problems
An optimization problem X may be transformed into a roughly equivalent problem with a yes/no answer, called the decision version X(D) of the optimization problem, by
1. supplying a target value for the quantity to be optimized; 2. asking whether this value can be attained.
􏰈 IS(D): given a graph G and an integer k, does G have an independent set of size k?
􏰈 VC(D): given a graph G and an integer k, does G have a vertex cover of size k?

The complexity class P and beyond
Definition 1.
P is the set of problems that can be solved by polynomial-time algorithms.

The complexity class P and beyond
Definition 1.
P is the set of problems that can be solved by polynomial-time algorithms.
Problems like IS(D) and VC(D):
􏰈 No polynomial time algorithm has been found despite significant effort, so we don’t believe they are in P.
􏰈 Is there anything positive we can say about such problems?

The class NP
Definition 2.
An efficient certifier (or verification algorithm) B for a problem X(D) is a polynomial-time algorithm that
1. takes two input arguments, the instance x and the short certificate t (both encoded as binary strings)
2. there is a polynomial p(·) so that for every string x, we have x ∈ X(D) if and only if there is a string t such that |t| ≤ p(|x|) and B(x, t) = yes.
Note that existence of the certifier B does not provide us with any efficient way to solve X(D)! (why?)
Definition 3.
We define NP to be the set of decision problems that have an efficient certifier.

Let X(D) be a problem in P.
􏰈 There is an efficient algorithm A that solves X(D), that is,
A(x) = yes if and only if x ∈ X(D).
􏰈 To show that X(D) ∈ NP, we need exhibit an efficient certifier B that takes two inputs x and t and answers yes if and only if x ∈ X(D).
􏰈 The algorithm B that on inputs x, t, simply discards t and simulates A(x) is such an efficient certifier.

􏰈 Arguably the biggest question in theoretical CS
􏰈 We do not think so: finding a solution should be harder than checking one, especially for hard problems…

Why would NP contain more problems than P?
􏰈 Intuitively, the hardest problems in N P are the least likely to belong to P.
􏰈 How do we identify the hardest problems?

Why would NP contain more problems than P?
􏰈 Intuitively, the hardest problems in N P are the least likely to belong to P.
􏰈 How do we identify the hardest problems? The notion of reduction is useful again.
Definition 5 (NP-complete problems:).
A problem X(D) is NP-complete if 1. X(D)∈NP,and
2. forallY∈NP,Y≤P X.

Why would NP contain more problems than P?
􏰈 Intuitively, the hardest problems in N P are the least likely to belong to P.
􏰈 How do we identify the hardest problems? The notion of reduction will be useful again.
Definition 5 (NP-complete problems).
A problem X(D) is NP-complete if 1. X(D) ∈ N P and
2. forallY∈NP,Y≤P X.
Suppose X is NP-complete. Then X is solvable in polynomial time (i.e., X ∈P) if and only if P =NP.

Why we should care whether a problem is NP-complete
􏰈 If a problem is NP-complete it is among the least likely to be in P: it is in P if and only if P = NP.

Why we should care whether a problem is NP-complete
􏰈 If a problem is NP-complete it is among the least likely to be in P: it is in P if and only if P = NP.
􏰈 Therefore, from an algorithmic perspective, we need to stop looking for efficient algorithms for the problem.
Instead we have a number of options
1. approximation algorithms, that is, algorithms that return a solution within a provable guarantee from the optimal
2. exponential algorithms practical for small instances
3. work on interesting special cases
4. study the average performance of the algorithm
5. examine heuristics (algorithms that work well in practice, yet provide no theoretical guarantees regarding how close the solution they find is to the optimal one)

How do we show that a problem is NP-complete?
Suppose we had an NP-complete problem X.
To show that another problem Y is NP-complete, we only need
1. Y ∈ N P and 2. X ≤P Y

How do we show that a problem is NP-complete?
Suppose we had an NP-complete problem X.
To show that another problem Y is NP-complete, we only need
1. Y ∈ N P and 2. X ≤P Y
Fact 7 (Transitivity of reductions).
IfX≤P Y andY ≤P Z,thenX≤P Z.
WeknowthatforallA∈NP,A≤P X. ByFact15,A≤P Y. Hence Y is NP-complete.

How do we show that a problem is NP-complete?
Suppose we had an NP-complete problem X.
To show that another problem Y is NP-complete, we only need
1. Y ∈ N P and 2. X ≤P Y
So, if we had a first NP-complete problem X, discovering a new problem Y in this class would require an easier kind of reduction: just reduce X to Y (instead of reducing every problem in N P to Y !).

How do we show that a problem is NP-complete?
Suppose we had an NP-complete problem X.
To show that another problem Y is NP-complete, we only need
1. Y ∈ N P and 2. X ≤P Y
The first NP-complete problem Theorem 7 (Cook-Levin). Circuit SAT is NP-complete.

1 Complexity classes The class NP
The class of NP-complete problems
2 Satisfiability: a fundamental NP-complete problem
3 The art of proving NP-completeness Circuit-SAT ≤P SAT
3SAT ≤P IS(D)

Boolean logic
Syntax of Boolean expressions
􏰈 Boolean variable x: a variable that takes values from {0, 1}
(equivalently, {F, T }, standing for False, True).
􏰈 Suppose you are given a set of n boolean variables
{x1,x2,…,xn}.
􏰈 Boolean connectives: logical AND ∧, logical OR ∨ and
logical NOT ¬
􏰈 Boolean expression or Boolean formula: boolean variables
connected by boolean connectives
􏰈 Notational convention: φ is a boolean formula

Boolean expressions
A boolean expression may be any of the following
1. A boolean variable, e.g., xi.
2. The negation of a Boolean expression φ, denoted by ¬φ1 or φ1.
3. The disjunction (logical OR) of two Boolean expressions in parentheses (φ1 ∨ φ2).
4. The conjunction (logical AND) of two Boolean expressions in parentheses (φ1 ∧ φ2).

Properties of Boolean expressions
Basic properties of Boolean expressions (associativity, commutativity, distribution laws)
2. (φ1 ∨φ2)≡(φ2 ∨φ1)
3. (φ1 ∧φ2)≡(φ2 ∧φ1)
4. ((φ1 ∨φ2)∨φ3)≡(φ1 ∨(φ2 ∨φ3))
5. ((φ1 ∧φ2)∧φ3)≡(φ1 ∧(φ2 ∧φ3))
6. ((φ1 ∨φ2)∧φ3)≡((φ1 ∧φ3)∨(φ2 ∧φ3)) 7. ((φ1 ∧φ2)∨φ3)≡((φ1 ∨φ3)∧(φ2 ∨φ3)) 8. ¬(φ1 ∨ φ2) ≡ (¬φ1 ∧ ¬φ2)
9. ¬(φ1 ∧ φ2) ≡ (¬φ1 ∨ ¬φ2)
10. φ1 ∨ φ1 ≡ φ1 11. φ1 ∧ φ1 ≡ φ1

Conjunctive Normal Form (CNF)
A literal li is a variable or its negation. Definition 8.
A Boolean formula φ is in CNF if it consists of conjunctions of clauses each of which is a disjunction of literals.
􏰈 In symbols, a formula φ with m clauses is in CNF if φ = C1 ∧ C2 ∧ . . . ∧ Cm
and each clause Ci is the disjunction of a number of literals l1 ∨l2 ∨…∨lk
􏰈 Example: n=3,m=2,φ=(x1∨x2)∧(x1∨x2∨x3) Remark: we will henceforth work with formulas in CNF.

Semantics of boolean formulas
􏰈 Let X = {x1,…,xn}.
􏰈 A truth assignment for X is an assignment of truth values from {0, 1} to each xi.
􏰈 So a truth assignment is a function v : X → {0, 1}.
􏰈 It is implied that xi obtains value opposite from xi. 􏰈 Example:X={x1,x2,x3}
􏰈 Truth assignment for X: x1 = 1,x2 = x3 = 0
􏰈 A truth assignment causes a boolean formula to receive a value from {0, 1}.
􏰈 Example: φ=(x1 ∨x2)∧(x1 ∨x2 ∨x3)
􏰈 The above truth assignment causes φ to evaluate to 0.

Satisfying truth assignments
􏰈 A truth assignment satisfies a clause if it causes the clause to evaluate to 1.
􏰈 Example: φ=(x1 ∨x2)∧(x1 ∨x2 ∨x3)
Then x1 = x2 = 1, x3 = 0 satisfies both clauses in φ.
􏰈 A truth assignment satisfies a formula in CNF if it satisfies every clause in the formula.
􏰈 Example: x1 = x2 = 1, x3 = 0 satisfies the above φ. Butx1 =1,x2 =x3 =0doesnotsatisfyφ.
􏰈 A formula φ is satisfiable if it has a satisfying truth assignment.
􏰈 Example: the above φ is satisfiable; a certificate of its satisfiability is the truth assignment x1 = x2 = 1, x3 = 0.

Satisfiability (SAT) and 3SAT
Definition 9 (SAT).
Given a formula φ in CNF with n variables and m clauses, is φ satisfiable?

Satisfiability (SAT) and 3SAT
Definition 9 (SAT).
Given a formula φ in CNF with n variables and m clauses, is φ
satisfiable?
A convenient (and not easier) variant of SAT requires that every
clause consists of exactly three literals. Definition 10 (3SAT).
Given a formula φ in CNF with n variables and m clauses such that each clause has exactly 3 literals, is φ satisfiable?
Are these problems hard?

1 Complexity classes The class NP
The class of NP-complete problems
2 Satisfiability: a fundamental NP-complete problem
3 The art of proving NP-completeness Circuit-SAT ≤P SAT
3SAT ≤P IS(D)

Physical circuits and boolean combinatorial circuits
􏰈 A physical circuit consists of gates that perform logical AND, OR and NOT.
􏰈 We will model such a circuit by a boolean combinatorial circuit which is a labelled DAG with
􏰈 Source nodes: these are the inputs of the circuit and may be hardwired to 0 or 1, or labelled with some variable.
􏰈 Intermediate nodes: these correspond to the gates of the circuit and are labelled with ∧ (AND), ∨ (OR) or ¬ (NOT).
􏰈 ∧, ∨ gates have two incoming and one outgoing edge
􏰈 ¬ gates have one incoming and one outgoing edge
􏰈 Sink node: corresponds to the output of the circuit and has no outgoing edges.

Example circuit
􏰓􏰒¬ 0 1 y􏰖 y􏰐 y􏰏
A circuit C with 2 hardwired source nodes, 3 variable inputs y1, y2, y3 and 5 logical gates.

Circuit-SAT: a first NP-complete problem
Evaluating a circuit:
􏰈 edges are wires that carry the value of their tail node;
􏰈 intermediate nodes perform their label operation on their incoming edges, pass the result along their outgoing edge;
􏰈 the value of the circuit is the value of its output node. Definition 12 (Circuit-SAT).
Given a circuit C, is there an assignment of truth values to its inputs that causes the output to evaluate to 1?
It is easy to see that Circuit-SAT is in NP. Cook and Levin showed that it is NP-complete.

SAT is NP-complete
Circuit-SAT ≤P SAT
Intuitively, this reduction should not be too difficult: formulas and circuits are just different ways of representing boolean functions and translating from one to the other should be easy.
The following two boolean connectives are very useful. 1. (φ1 ⇒ φ2) is a shorthand for (φ1 ∨ φ2).
Intuition: if φ1 =1, then φ2 =1 too (o.w., (φ1 ⇒φ2)=0).
2. (φ1 ⇔φ2)isashorthandfor((φ1 ⇒φ2)∧(φ2 ⇒φ1)), which may be expanded to (φ1 ∨ φ2) ∧ (φ1 ∨ φ2).
This clause evaluates to 1 if and only if φ1 = φ2.

Transforming a circuit C into a formula φ
Consider an arbitrary instance of Circuit-SAT, that is, a circuit C with source nodes, intermediate nodes and an output node.
For every node v in C, we introduce to φ
􏰈 a variable xv that encodes the truth value computed by
node v in C;
􏰈 clauses that ensure that xv takes on the same value as the
output of node v given its inputs
Then any satisfying truth assignment for the circuit C will imply that φ is satisfiable, while, if φ is satisfiable, setting the variable inputs of C to the truth values of their corresponding variables in φ will result in C computing an output with value 1.

φ is the conjunction of the following clauses
1. If v is a source node corresponding to a variable input of the circuit C, we do not add any clause.
2. If v is a source node hardwired to 0, add (xv).
3. If v is a source node hardwired to 1, add (xv).
4. If v is the output node, add (xv).
5. If v is a node labelled by NOT and its input edge is from node u, add (xv ⇔ xu).
6. If v is a node labelled by OR and its input edges are from nodes u and w, add (xv ⇔ (xu ∨ xw)).
7. If v is a node labelled by AND and its input edges are from nodes u and w, add (xv ⇔ (xu ∧ xw)).

Transforming C into φ requires polynomial time
This completes our construction of the clauses of φ.
For example, for the circuit in slide 34, we construct the
following formula.
φ = (¬x1)∧(x2)∧(x6 ⇔(x1 ∧x2))∧(x7 ⇔(x3 ∨x4))∧
(x8 ⇔ ¬x5)∧(x9 ⇔ (x6 ∨x7))∧(x10 ⇔ (x9 ∧x8))∧(x10) The construction is polynomial in the size of the input circuit
Moreover, every clause consists of at most three literals, once φ is in CNF (exercise).

Proof of equivalence
⇒ Let TC be a truth assignment to the variable inputs of C that causes C to evaluate to 1. Propagate TC to assign a truth value to every node v in C. Define a truth assignment Tφ for φ as follows: xv takes on the truth value of v, for every node v in C. Then Tφ satisfies φ.
⇐ Suppose φ has a satisfying truth assignment. Then the truth values of the variables of φ that correspond to inputs in C satisfy C: the clauses in φ guarantee that, for every node in C, the value assigned to that node is exactly what that node computes in C. Since φ = 1, C evaluates to 1.

Independent set
So far, we have stated (with or without proofs) that 􏰈 Circuit-SAT is NP-complete
􏰈 Circuit-SAT ≤P SAT
􏰈 SAT ≤P 3SAT
⇒ SAT and 3SAT are NP-complete. Is IS(D) as “hard” as SAT?

Independent set
So far, we have stated (with or without proofs) that 􏰈 Circuit-SAT is NP-complete
􏰈 Circuit-SAT ≤P SAT
􏰈 SAT ≤P 3SAT
⇒ SAT and 3SAT are NP-complete. Claim 1.
IS(D) is NP-complete.
Reduction from 3SAT.

Structure of the proof
Given an arbitrary instance formula φ of 3SAT, we need to transform it into a graph G and an integer k, so that
1. The transformation is completed in polynomial time.
2. G has an independent set of size at least k if and only if
φ is satisfiable
Example: given
φ = (x1 ∨x2 ∨x3)∧(¬x1 ∨x2 ∨¬x3)∧(x1 ∨¬x2 ∨¬x3)

Structure of the proof
Given an arbitrary instance formula φ of 3SAT, we need to transform it into a graph G and an integer k, so that
1. The transformation is completed in polynomial time.
2. G has an independent set of size at least k if and only if
φ is satisfiable.
􏰈 Heart of reduction X ≤P Y: understand why some small instance of Y makes it difficult.
􏰈 For IS(D), such an instance is a triangle: it’s not clear which of its vertices to add to our independent set.

When reducing from 3SAT, we often use gadgets. Gadgets are constructions that ensure:
1. Consistency of truth values in a truth assignment: once xi is assigned a truth value, we must henceforth consistently use it under this truth value.
2. Clause constraints: since φ is in CNF, we must provide a way to satisfy every clause. Equivalently, we must exhibit at least one literal that is set to 1 in every clause.
In effect, these gadgets will allow us to derive a valid and satisfying truth assignment for φ when the transformed instance is a yes instance of our problem, so we can prove equivalence of the two instances.

Gadgets for IS(D)
Clause constraint gadget: for every clause, introduce a triangle where a node is labelled by a literal in the clause.
Example: φ = (x1 ∨ x2 ∨ x3% ∧ (¬x1 ∨ x2 ∨ ¬x3% ∧ (x1∨ ¬x2 ∨ ¬x3% x1 x1 x1
x2 x3 x2 x3 x2 x3
􏰈 Hence our graph G consists of m isolated triangles.
􏰈 The max independent set in this graph has size m: pick
one vertex from every triangle. So we will set k = m.
Goal: derive a truth assignment from our independent set S. Idea: when a node from a triangle is added to S, set the corresponding literal to 1.

Consistency gadgets
2. Is this truth assignment consistent?
􏰈 Suppose x1 was picked from the first triangle.
􏰈 Can still pick x1 from the second triangle!
􏰈 But then we are setting x1 to both 1 and 0.
⇒ This is obviously not a valid truth assignment!
Consistency of truth assignment: must ensure that we cannot add a node labelled xi and a node labelled xi to our independent set.

Constructed instance (G, k) of IS(D)
Example: given the formula φ below (n=m=3)
φ = (x1 ∨ x2 ∨ x3% ∧ (¬x1 ∨ x2 ∨ ¬x3% ∧ (x1 ∨ ¬x2 ∨ ¬x3%,
the derived graph G is as follows:
x1 ¬x1 x1
x2 x3 x2 ¬x3 ¬x2 ¬x3
Set k=m=3; the input instance R(φ) to IS(D) is (G, 3).
Remark: the construction requires time polynomial in the size of φ.

Proof of equivalence
We need to show that
φ is satisfiable
if and only if
G has an independent set of size at least m

Proof of equivalence, reverse direction
􏰈 Suppose that G has an independent set S of size m. 􏰈 Then every triangle contributes one node to S.
􏰈 Define the following truth assignment
􏰈 Set the literal corresponding to that node to 1.
􏰈 Any variables left unset by this assignment may be set to 0 or 1 arbitrarily.
φ = (x1 ∨ x2 ∨ x3% ∧ (¬x1 ∨ x2 ∨ ¬x3% ∧ (x1∨ ¬x2 ∨ ¬x3%
x1 ¬x1 x1
x2 x3 x2 ¬x3 ¬x2 ¬x3
Independent set S = {x1, x2, x1}
Derived truth assignment: x1=1, x2=1, x3=0

Proof of equivalence, reverse direction
􏰈 Suppose that G has an independent set S of size m. 􏰈 Then every triangle contributes one node to S.
􏰈 Define the following truth assignment
􏰈 Set the literal corresponding to that node to 1.
􏰈 Any variables left unset by this assignment may be set to
0 or 1 arbitrarily.
We need to show that this truth assignment
1. is valid
2. satisfies φ

Proof of equivalence, reverse direction
􏰈 Suppose that G has an independent set S of size m. 􏰈 Then every triangle contributes one node to S.
􏰈 Define the following truth assignment
􏰈 Set the literal corresponding to that node to 1.
􏰈 Any variables left unset by this assignment may be set to
0 or 1 arbitrarily.
We need to show that this truth assignment
1. is valid: by construction, xi,xi cannot both appear in S.
2. satisfies φ: since every triangle contributes one node to S, every clause has a true literal, thus every c

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts