L19&L20 NP

Posted on Edited on In Views:

Outline:

  • Decision Problem
  • The class P
  • The class NP
  • Reduction between problems
  • NP-Complete Problems
  • Other advanced topics

Ref:

  • 算法设计与分析(Algorithm design and analysis) by 黄宇

Decision Problem

  • Statement of a decision problem
    • Part 1: instance description defining the input
    • Part2: question stating the actual yes-or-no question
  • A decision problem is a mapping from all possible inputs into the set {yes, no}

Optimization vs. Decision

  • Usually, an optimization problem can be rephrased as a decision problem.
    • 优化问题往往比判定问题难
  • If the decision problem can't be solved in polynomial time, then the corresponding optimization problem can't be either.
  • Often, it can be proved that the decision can be solved in polynomial time if and only if the corresponding optimization problem can. （ 通常， 判定问题在多项式时间可解当且仅当优化问题在多项式时间可解）

Some Typical Decision Problems

  • Graph coloring
    • Given a undirected graph G and a positive integer k, is there a coloring of G using at most k colors?
  • Job scheduling with penalties
    • Given a group of jobs, each with its execution duration, deadline and penalty for missing the deadline, and a nonnegative integer k, is there a schedule with the total penalty bounded by k?
  • Bin packing
    • Given k bins each of capacities one, and n objects with size \(s_1,\dots,s_n\), (where \(s_{i}\) is a rational number in (0,1] ). Do the n objects fit in k bins?
  • Knapsack
    • Given a knapsack of capacity C, n objects with sizes \(s_1, \dots, s_n\) and "profits" \(p_1, \dots, p_n\), and a positive integer k. Is there a subset of the n objects that fits in the knapsack and has total profit at least k?
      • ( Subset sum as a simplified version )
  • CNF-Satisfiability
    • Given a CNF formula, is there a truth assignment that satisfied it?
  • Hamiltonian cycles or Hamiltonian paths
  • Traveling salespersion
    • 带权完全图，问是否存在总权小于 k 的哈密尔顿回路？

Theory of NP-Completeness

  • What it cannot do
    • Provide a method of obtaining polynomial time algorithms for those "hard" problems. 不能为难问题提出高效解
    • Negate the existence of algorithms of polynomial complexity for those problems. 不能否定难问题的高效解的存在
  • What it can do
    • Show that many of the problems for which there is no known polynomial time algorithm are computationally related. 可以给问题难度分档

The class P

  • A polynomially bounded algorithm
    • is one with its worse-case complexity bounded by a polynomial function of the input size
  • A polynomially bounded problem
    • is one for which there is a polynomially bounded algorithm.
      • "bounded"： 问题只要小于等于多项式时间。 如O(logn)不是多项式，但是小于多项式，这也算多项式可解
  • The class P is the class of decision problems that are polynomially bounded

Notes one the class P

  • Class P has a too broad coverage
  • However
    • The problem not in P must be extremely expensive and probably impossible to solve in practice.
    • The problems in P have nice "closure" properties for algorithm integration.
    • The property of being in P is independent of the particular formal model of computation used.

The class NP

  • A polynomial bounded nondeterministic algorithm( 非确定性算法, 就是猜一个解并验证这个解 )
    • \(O(p(n))\) time for some polynomial function \(p(n)\)
    • For all possible executions
  • The class NP
    • is the class of decision problems for which there is a polynomial bounded nondeterministic algorithm.
  • NP means Non-deterministic P
    • From "deterministic" to "non-deterministic"
    • From "solve a problem" to “verify the answer of a problem"
  • What does NP indicate?
    • Harder problems
    • Not too hard
      • At least, you can quickly understand the answer

Proof of Being in NP

