CS代考程序代写 algorithm computational biology distributed system Lecture 11 cont’d:

Lecture 11 cont’d:
NP and Computational Intractability
The University of Sydney
Page 1

Definition of the class NP
Class NP: Decision problems for which YES-instances have a poly-time certifier.
Certification algorithm intuition.
– Certifier views things from “managerial” viewpoint.
– Certifier does not solve the problem by its own;
rather, it checks if a proposed proof t is a valid solution.
Definition: Algorithm C(s,t) is a certifier for problem X if for every input instance s and proposed proof t, C(s, t) = `yes’ if and only if t is a valid solution to s.
“certificate” or “witness”
The University of Sydney
Page 2

Certifiers and Certificates: 3-Satisfiability
SAT: Given a CNF formula F, is there a satisfying assignment? Certificate: An assignment of truth values to the n boolean variables. Certifier: Check that each clause in F has at least one true literal.
(x1 Úx2 Úx3)Ù(x1 Úx2 Úx3)Ù(x1 Úx2 Úx4)Ù(x1 Úx3 Úx4) instance s
Conclusion: SAT is in NP. The University of Sydney
Page 3
x1,x2,x4=true, x3=false certificate t

Class NP-hard
Class NP-complete: A problem in NP such that every problem in NP polynomially reduces to it.
Class NP-hard:
A decision problem such that every problem in NP polynomially reduces to it.
not necessarily in NP
The University of Sydney
Page 4

Establishing NP-Completeness
Remark: Once we establish first “natural” NP-complete problem, others fall like dominoes.
Recipe to establish NP-completeness of problem Y. – Step1. ShowthatYisinNP.
– Step 2. Choose an NP-complete problem X. – Step 3. Prove that X £ p Y.
Justification: If X is an NP-complete problem, and Y is a problem in NP with the property that X £ P Y then Y is NP-complete.
Proof: LetWbeanyprobleminNP. ThenW £P X £P Y. – Bytransitivity,W£P Y.
– Hence Y is NP-complete. ▪ The University of Sydney
by definition of NP-complete
by assumption
Page 5

Reduction Template for Decision Problems (aka Karp reduction)
Algorithm for X
Instance of Y
f(I)
Yes for f(I) No for f(I)
Transforms instance of X to instance of Y
Algorithm for Y
Instance of X
I
Yes for I No for I
Step 2
Step 1
Step 1: Construct a polynomial-time algorithm that transforms instance I of X to an instance f(I) of Y
Step 2: Prove correctness, which boils down to showing
Answer for I is Yes iff answer for f(I) is Yes
Proof usually done by transforming certificate for I to certificate
for f(I) and vice versa The University of Sydney
Page 6

Summary – Lecture 11
§ Polynomial time reductions
3-SAT £P DIR HAMILTONIAN CYCLE £P HAMILTONIAN CYCLE £P TSP 3-SAT £P INDEPENDENT-SET £P VERTEX-COVER £P SET-COVER VERTEX-COVER £P SUBSET-SUM
§ Complexity classes:
P: Decision problems for which there is a poly-time algorithm. NP: Decision problems for which there is a poly-time certifier.
NP-complete: A problem in NP such that every problem in NP polynomial reduces to it.
NP-hard: A problem such that every problem in NP polynomial reduces to it.
§ Lots of problems are NP-complete
See https://www.nada.kth.se/~viggo/wwwcompendium/
The University of Sydney
Page 7

Partitioning Problems
Six basic genres
§ Packing problems: SET-PACKING, INDEPENDENT SET. § Covering problems: SET-COVER, VERTEX-COVER.
§ Constraint satisfaction problems: SAT, 3-SAT.
§ Sequencing problems: HAMILTONIAN-CYCLE, TSP.
3-SAT £P DIR HAMILTONIAN CYCLE £P HAMILTONIAN CYCLE £P TSP § Partitioning problems: 3D-MATCHING, 3-COLOR.
§ Numerical problems: SUBSET-SUM, KNAPSACK. The University of Sydney
Page 8

Graph Coloring
Given an undirected graph G = (V, E), a proper coloring is a coloring of vertices such that every edge has two different colors at its endpoints.
Optimization version: Find a proper coloring using as few colors as possible. Example: How many colors?
A complete graph on n vertices require at least n colors. (Proof by induction.) The University of Sydney
Page 9

Graph Coloring
Given an undirected graph G = (V, E), a proper coloring is a coloring of vertices such that every edge has two different colors at its endpoints.
Optimization version: Find a proper coloring using as few colors as possible. Example: How many colors?
1 1′ 2 2′
3 3′
The University of Sydney
Page 10

Graph Coloring
Given an undirected graph G = (V, E), a proper coloring is a coloring of vertices such that every edge has two different colors at its endpoints.
Optimization version: Find a proper coloring using as few colors as possible. Example: How many colors?
1 1′ 2 2′
3 3′
A graph can be colored with at most 2 colors iff it is bipartite The University of Sydney
Page 11

Graph Coloring
k-COLOR: Given an undirected graph G = (V, E) with n vertices, does there exist a proper coloring using at most k colors?
k-COLOR is in NP:
– certificate = k-coloring,
– certifying algorithm checks that it is a proper coloring and uses at most k colors
1 1′ 2 2′
3 3′
2-COLOR is equivalent to testing for bipartiteness and so is in P. 1-COLOR and n-COLOR is also in P (why?)
The University of Sydney
Page 12

3-SAT Reduces to 3-COLOR
3-COLOR: Given an undirected graph G = (V, E), does there exist a proper coloring using at most 3 colors?
Theorem: 3-SAT £P 3-COLOR.
The University of Sydney Page 13

3-SAT Reduces to 3-COLOR
Theorem: 3-SAT £P 3-COLOR.
Proof: Given an arbitrary instance F of 3-SAT, we construct an instance G of 3-
COLOR that has a 3-coloring iff F is satisfiable. Construction of G:
1. Truth gadget. Introduce 3 special vertices called T, F and O connected to each other. Call their colors T, F and O.
2. Variable gadget. Introduce 2 literal vertices per variable and connect them to each other and O. Literals with same color as T is assigned true, those with same color as F is assigned false. Thus, 3-coloring = consistent truth assignment (every variable is either true or false).
O
TF
The University of Sydney
x1 x1
Page 14

3-SAT Reduces to 3-COLOR
Construction of G:
3.
– –
Clause gadget.
For each clause, add 5 new vertices, connecting them and the corresponding variable vertices with T in the following manner.
Suppose both left and middle variable vertices colored with F.
T
(x1 Úx2 Úx3)Ù(x1 Úx2 Úx3)Ù(x1 Úx2 Úx4)Ù(x1 Úx3 Úx4)
The University of Sydney x1 x2 x3 Page 15

3-SAT Reduces to 3-COLOR
Construction of G:
3.
– –
Clause gadget.
For each clause, add 5 new vertices, connecting them and the corresponding variable vertices with T in the following manner.
Suppose both left and middle variable vertices colored with F. Then, the highlighted vertices must have the following colors.
T
(x1 Úx2 Úx3)Ù(x1 Úx2 Úx3)Ù(x1 Úx2 Úx4)Ù(x1 Úx3 Úx4) TO
FF
The University of Sydney x1 x2 x3 Page 16

3-SAT Reduces to 3-COLOR
Construction of G:
3.
– –
Clause gadget.
For each clause, add 5 new vertices, connecting them and the corresponding variable vertices with T in the following manner.
Suppose both left and middle variable vertices colored with F. Then, the highlighted vertices must have the following colors.
T
(x1 Úx2 Úx3)Ù(x1 Úx2 Úx3)Ù(x1 Úx2 Úx4)Ù(x1 Úx3 Úx4) F
TO
FF
The University of Sydney x1 x2 x3 Page 17

3-SAT Reduces to 3-COLOR
Construction of G:
3.
– –
Clause gadget.
For each clause, add 5 new vertices, connecting them and the corresponding variable vertices with T in the following manner.
Suppose both left and middle variable vertices colored with F. Then, the highlighted vertices must have the following colors.
T
OF
(x1 Úx2 Úx3)Ù(x1 Úx2 Úx3)Ù(x1 Úx2 Úx4)Ù(x1 Úx3 Úx4) F
TO
FF
The University of Sydney x1 x2 x3 Page 18

3-SAT Reduces to 3-COLOR
Construction of G:
3.
– –
Clause gadget.
For each clause, add 5 new vertices, connecting them and the corresponding variable vertices with T in the following manner.
Suppose both left and middle variable vertices colored with F. Then, the highlighted vertices must have the following colors. In particular, the right
variable vertex must be colored T.
T
OF
(x1 Úx2 Úx3)Ù(x1 Úx2 Úx3)Ù(x1 Úx2 Úx4)Ù(x1 Úx3 Úx4) F
TO
FF
T
The University of Sydney x1 x2 x3 Page 19

3-SAT Reduces to 3-COLOR
Claim: For each clause gadget, a coloring of variable vertices using T and F colors can be extended to a proper 3-coloring of the entire gadget iff at least one variable vertex is colored T.
Proof:
Þ Done in previous slide.
Ü Check all 7 such colorings by hand.
T
OF
(x1 Úx2 Úx3)Ù(x1 Úx2 Úx3)Ù(x1 Úx2 Úx4)Ù(x1 Úx3 Úx4) F
TO
FF
T
The University of Sydney x1 x2 x3 Page 20

3-SAT Reduces to 3-COLOR
Claim: G has a 3-coloring iff F is satisfiable.
Proof: Þ Suppose G has a 3-coloring.
– Assign literals with same color as vertex T true, rest is false.
– We have argued previously that assignment is consistent and every clause has at least one true literal.
Ü Suppose F has a satisfying assignment.
– Color literal vertices and truth gadget accordingly.
– For each clause gadget, can extend to a proper 3-coloring if at least one literal vertex is set to true.
Truth Gadget
The University of Sydney
Variable Gadget
Clause Gadget
Page 21

Lecture 11:
Coping with hardness
The University of Sydney
Page 22

Algorithms and hardness
Algorithmic techniques:
– Greedy algorithms [Lecture 3]
– Divide & Conquer algorithms [Lectures 4 and 5]
– Dynamic programming algorithms [Lectures 6 and 7]
– Network flow algorithms [Lectures 8 and 9]
Hardness:
– NP-hardness [Lectures 10 and 11]: O(nc) algorithm is unlikely
Today
– How can we cope with hard problems? The University of Sydney
Page 23

Algorithms and hardness
Lots of problems that we can solve efficiently:
– MST
– Shortest path
– Scheduling
– Max flow –…
But lots of problems that we can’t solve efficiently:
– All NP-complete problems: O(nc) algorithm is unlikely vertex cover, independent set, 3-SAT,…
– But what if we need to solve an NP-complete problem? The University of Sydney
Page 24

Cope with NP-complete problems?
The University of Sydney Page 25

Cope with NP-complete problems?
• Heuristics: Local search, simulated annealing, neural networks…
• Randomized algorithms: Not always correct, but a probability is
guaranteed.
• Approximation algorithms: Not optimal solution, but within a guaranteed
error.
• Fixed-parameter algorithms: Algorithms whose complexity depends on
other parameters than n.
• Efficient exact algorithms: Euclidean TSP
• Restricted instance: trees, bipartite graphs…
The University of Sydney
Page 26

Coping With NP-Completeness
Question: What should I do if I need to solve an NP-complete problem?
Answer: Theory says you’re unlikely to find poly-time algorithm.
Must sacrifice one of three desired features. – Solve problem to optimality.
• Approximation algorithms
• Randomized algorithms
– Solve problem in polynomial time.
• Exact exponential time algorithms
– Solve arbitrary instances of the problem.
• Solve restricted classes of instances • Parametrized algorithms
The University of Sydney
Page 27

10.1 Solving restricted instances
For example in the case when the vertex cover is small.
The University of Sydney Page 28

10.1 Finding Small Vertex Covers
VERTEX COVER: Given a graph G = (V, E) and an integer k, is there a subset of vertices S Í V such that |S| £ k, and for each edge (u, v) either u Î S, or v Î S, or both.
16 27
38 49
5 10
k=4
S = { 3, 6, 7, 10 }
The University of Sydney
Page 29

Vertex Cover
VERTEX COVER: Given a graph G = (V, E) and an integer k, is there a subset of vertices S Í V such that |S| £ k, and for each edge (u, v) either u Î S, or v Î S, or both.
Vertex Cover (or Independent Set) arises naturally in many applications:
– dynamic detection of race conditions (distributed systems).
– computational biology
– Biochemistry
– Pattern recognition
– Computer vision –…
What should we do if we need to solve it?
The University of Sydney
Page 30

Finding Small Vertex Covers
Question: What if k is small?
Brute force: O(knk+1).
– Try all nk Î O(nk) subsets of size k.
– Takes O(kn) time to check whether a subset is a vertex cover.
Aim: Limit exponential dependency on k, e.g., to O(2k kn).
Example: n = 1000, k = 10.
– Brute force. knk+1 = 1034 Þ infeasible. – Better. 2k kn = 107 Þ feasible.
Remark. If k is a constant, algorithm is poly-time; if k is a small constant, then it’s also practical.
The University of Sydney
Page 32

Finding Small Vertex Covers
Theorem: Let (u,v) be an edge of G. G has a vertex cover of size £ k iff at least one of G\{u} and G\{v} has a vertex cover of size £ k-1.
delete u and all incident edges
Proof:
uv
Þ
– Suppose G has a vertex cover S of size £ k.
– S contains either u or v (or both). Assume it contains u.
– S\{u} is a vertex cover of G\{u}. Ü
– Suppose S is a vertex cover of G\{u} of size £ k-1.
– ThenSÈ{u}isavertexcoverofGofsizek. ▪
G\{u}
The University of Sydney
Page 35

Finding Small Vertex Covers: Algorithm
Theorem: The following algorithm determines if G has a vertex cover of size £ k in O(2k kn) time.
uv
G,k
G\{u} k-1
boolean Vertex-Cover(G,k) {
if (G contains no edges) return true
if (G contains > k(n-1) edges) return false
let (u,v) be any edge of G
a = Vertex-Cover(G\{u},k-1)
b = Vertex-Cover(G\{v},k-1)
return a or b
}
The University of Sydney
Page 37

Finding Small Vertex Covers: Algorithm
Theorem: The following algorithm determines if G has a vertex cover of size £ k in O(2k kn) time.
uv
G,k
boolean Vertex-Cover(G,k) {
if (G contains no edges) return true
if (G contains > k(n-1) edges) return false
let (u,v) be any edge of G
a = Vertex-Cover(G\{u},k-1)
b = Vertex-Cover(G\{v},k-1)
return a or b
}
G\{u} k-1
G\{v}
k-1 £k
The University of Sydney
Page 38

Finding Small Vertex Covers: Algorithm
Theorem: The following algorithm determines if G has a vertex cover of size £ k in O(2k kn) time.
boolean Vertex-Cover(G,k) {
if (G contains no edges) return true
if (G contains > k(n-1) edges) return false
let (u,v) be any edge of G
a = Vertex-Cover(G\{u},k-1)
b = Vertex-Cover(G\{v},k-1)
return a or b
}
uv
G,k
G\{u} k-1
G\{v}
k-1 £k
Proof:
– Correctness follows from previous two claims and induction on k. – There are £ 2k+1 nodes in the recursion tree; each invocation
takes O(kn) time. ▪ The University of Sydney
Page 39

Finding Small Vertex Covers: Algorithm
Theorem: Vertex cover can be solved in O(2k kn) time. This is fine as long as k is (a small) constant.
What if k is not a small constant?
uv
G,k
G\{u} k-1
G\{v}
k-1 £k
The University of Sydney
Page 40

10.2 Solving NP-Hard Problems on restricted input instances
For example special cases of graphs: – trees,
– bipartite graphs,
– planar graphs,
–…
The University of Sydney
Page 41

Independent Set on Trees
INDEPENDENT-SET: Given a graph G = (V, E) and an integer k, is there a subset of vertices S Í V such that |S| 3 k, and for each edge at most one of its endpoints is in S?
Problem: Given a tree, find a maximum IS. Key observation: If v is a leaf, there exists
a maximum size independent set containing v. Proof: [exchange argument]
u v
– Consider a max cardinality independent set S.
– IfvÎS,we’redone.
– IfuÏSandvÏS,thenSÈ {v}isindependentÞSnotmaximum. – IF u Î S and v Ï S, then S È {v}/{u} is independent. (exchange) ▪
The University of Sydney
Page 42

Independent Set on Trees: Greedy Algorithm
Theorem: The following greedy algorithm finds a maximum cardinality independent set in forests (and hence trees).
u v
Independent-Set-In-A-Forest(F) { S¬Æ
while (F has at least one edge) {
Let e = (u,v) be an edge such that v is a leaf
Add v to S
Delete from F nodes u and v, and all edges
incident to them.
}
Add remaining vertices to S
return S }
ß
u v
ß
Proof: Correctness follows from the previous key observation. ▪
Remark. Can implement in O(n) time by considering nodes in postorder. The University of Sydney
Page 43

Independent Set on Trees
INDEPENDENT-SET: Given a graph G = (V, E) and an integer k, is there a subset of vertices S Í V such that |S| 3 k, and for each edge at most one of its endpoints is in S?
Problem: Given a tree, find a maximum IS. Theorem:
INDEPENDENT-SET on trees can be solved in O(n) time.
Corollary:
VERTEX-COVER on trees can be solved in O(n) time.
u v
The University of Sydney
Page 44

Weighted Independent Set on Trees
Weighted independent set on trees. Given a tree and node weights wv > 0, find an independent set S that maximizes SvÎS wv.
r
u vwx
children(u) = { v, w, x }
The University of Sydney
Page 45

Weighted Independent Set on Trees
Weighted independent set on trees. Given a tree and node weights wv > 0, find an independent set S that maximizes SvÎS wv.
Observation: If (u, v) is an edge such that v is a leaf node, then either OPT includes u, or it includes all leaf nodes incident to u.
Dynamic programming solution: Root tree at some node, say r. – OPTin(u) = max weight independent set
rooted at u, containing u.
– OPTout(u) = max weight independent set rooted at u, not containing u.
r
u vwx
children(u) = { v, w, x }
OPTin(u) = wu + å OPTout(v) v Î children(u)
OPTout (u) = å max {OPTin (v), OPTout (v)} v Î children(u)
The University of Sydney
Page 47

Weighted Independent Set on Trees: Dynamic Programming
Theorem: The dynamic programming algorithm find a maximum weighted independent set in trees in O(n) time.
u
Weighted-Independent-Set-In-A-Tree(T) {
Root the tree at a node r
foreach (node u of T in postorder) {
if (u is a leaf) { Min [u] = wu
Mout[u] = 0} else {
Min [u] = SvÎchildren(u) Mout[v]+wv
Mout[u] = SvÎchildren(u) max(Mout[v],Min[v])}
}
return max(Min[r], Mout[r]) }
u
Proof: Takes O(n) time since we visit nodes in postorder and examine each edge exactly once. ▪
The University of Sydney
Page 48

Approximation Algorithms
Sacrifice optimality, but still run in polynomial time.
Approximation ratio =
Cost of apx solution Cost of optimal solutions
An approximation algorithm for a minimization problem requires an approximation guarantee:
• Approximation ratio ≤ c
• Approximation solution ≤ c · value of optimal solution
The University of Sydney
Page 73

Vertex Cover
The University of Sydney Page 74

Vertex Cover
Optimization version: Given an undirected graph G = (V, E), find the smallest vertex cover C.
First try: Pick an edge e = (u,v) that is uncovered. Choose one of u and v to add to cover. Repeat.
On a star graph, approximation factor is 𝛀(n)! Example: Star graph with 4 vertices
The University of Sydney
Page 75

Vertex Cover
Weak duality: Let M be a matching, and let C be a vertex cover. Then, |M| £ |C|.
Proof: Each vertex can cover at most one edge in any matching. 1 1′
2 2′
3 3′ 4 4′
5 5′
M = 1-2′, 3-1′, 4-5′ |M| = 3
The University of Sydney
Page 76

Vertex Cover
Weak duality: Let M be a matching, and let C be a vertex cover. Then, |M| £ |C|.
Greedy algorithm:
– Initialise S = empty set
– While there exists an edge e = (u,v) not covered by S:
– AddbothuandvtoS Thm: S is a 2-approximation.
Proof:
– Let M be set edges encountered in while loop. This is a matching.
– Let C* be smallest vertex cover.
– |S| = 2|M| £ 2|C*|.
Not known how to do better! 7/6 is NP-hard. The University of Sydney
Page 77

Randomization
Randomization: Allow fair coin flip in unit time.
Why randomize? Can lead to simplest, fastest, or only known algorithm for a
particular problem.
Example: Symmetry breaking protocols, graph algorithms, quicksort, hashing, load balancing, Monte Carlo integration, cryptography.
The University of Sydney Page 85

13.4 MAX 3-SAT
The University of Sydney Page 86

Maximum 3-Satisfiability
MAX-3SAT: Given 3-SAT formula, find a truth assignment that satisfies as many
clauses as possible.
C1 =x2Úx3Úx4 C2 =x2Úx3Úx4 C3 =x1Úx2Úx4 C4 =x1Úx2Úx3 C5 =x1Úx2Úx4
Remark. NP-hard search problem.
Simple idea: Flip a coin, and set each variable true with probability 1⁄2,
independently for each variable. The University of Sydney
Page 87

Maximum 3-Satisfiability: Analysis
Theorem: Given a 3-SAT formula with k clauses, the expected number of clauses satisfied by a random assignment is 7k/8.
Proof: Consider random variable Zj = ìí1 if clause Cj is satisfied î 0 otherwise.
Let Z = number of clauses satisfied by the assignment Þ linearity of expectation
E[Z] = åk E[Zj] j=1
= åk Pr[clause C j is satisfied] j=1
= 78 k
Z=Z1+Z2+Z3+…+Zk
E[Zi] = Probability that (x Ú y Ú z) is not satisfied?
1⁄2 · 1⁄2 · 1⁄2 = 1/8
The University of Sydney
Page 88

The Probabilistic Method
Corollary: For any instance of 3-SAT, there exists a truth assignment that satisfies at least a 7/8 fraction of all clauses.
Proof: There must be an assignment that performs at least as well as the expectation! ▪
Remark: Any 3-SAT instance with at most 7 clauses must always be satisfiable.
Probabilistic method: We showed the existence of a non-obvious property of 3-SAT by showing that a random construction produces it with positive probability!
Hardness of Approximation: NP-hard to do better than 7/8!
The University of Sydney Page 89

Summary
NP-complete problems show up in many applications. There are different approaches to cope with it:
• Approximation algorithms
• Restricted cases (trees, bipartite graphs, small solution…)
• Randomized algorithms •…
Each approach has its pros and cons.
The University of Sydney Page 92

Related Posts