Algorithms for Data Science
CSOR W4246
Eleni Drinea
Computer Science Department
Columbia University
Satisfiability problems: SAT, 3SAT, Circuit-SAT
Outline
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)
Today
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
Reduction
R
x y=R(x) Algorithm
for Y
yes
no
Algorithm for X
We used reductions
I as a means to design efficient algorithms
I for arguing about the relative hardness of problems
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.
Examples:
I IS(D): given a graph G and an integer k, does G have an
independent set of size k?
I 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.
Beyond P?
The complexity class P and beyond
Definition 1.
P is the set of problems that can be solved by polynomial-time
algorithms.
Beyond P?
Problems like IS(D) and VC(D):
I No polynomial time algorithm has been found despite
significant effort, so we don’t believe they are in P.
I 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.
P vs NP
Fact 4.
P ⊆ NP
Proof.
Let X(D) be a problem in P.
I There is an efficient algorithm A that solves X(D), that is,
A(x) = yes if and only if x ∈ X(D).
I 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).
I The algorithm B that on inputs x, t, simply discards t and
simulates A(x) is such an efficient certifier.
P vs NP
P = NP ?
P vs NP
P = NP ?
I Arguably the biggest question in theoretical CS
I 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?
I Intuitively, the hardest problems in NP are the least likely
to belong to P.
I How do we identify the hardest problems?
Why would NP contain more problems than P?
I Intuitively, the hardest problems in NP are the least likely
to belong to P.
I 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. for all Y ∈ NP, Y ≤P X.
Why would NP contain more problems than P?
I Intuitively, the hardest problems in NP are the least likely
to belong to P.
I 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) ∈ NP and
2. for all Y ∈ NP, Y ≤P X.
Fact 6.
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
I 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
I 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.
I Therefore, from an algorithmic perspective, we need to
stop looking for efficient algorithms for the problem.
Why we should care whether a problem is NP-complete
I 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.
I 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
show that
1. Y ∈ NP 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
show that
1. Y ∈ NP and
2. X ≤P Y
Why?
Fact 7 (Transitivity of reductions).
If X ≤P Y and Y ≤P Z, then X ≤P Z.
We know that for all A ∈ NP, A ≤P X. By Fact 15, 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
show that
1. Y ∈ NP 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 NP 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
show that
1. Y ∈ NP and
2. X ≤P Y
The first NP-complete problem
Theorem 7 (Cook-Levin).
Circuit SAT is NP-complete.
Today
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
I Boolean variable x: a variable that takes values from {0, 1}
(equivalently, {F, T}, standing for False, True).
I Suppose you are given a set of n boolean variables
{x1, x2, . . . , xn}.
I Boolean connectives: logical AND ∧, logical OR ∨ and
logical NOT ¬
I Boolean expression or Boolean formula: boolean variables
connected by boolean connectives
I 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)
1. ¬¬φ ≡ φ
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 `i 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.
I 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
`1 ∨ `2 ∨ . . . ∨ `k
I Example: n = 3, m = 2, φ = (x1 ∨ x2) ∧ (x1 ∨ x2 ∨ x3)
Remark: we will henceforth work with formulas in CNF.
Semantics of boolean formulas
I Let X = {x1, . . . , xn}.
I A truth assignment for X is an assignment of truth values
from {0, 1} to each xi.
I So a truth assignment is a function v : X → {0, 1}.
I It is implied that xi obtains value opposite from xi.
I Example: X = {x1, x2, x3}
I Truth assignment for X: x1 = 1, x2 = x3 = 0
I A truth assignment causes a boolean formula to receive a
value from {0, 1}.
I Example: φ = (x1 ∨ x2) ∧ (x1 ∨ x2 ∨ x3)
I The above truth assignment causes φ to evaluate to 0.
Satisfying truth assignments
I A truth assignment satisfies a clause if it causes the clause
to evaluate to 1.
I Example: φ = (x1 ∨ x2) ∧ (x1 ∨ x2 ∨ x3)
Then x1 = x2 = 1, x3 = 0 satisfies both clauses in φ.
I A truth assignment satisfies a formula in CNF if it satisfies
every clause in the formula.
I Example: x1 = x2 = 1, x3 = 0 satisfies the above φ.
But x1 = 1, x2 = x3 = 0 does not satisfy φ.
I A formula φ is satisfiable if it has a satisfying truth
assignment.
I 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?
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?
Theorem 11.
SAT, 3SAT are NP-complete.
Today
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
I A physical circuit consists of gates that perform logical
AND, OR and NOT.
I We will model such a circuit by a boolean combinatorial
circuit which is a labelled DAG with
I Source nodes: these are the inputs of the circuit and may
be hardwired to 0 or 1, or labelled with some variable.
I Intermediate nodes: these correspond to the gates of the
circuit and are labelled with ∧ (AND), ∨ (OR) or ¬ (NOT).
I ∧, ∨ gates have two incoming and one outgoing edge
I ¬ gates have one incoming and one outgoing edge
I 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:
I edges are wires that carry the value of their tail node;
I intermediate nodes perform their label operation on their
incoming edges, pass the result along their outgoing edge;
I 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
Lemma 13.
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) is a shorthand for ((φ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 φ
I a variable xv that encodes the truth value computed by
node v in C;
I 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
(why?).
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
I Circuit-SAT is NP-complete
I Circuit-SAT ≤P SAT
I 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
I Circuit-SAT is NP-complete
I Circuit-SAT ≤P SAT
I SAT ≤P 3SAT
⇒ SAT and 3SAT are NP-complete.
Claim 1.
IS(D) is NP-complete.
Proof.
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. The instance (G, k) is a yes instance of IS(D)
if and only if
φ is a yes instance of 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)
construct
(G, k)
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.
Remark 1.
I Heart of reduction X ≤P Y: understand why some small
instance of Y makes it difficult.
I For IS(D), such an instance is a triangle: it’s not clear
which of its vertices to add to our independent set.
Gadgets!
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.
x₁
x2 x₃
x₁
x2 x₃
x₁
x2 x₃
Example: ϕ = (x₁ ∨ x2 ∨ x₃% ∧ (¬x₁ ∨ x₂ ∨ ¬x₃% ∧ (x₁∨ ¬x₂ ∨ ¬x₃%
I Hence our graph G consists of m isolated triangles.
I 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?
I Suppose x1 was picked from the first triangle.
I Can still pick x1 from the second triangle!
I 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.
Consistency gadgets
2. Is this truth assignment consistent?
I Suppose x1 was picked from the first triangle.
I Can still pick x1 from the second triangle!
I 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.
Consistency gadget: add edges between all occurrences of xi
and xi, for every i, in G.
Constructed instance (G, k) of IS(D)
x₁
x2 x3
¬x₁
x2 ¬x3
x₁
¬x2 ¬x3
ϕ = (x₁ ∨ x2 ∨ x3% ∧ (¬x₁ ∨ x2 ∨ ¬x3% ∧ (x₁ ∨ ¬x2 ∨ ¬x3%,
Example: given the formula ϕ below (n=m=3)
the derived graph G is as follows:
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
I Suppose that G has an independent set S of size m.
I Then every triangle contributes one node to S.
I Define the following truth assignment
I Set the literal corresponding to that node to 1.
I Any variables left unset by this assignment may be set to
0 or 1 arbitrarily.
x₁
x2 x₃
¬x₁
x2 ¬x₃
x₁
¬x2 ¬x₃
ϕ = (x₁ ∨ x2 ∨ x₃% ∧ (¬x₁ ∨ x₂ ∨ ¬x₃% ∧ (x₁∨ ¬x₂ ∨ ¬x₃%
Derived truth assignment: x₁=1, x2=1, x₃=0
Independent set S = {x₁, x2, x₁}
Proof of equivalence, reverse direction
I Suppose that G has an independent set S of size m.
I Then every triangle contributes one node to S.
I Define the following truth assignment
I Set the literal corresponding to that node to 1.
I 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
I Suppose that G has an independent set S of size m.
I Then every triangle contributes one node to S.
I Define the following truth assignment
I Set the literal corresponding to that node to 1.
I 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 clause is satisfied.
Proof of equivalence, forward direction
I Now suppose there is a satisfying truth assignment for φ.
I Then there is (at least) one True literal in every clause.
I Construct an independent set S as follows:
From every triangle, add to S a node labelled by such a
literal; hence S has size m.
We claim that S thus constructed is indeed an independent set.
Proof of equivalence, forward direction
I Now suppose there is a satisfying truth assignment for φ.
I Then there is (at least) one True literal in every clause.
I Construct an independent set S as follows:
From every triangle, add to S a node labelled by such a
literal; hence S has size m.
We claim that S thus constructed is indeed an independent set.
1. S would not be an independent set if there was an edge
between any two nodes in it.
2. Since all nodes in S belong to different triangles, an edge
implies that the two nodes are labelled by opposite literals.
3. Impossible: S only contains True literals (so it cannot