STUDY MATERIAL:
• [CLRS] chapter 34
Copyright By PowCoder代写 加微信 powcoder
Preliminaries
Complexity Classes P, NP, co-NP, NP-complete
Polynomial Reducibility & NP-Completeness NP-Complete Problems
Preliminaries
Foundations & Limitations ?
Cantor’s Continuum Hypothesis (CH):
There is no set S such that N < S < |R| .
Frege published Basic Laws of Arithmetic 1893
Russell and Whitehead published 1910
proved Incompleteness Theorem 1931
Electronic Digital Computers 1940’s
Russell wrote Frege about the Paradox
posed EntscheidungsProblem (the decision problem on first-order logic)
On Computable Numbers with an Application to the EntscheidungsProblem
+ Godel proved CH is independent of axioms of set theory
Un-Computable Problems
No algorithm exists for certain computational problems, such as:
Diophantine Equations [Diophantus of Alexandria, 3rd century AD] Does a multi-variable polynomial with integer coefficients, e.g.,
x3y2z2 + 7xy4z3 – 3x2y5z = 8,
have an integer valued solution for its variables?
[1900]: Hilbert’s 10th problem asked is this problem solvable. Matiyasevich [1970] proved the unsolvability of general diophantine equations.
The Halting Problem [ . Turing,1936]
– he was then a math student at Cambridge, England.
There were no digital computers or programming languages!
Arguably, these things came about exactly because of Turing’s brilliant thoughts.
Other contributors: Emil Post [1920], ̈del [1930], [1935].
There are infinitely many uncomputable problems, e.g., Buffer Overflow, Post’s Correspondence, ...
Computational Complexity Classes
So, there are computationally unsolvable problems.
Computable problems themselves have vastly different computational complexity. Complexity Classes classify problems by their computational complexity.
Computable
EXP = exponential P = polynomial
Uncomputable
Linear Programming
Given linearly constrained (in-)equalities & a linear objective function on many variables with integer coefficients, find real values for the variables that satisfy the constraints and optimize the objective function.
minimize 3x5y2z subjectto: 4x-y7z8 2x 4y 3 5y 3z 9 x0
Computational Complexity of LP = polynomial [Leonid Khachyian 1979]
LP is a versatile computational model for problem formulation.
Virtually all problems we have studied so far can be modeled as LP problems (with the exception of 0/1 Knapsack) and have polynomial time complexity, e.g.,
, , Shortest Paths, ...
Integer Linear Programming
Given linearly constrained (in-)equalities & a linear objective function on many variables with integer coefficients, find integer values for the variables that
satisfy the constraints and optimize the objective function.
minimize 3x5y2z subjectto: 4x-y7z8 2x 4y 3 5y 3z 9 x0
x,y,z areintegers
Computational Complexity of ILP: polynomial or exponential ???
ILP is at least as powerful and versatile as LP. Search problems can be cast as ILP, e.g.,
0/1 Knapsack, Graph Coloring, Matching, ,
Traveling Salesman Problem, Boolean Formula Satisfiability, ... ...
z =x y AND
(a DAG of logical gates)
is satisfiable
if and only if
there is a truth assignment to its variable input gates
that makes the output true.
Circuit SAT 1
z =x y OR
z = x NOT
xyx Combinatorial Circuit
true ? ? ?
For a given truth assignment, evaluate gate outputs in topological order.
Boolean Formula SAT
φ(x yz)(x y)(yz)(zx)(x yz)(wxz)
is an instance of CNF-SAT or SAT for short:
a Boolean formula in conjunctive normal form (CNF),
i.e., a conjunction () of a number of clauses (the parentheses); each clause is disjunction () of some literals;
each literal is a Boolean variable or negation of a Boolean variable.
𝑘SAT: instances are in 𝑘-CNF, i.e., each clause has ≤ 𝑘 literals.
3SAT: instances are in 3-CNF. (e.g., 𝜑 above)
A Boolean formula is satisfiable, (Is 𝜑 satisfiable?)
if there is a truth assignment to its variables that makes the formula true.
A Boolean formula is a tautology, (Is 𝜑 a tautology?) if every truth assignment of its variables makes the formula true. (Negation of a tautology is unsatisfiable.)
Input: a boolean 2-CNF formula Φ. Question: Is Φ satisfiable?
Step 1: Idea: 𝑥 ∨ 𝑦 ≡ 𝑥 ⟹ 𝑦 ≡ 𝑦 ⟹ 𝑥 Construct the directed graph 𝐺 = (𝑉, 𝐸):
𝑉= 𝑥, 𝑥 𝑥isavariablein Φ.
𝐸= 𝑥⟶𝑦 , 𝑦⟶𝑥 𝑥∨𝑦 isaclausein Φ}
Example: Φ=(𝑥∨𝑦)∧(𝑥∨𝑦)∧(𝑦∨𝑧)∧(𝑧∨𝑥)∧(𝑤∨𝑧)
Question: Can we assign T or F labels to vertices of G such that
• no opposite literal pair i. e., 𝑥 and 𝑥 is labeled the same, and • no edge has its incident vertices labeled as: 𝑇 ⟶ 𝐹 ?
CLAIM: F is satisfiable No SCC of G contains
a variable and its negation.
Proof of []: In a satisfying truth assignment all literal nodes in the same cycle,
Proof sketch: See Exercise 10.
hence in the same SCC, must have the same truth value (all true or all false).
Proof of []: In the SCC component DAG, if an SCC node has in-degree 0, its “negated” SCC node must have out-degree 0. Why?
What truth values would you assign to such a pair of SCC nodes?
Adapt the SCC algorithm to get a full truth assignment in linear time.
Circuit SAT SAT
Give the output of each gate a distinct name. Convert each gate to an equivalent small CNF-SAT.
Then take their conjunction, including the circuit output.
(z x y)
(z x y)
(z x) (z x)
Solution Construction vs Verification Circuit-SAT, SAT, ILP, LP ... are (Combinatorial) Search Problems.
Search Problem. Instance I:
Construction: Verification:
Obvious: Question:
given I, output a valid solution S for instance I.
given (I, S), verify that S is a valid solution for instance I.
Construction is at least as hard as Verification. Is Construction strictly harder than Verification?
Consider establishing a Mathematical Fact. Construction: Provide a Proof.
Verification: Given a “proof”, verify its validity.
true false
Circuit SAT Verification LP
z1x Plus, for all gate-output variables z, add the constraints:
zy zy zxy1 zxy
0 z 1.
Objective: Maximize zOUT (the circuit output). Now we have an instance of LP
Circuit SAT Construction ILP
zy zxy1
true false ?
Plus, for all gate-output variables z, add the constraints: 0 z 1, and z is an integer.
Objective: Maximize zOUT (the circuit output).
Now we have an instance of ILP.
zx zy zxy
Why ILP and not LP?
zy zxy1
zx zy zxy
Plus the constraints 0 z 1 , for every variable z.
Integrality constraints are essential.
Consider the circuit for an un-satisfiable 3SAT instance. Ignore the integrality constraints and assign the value
1⁄2 = 1 – 1⁄2 to each variable and its negation.
Part of the circuit for an arbitrary clause (u v w) :
Conjunction of all these “1” clause outputs will be a “1” ! Is the circuit satisfiable or not ?!
u=1⁄2 v=1⁄2 w=1⁄2
Construction HARD Verification EASY ??? Linear Programming
Search Problem Verification 3SAT Verification
Integer Linear Programming Search Problem Construction
3SAT Construction
Complexity Classes:
P, NP, co-NP, NP-complete
Optimization vs Decision Problems Optimization Problem: output is an optimum solution to the input instance
Shortest Path:
Instance: G, s, t
Output: Shortest path in graph G from vertex s to t.
Decision Problem: the output is a “yes” or “no” answer.
Decision version of Shortest Path:
Instance: G, s, t, K
Question: Does graph G have a path from vertex s to t with length at most K?
For a maximization problem, “at most” is replaced by “at least”.
Why Decision Problems ?
1. Optimization version of a problem is at least as hard as its decision version.
Example: To answer whether G has a path of length at most K from s to t, we can find the shortest path from s to t and compare its length with K.
2. So, if we can establish the fact that the decision version is hard, that would imply that the optimization version must also be hard.
3. With uniform “yes/no” output type, it is more convenient to transform (or reduce) one decision problem to another, as we shall see.
4. The purpose of these reductions is to establish lower-bound (as was done in the Sorting/Selection Slides), rather than obtaining an algorithmic upper-bound (as was done by reducing bipartite matching to max-flow).
5. By the way, the converse of (2) is usually true as well:
If the decision version is easy, so is the optimization version. Example: with integer numeric input, do binary search on K in the decision version to find the shortest path.
The Complexity Class P
P = Deterministic Polynomial time:
the class of problems that admit a deterministic algorithm whose
running time is O(nd) for some constant d, where n is the input size.
[ 1964], [ 1965]:
A problem is tractable (easy) if it belongs to P, otherwise it is intractable (hard).
Justification (polynomial vs exponential):
P is preserved under many important computational models, e.g., RAM, Turing Machine, etc.
Polynomials are the smallest class that contain linear functions & are closed under: composition, addition, multiplication.
P scales nicely (multiplicative rather than additive) Dilemma: O(n1000) vs O(1.1n) ! Explain.
The Complexity Class NP
NP = Non-deterministic Polynomial time:
the class of decision problems that admit a non-deterministic
polynomial time algorithm.
Decision problem A
Decision language of A: LA = { I | I is a “yes” instance of problem A}
LA = { I | ALG(I)=“yes”}
for some non-deterministic polynomial time algorithm ALG (ALG gives no termination guarantee on “no” instances!)
LA = { I | solution certificate S, |S| poly(|I|), Verify(I, S) = “yes”} for some deterministic algorithm Verify with running time poly(|I|). (Note: the “guessed” solution certificate S cannot be too large.
It must satisfy: |S| poly(|I|). See Exercise 9 at the end of these slides.)24
P, NP, EXP
“polynomial time Construction vs Verification” EXP
The $1,000,000 Question
[ , 1971]: Is P = NP or P NP ?
This has turned out to be one of the most challenging open problems in all of mathematics and computer science!
At the turn of the 20th century, The Clay Mathematics Institute posted 7 “Millenium Problems” with an award of $1,000,000 for the solution
of any one of them. The “P vs NP” question is one of them.
PNP thereexistproblemsinNP–P.
The quest in search of such problems led to the question
“what are the hardest problems in NP?”
This gave rise to the class of NP-complete problems; the hardest in NP.
[ , 1971] discovered the first NP-complete problem: SAT
[ , 1972] published a long list of other NP-complete problems.
These were seemingly intractable (?) highly researched problems, with
important applications in science technology and engineering.
By now there are thousands of published NP-complete problems.
Search/OPT Problems: HARD vs EASY
Hard Problems (NP-complete)
Integer Linear Programming 3SAT
Minimum Spanning Path Longest Path
3D Matching
0-1 Knapsack Independent Set Hamiltonian Cycle
Some (unresolved) exceptions:
Easy Problems (in P)
Linear Programming 2SAT
2Color Minimum Spanning Tree Shortest Path Matching Fractional Knapsack Independent Set on trees Eulerian Cycle
Graph Isomorphism quasi-poly time [L. Babai, STOC2016] IntegerFactoring poly-timequantumalg.[P.Shor,FOCS1994]
Complements of P and NP
co-P = {A | (complementofA) = ĀP }
co-NP = {A | (complementofA) = ĀNP} P is closed under complementation [P = co-P]:
A: AP ĀP
“yes” I ALG
“yes” I ALG
“no” “yes”
NP is not known to be closed under complementation. P = co-P, P NP, co-P co-NP.
P NP co-NP
Open Questions:
P = NP ? P = NP co-NP ? NP = co-NP ?
Polynomial Reducibility
NP-Completeness
Hardest Problems in NP
NP-complete = the class of hardest problems in NP.
How do we show that a problem A NP is NP-complete,
i.e., A is at least as hard as any other problem in NP ?
That is, if A is tractable, then every problem in NP is also tractable.
Inotherwords: AP NP=P.
Polynomial Reducibility denoted “ P ” is the tool to use.
Polynomial Reducibility
A P B : Problem A is polynomially reducible to Problem B, if there is a polynomial-time computable transformation f
from instances of A to instances of B that preserves membership:
1. IA f(I)B,and
2. f(I) can be computed in poly(|I|) time.
the direction of reduction is from A to B (not the reverse). I A f(I) B, &
I A f(I) B, &
a reduction algorithm that computes f(I) in poly(|I|) time, & length of instance f(I) is also poly(|I|).
Polynomial Reducibility
A is not harder than B (to within a polynomial), & B is at least as hard as A (the contra-positive)
BP AP, AP BP.
algorithm for A
Reduction procedure
algorithm for
NP-hard & NP-complete
B is NP-hard if every problem in NP polynomially reduces to B:
A NP: A P B
NP-complete
B is NP-complete if 1. BNP,and 2. B is NP-hard.
Circuit SAT is NP-complete
This is our first problem to be proved NP-complete. We must show two things:
1. Circuit SAT NP,
2. Circuit SAT is NP-hard: A NP: A P Circuit SAT.
Proof of 1. Circuit SAT NP: We have already seen this.
An instance of the problem is a combinatorial circuit of size n (# wires and gates).
A certificate is a truth assignment to the input gates.
In time poly(n) (in fact in O(n) time) we can deterministically verify whether the given certificate satisfies the circuit output gate:
evaluate gate outputs in topological order.
Circuit SAT is NP-complete
This is our first problem to be proved NP-complete. We must show two things:
1. Circuit SAT NP,
2. Circuit SAT is NP-hard: A NP: A P Circuit SAT.
Proof of 2 [sketch]. Circuit SAT is NP-hard:
Consider an arbitrary problem A NP.
a deterministic algorithm Verify(I,S) that for any certificate S (encoded in binary) & |S| = poly(|I|), runs in poly(|I|) time and verifies whether S is a valid solution for instance I of problem A.
Reduction Procedure: transform Verify(I,S), for any given instance I, to a circuit C with the following properties:
a) The reduction procedure constructs C in poly(|I|) time,
b) C has input bits I and S, where the I bits are given and fixed (0 or 1), and the S bits are unknown variables (? bits),
c) Verify(I,S) = “yes”
the truth assignment S to the variable input bits satisfies C. (P.T.O.)
poly( |I| )
aux machine state
working storage
Computer Hardware
aux machine state
working storage
Computer Hardware
Computer Hardware
aux machine state
working storage
output bit
poly( |I| )
Other NP-complete Problems There is a shortcut on how to prove other problems are NP-complete.
FACT 1: P is transitive.
Proof: APB and BPC APC
(because polynomials are closed under composition)
AP B : xAf(x)B
for some f : f(x) is computable in O(nd) time, n = |x| & some constant d.
BP C : xBg(x)C
for some g : g(x) is computable in O(nc) time, n = |x| & some constant c.
AP C : xAh(x)C
for h(x) = g(f(x)) computable in O(ndc) time, n = |x| & the constant dc.
Other NP-complete Problems There is a shortcut on how to prove other problems are NP-complete.
FACT 1: P is transitive.
FACT 2: Suppose A P B. Then
A is NP-hard B is NP-hard.
Proof: [CNP: C P A ] and [ A P B ] [CNP: C P B ]
How to prove a new problem B is NP-hard:
Select a known NP-complete problem A and show A P B.
If you have choices, pick a problem A that “resembles” B as much as possible to facilitate an easier reduction.
NP-completeness & P vs NP ?
The following statements are equivalent:
(1) P = NP,
(2) All NP-complete problems are in P,
(3) Some NP-complete problem is in P.
(1) (2) (3) are obvious.
(3) (1): B is NP-hard [ANP: A P B ]
APB andBPAP.
If a single NP-complete problem is tractable, then all are!
This is a strong but inconclusive evidence that P NP, since despite decades of intense research by experts, no polynomial-time algorithm has been found for any one of a multitude of well known NP-complete problems.
If P NP NP-hard
NP-complete
Increasing complexity
Additional
NP-Complete
Some Reductions
Circuit SAT
SAT ILP 3SAT
3-Colorability K-Colorability
Independent Set
Vertex Cover Directed Hamiltonian Cycle
Undirected Hamiltonian Cycle Traveling Salesman
These are all in NP
To prove a problem is NP-complete, we must show 2 things:
(1) It is in NP (i.e., it has a polynomial-time verification algorithm) (2) It is NP-hard (the indicated reductions will show this)
(1) The listed problems are all in NP. (All except ILP are easy to show.) Some examples:
3SAT NP:
Verify that a given truth assignment satisfies the 3SAT instance: Done in linear time by evaluating each clause.
3-Colorability NP:
Given a coloring of vertices of a graph, verify that at most 3 colors are used, and verify that for each edge, its two incident vertices have different colors.
Undirected Hamiltonian Cycle NP:
Given a permutation certificate of vertices of a graph, verify that it forms a Hamiltonian cycle, i.e., a cycle in the graph that visits each vertex exactly once: Check that the given certificate is indeed a permutation, and that there is an edge in the graph between each successive pair of vertices in the permutation (cyclically). 44
SAT P 3SAT
In polynomial time transform an instance of SAT to an instance of 3SAT: Convert each clause with k > 3 literals to k-2 clauses, each with 3 literals, using some new Boolean variables:
φ(a1 a2 ak) ψ(aax)(xax)(xax)(x a x )(x a a)
Proof of []: If is satisfied, then some ai must be true.
Set x1 , … , xi–2 to true and the rest false. That satisfies .
Proof of []: If is satisfied, then at least one ai must be true. Otherwise, the 1st clause of forces x1 to be true,
then the 2nd clause forces x2 to be true, …
eventually falsifying the last clause of ; a contradiction.
1 2 1 1 3 2 2 4 3 k4 k2 k3 k3 k1 k CLAIM: is satisfied truth assignment to xi’s for which is satisfied.
3-Colorability
The 3-Colorability Problem:
Given a graph G,
is it possible to color each vertex of G by one of 3 colors (say red, blue, green) such that no edge of G has its both end vertices colored the same?
3-colorable
Not 3-colorable
3SAT P 3-Colorability
Reduction: Given any 3-CNF-SAT formula F, in time polynomial in |F|,
transforms F to a graph G such that
F is satisfiable G is 3-colorable.
G will be constructed from F
by assembling suitable pieces together
STEP 1: The control assembly
True False
3SAT P 3-Colorability STEP 2: The assembly of Boolean literals
x1 x1 x2 x2 x3 x3 xn xn
Each literal is forced a color T or F and its negation the opposite (F or T). This forces a truth assignment.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com