P vs NP问题

|--P vs NP
  多项式时间求解 vs 多项式时间验证

    P --> polynomial time
  多项式时间
  O(1) O(logn) O(n) O(nlogn) O(n^2) O(n^3) O(n^4)

    NP --> nondeterministic polynomial

|--NP Complete
  eg:
    3 - SAT问题
    boolean x1, x2, x3, ....., xn

    CNF
    (x1 || x2 || x3) && (x1 || !x2 || !x3) && (!x1 || x4 || x5) = true

    存在一个数x1, x2, x3, x4, x5使true

     ____________
    |         |
    | NP       |
    |------ |    |
       | P     |    |
    |     |   |
    -------------
  eg:
    CLIQUE 图论问题
    全连接图

    G --> k clique

    如何证明是NP Complete问题
      x --> y

    先证明是NP问题

    3-SAT <= CLIQUE 在多项式时间内

  eg:
    Independent Set问题
      k = 3
  eg:
    Vertex Cover
      k = 3

上一篇:AcWing:239. 奇偶游戏(前缀和 + 离散化 + 带权并查集 + 异或性质)


下一篇:一种在程序中求两直线交点的简单数学方法