算法设计与分析笔记0x0C —— Part 1 NP完全

Algorithm design patterns.

  • Greedy.
  • Divide-and-conquer.
  • Dynamic programming.
  • Max-flow min-cut.
  • Reductions.

Algorithm design anti-patterns.

  • NP-completeness.
  • PSPACE-completeness.
  • Undecidability.

Polynomial-Time Reductions

  • Definition: > Problem X polynomial-time reduces to problem Y if arbitrary instances of problem X can be solved using: > 1. Polynomial number of standard computational steps, plus > 2. Polynomial number of calls to oracle that solves problem Y.
  • Notation: XpY
  • Design algorithms. If XpY and Y can be solved in polynomial-time, then X can also be solved in polynomial time.
  • Establish intractability. If XpY and X cannot be solved in polynomial-time, then Y cannot be solved in polynomial time.
  • Establish equivalence. If XpY and YpX, we use notation XpY. In this case, X can be solved in polynomial time iff Y can be.

1. Reduction by Simple Equivalence

  • Independent Set: 两两互不相邻的顶点构成的集合
    • Given a graph G = (V, E) and an integer k, is there a subset of vertices S V such that |S| k, and for each edge at most one of its endpoints is in S?

  • Vertex Cover: 一个集合,使得每条边至少有一个点在集合中
    • Given a graph G = (V, E) and an integer k, is there a subset of vertices S V such that |S| k, and for each edge, at least one of its endpoints is in S?

  • 互为补集,可相互归约. VERTEX-COVER =p INDEPENDENT-SET
  • Pf. S is an independent set iff V – S is a vertex cover.
    • =>
      • Let S be any independent set.
      • Consider an arbitrary edge (u,v).
      • S independent => u ∉ S or v ∉ S => u ∈ V − S or v ∈ V − S.
      • Thus, V-S covers (u,v).
    • <=
      • Let V-S be any vertex cover.
      • Consider two nodes u ∈ S and v ∈ S.
      • Observe that (u,v) E since V-S is a vertex cover.
      • Thus, no two nodes in S are joined by an edge => S is independent set.

2. Reduction from Special Case to General Case

  • Set Cover Given a set U of elements, a collection S1, S2,… ,Sm of subsets of U, and an integer k, does there exist a collection of k of these sets whose union is equal to U?
  • VERTEX-COVER p SET-COVER
  • Pf. Given a VERTEX-COVER instance G = (V, E), k, we construct a set cover instance (U,S) whose size equals the size of the vertex cover instance.
  • Construction
    • Create SET-COVER instance:
      • k=k, U=E, Sv = {e ∈ E: e incident to v}
    • Set-cover of size k iff vertex cover of size k.

3. Reductions via “Gadgets”

  • Literal A boolean variable or its negation.
    • xi or $\overline{x_i}$
  • Clause A disjunction of literals.
    • $C_j = x_1 \vee \overline{x_2} \vee x_3$
  • Conjunctive Normal Form 合取范式 A propositional formula Φ that is the conjunction of clauses.
    • Φ = C1 ∧ C2 ∧ C3 ∧ C4
  • SAT Given CNF formula Φ, does i have a satisfyling truth assignment?
  • 3-SAT SAT where each clause contains exactly 3 literals.

3-SAT p INDEPENDENT-SET
Pf. Given an instance Φ of 3-SAT , we construct an instance (G, k) of INDEPENDENT-SET that has an independent set of size k iff Φ is satisfiable.
Construction:

  • G contains 3 vertices for each clause, one for each literal.
  • Connect 3 literals in a clause in a triangle.
  • Connect literal to each of its negations.

G contains independent set of size k=| Φ | iff Φ is satisfiable.

  • Pf. <= Given satisfying assignment, select one true literal from each triangle. This is an independent set of size k.
  • Pf. => Let S be independent set of size k.
    • S must contain exactly one vertex in each triangle.
    • Set these literals to true, and any other variables in a consistent way
    • Truth assignment is consistent and all clauses are satisfied.
  • Note:
    • each triangular has one node to be chose.
    • each sat has one true literal to be chose.
    • finally we choose k nodes

Self-Reducibility

  • Decision Problem. 判定问题
    • e.g. Does there exist a vertex cover of size k?
  • Optimization Problem. 优化问题
    • e.g. Find vertex cover of minimum cardinality.
  • Self-reducibility Optimization problem p decision version.
    • Justifies our focus on decision problem.

Ex: to find min cardinality vertex cover.

  • (Binary) search for cardinality k* of min vertex cover.
  • Find a vertex v such that G – {v} has a vertex cover of size k* – 1.
    • v must be in a vertex cover of size k*
    • Prove by construction: a vertex cover of G – {v} plus v must be a vertex cover of G
  • Include v in the vertex cover.
  • Recursively find a min vertex cover in G – {v}.

Definitions

P. Decision problems for which there is a poly-time algorithm?
NP. 存在多项式时间的验证算法,返回yes
– NP stand for nondeterministic polynomial-time.

EXP. 存在指数级时间算法的决策问题. (指上界,若是多项式时间算法,亦属于EXP)
NP-Complete 一个属于NP的问题,所有NP中的其他问题都能归约到这个问题
co-NP NP的补集,对一个否定实例,存在一个简洁的验证算法
Asymmetry of NP 去证明一个实例的错误的(NP为证明一个实例是正确的)
NP-hard A problem such that every problem in NP reduces to it.

Certifiers and Certificates

Certification algorithm intuition.

  • Certifier views things from “managerial” viewpoint.
  • Certifier doesn’t determine whether s X on its own; rather, it checks a proposed proof t that s X.

Def. Algorithm C(s, t) is a certifier for problem X if for every string s, s X iff there exists a string t such that C(s, t) = yes.

  • where string t is the “certificate” or “witness”

Examples. 1. COMPOSITES. Given an integer s, is s composite? 是否为合数?

  1. 3-SAT
  2. Hamiltonian Cycle 一笔画问题

Check that the permutation contains each node in V exactly once, and that there is an edge between each pair of adjacent nodes in the permutation.

Claim. P NP
Pf. Consider any problem X in P

  • By definition, there exists a poly-time algorithm A(s) that solves X.
  • Certificate: t = ϵ, certifier C(s, t) = A(s).

Claim. NP EXP
Pf. Consider any problem X in NP

  • By definition, there exists a poly-time certifier C(s, t) for X.
  • To solve input s, run C(s, t) on all strings t with |t| p(|s|).
  • Return yes , if C(s, t) returns yes for any of these.

NP-Completeness

Def. Problem X polynomial reduces (Cook) to problem Y if arbitrary instances of problem X can be solved using:

  • Polynomial number of standard computational steps, plus
  • Polynomial number of calls to oracle that solves problem Y.

Def. Problem X polynomial transforms (Karp) to problem Y if given any input x to X, we can construct an input y in poly-time such that x is a yes instance of X iff y is a yes instance of Y.

  • 多项式时间构造Y的输入,再调用Y的算法
  • We blur the distinction of these two conscepts.

Theorem. Suppose Y is an NP-complete problem. Then Y is solvable in poly-time iff P = NP.
Pf. <= If P = NP then Y can be solved in poly-time since Y is in NP.
Pf. => Suppose Y can be solved in poly-time.

  • Let X be any problem in NP. Since X p Y, we can solve X in poly-time. This implies NP P.
  • We already know P NP. Thus P = NP.

Leave a Reply

Your email address will not be published.