Algorithms for Data Science CSOR W4246
Algorithms for Data Science CSOR
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Algorithms for Data Science
CSOR W4246
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)