先猜一个解； 对于任意一个猜的解，你都能够验证yes or no, 如果这两个步骤都必定能够在多项式时间内结束，则该问题为NP( NP不是Not P ! )

  • Graph coloring is in NP

    • Phase1 - Guess a certificate
      • Description of the input and the certificate
    • Guess2 - Verify the certificate
      • There are n colors listed: \(c_1,c_2,\dots,c_n\) ( not necessarily different )
      • Each \(c_i\) is in the range \(1,\dots,k\)​ //颜色在范围内
      • Scan the list of edges to see if a conflict exists //颜色有无冲突
    • Phase1 and 2 in polynomial time

  • CLIQUE is in NP

    1
    2
    3
    4
    5
    6
    7
    8
    void nodeteClique( graph G, int n, int k )
    {
    	S = genCertif(); // in O(n)
        if( S is a clique of size k )	Output "accept";
        else Output "reject"; // in O(k^2)
        return

    }

  • SAT

    略

Relation between P and NP

  • An deterministic algorithm for a decision problem is a special case of a nondeterministic algorithm, which means: \(P \subset NP\)​（已证明）

  • Intuition implies that NP is much larger than P. 直觉和经验告诉我们P真包含于NP， 但目前没人能证明

    • The number of possible s is exponential in n.
    • No one problem in NP has been proved not in P.

Reduction between problems

  • 归约： reduce P to Q. 通过解决Q来间接解决P

    • 把P的输入转换为Q的合法输入
    • 并验证正确性（符合Specification）

  • "P多项式时间归约到Q" 记为 \(P \leq_P Q\)​​.

    • 如果解决了Q，根据归约，能够解决P
    • 如果解决了P，还不能根据归约解决Q
    • 这说明Q更难
    • 若Q问题多项式时间可解，可证明P问题也是多项式时间可解。 证明略
    • \(\leq_P\) 是可传递的。（通过多项式的封闭性可证）

NP-Complete Problems

Definition

  • A problem Q is NP-hard if every problem P in NP is reducible to Q, that is \(P \leq_P Q\)​.

    （which means that Q is at least as hard as any problem in NP ）

    • 比所有NP都难或者一样难，但是难度上不封顶，甚至可以不属于NP（ 比如不可判定问题 ）

  • A problem Q is NP-complete if it is in NP and is NP-hard( which means that Q is at most as hard as to be solved by a polynomially bounded nondeterministic algorithm )

P and NP - Revisited

  • Intuition implies that NP is a much larger set than P
    • No one problem in NP has been proved not in P.
  • If any NP - completed problem is in P, then NP = P
    • Which means that every problems in NP can be reducible to a problem in P

Proof of NP-Completeness

  • Knowledge ： P is NPC
  • Task: to prove that Q is NPC
  • Approach: to reduce P to Q
    • 已知 For any \(R \in NP\), $ R _P P$​ ​
    • Show \(P \le_P Q\)
    • Then \(R \le_P Q\), by transitivity of reductions
    • Done. Q is NP-complete ( given that Q has been proven in NP ) 即通过传递性证明Q是NP-hard, 而Q是否为NP需要另外证明
  • 该证明需要知道一个最初的NPC
    • SAT问题, 由Cook提出

Satisfiability Problem

  • CNF
  • CNF-SAT problem
  • a special case: 3-SAT
    • 子句中的布尔量永远小于等于3 ( 永远小于等于二 则成为2-SAT)

Example: Prove CLIQUE is NPC

  • 把3-SAT的输入转换成图作为CLIQUE 的输入,并证明3-SAT的输出(即只能个语句是否为True)等价于CLIQUE的输出

Known NP-Complete Problems

Ref: Computer and Intractability: A guide to the Theory of NP-Completeness,Freeman,1979

Other advanced topics

Advanced algorithms

Approximation

  • Make modification on the problem
    • Restrictions on the input
    • Change the criteria for the output
    • Find new abstractions for a practical situation
  • Find approximate solution
    • Approximation algorithm
    • Bound of the errors
  • 应用: Bin Packing Problem

Randomized Algorithm

  • Mote Carlo
    • Always finish in time
    • The answer may be incorrect
  • Las Vegas
    • Always return the correct answer
    • The running time varies a lot

Online Algorithm

  • The main difference
    • Offline algorithm: you can obtain all your input in advance
    • Online Algorithm: you must cope with unpredictable inputs
  • How to analyze an online algorithm
    • Competitive analysis: the performance of an online algorithm is compared to that of an optimal offline algorithm

Distributed Algorithm

  • Model of distributed computation

Advanced computation models

Distributed Data

  • External memory model