跳转至

NP问题

概念

  • P: 能在多项式时间O(\(n^k\)) 内解决的问题

  • NP: 不能在多项式时间内解决或不确定能不能在多项式时间内解决，但能在多项式时间验证（检验一组解是否满足）的问题，P\(\subseteq\)NP

  • NPC: NP完全问题，所有NP问题在多项式时间内都能约化(Reducibility)到它 的NP问题，即解决了此NPC问题，所有NP问题也都得到解决。

  • NP hard: NP难问题，所有NP问题在多项式时间内都能约化(Reducibility)到它 的问题(不一定是NP问题)。

image-20230704230802879

NP完全问题：找不到多项式算法，也无法证明不存在多项式时间算法

  • 最短路径判定版本
  • 哈密顿圈
  • 3-CNF可满足性问题
  • 先证明它至少是一个NP问题，再证明其中一个已知的NPC问题能约化到它（由约化的传递性，则NPC问题定义的第二条也得以满足；至于第一个NPC问题是怎么来的，下文将介绍），这样就可以说它是NPC问题了。
  • 已知的NPC：SAT问题，Vertex cover，TSP判定版本（求最短回路的是NPhard但不是NPC，一般说TSP都指的是NPC的TSP）
  • Reduction(规约)：如果能找到这样一个变化法则，对任意一个程序A的输入，都能按这个法则变换成程序B的输入，使两程序的输出相同，那么我们说，问题A可约化为问题B。
  • x在多项式时间规约到y （x \(\leq_p\)y）

例子

停机问题

最短路问题

  • (G,s,t,k)：s到t是否有＜=k长的路径
  • decision问题 -> 等价于一个集合
    • instance: -> String

3-CNF问题

  • satisfability问题（SAT）
  • 对一组赋值，证明可满足
  • 3-SAT：有k个clause，the MAX-3SAT problem is to find a truth assignment that satisfies as many clauses as possible.
    • 每一个clause都是 a || b || c 的形式
  • B() is an efficient verifier(验证器) for problem X if
    • B为多项式时间算法
    • P() is a poly function且满足对任意s，s属于X当且仅当存在string t使得B(s,t) = yes，其中|t|<=P(|s|)
  • B(s,t)：在t下计算s，若s满足，返回yes
  • 只要求存在性，yes-certificate

哈密顿圈（HCP）

  • hint：一组圈
  • B：按照hint走一遍，检查是否每个点都走了一次

Travelling Salesman Problem（TSP）

  • 给一张完全图G和整数k，问是否存在简单环使得每个点走一次且cost<=k
  • HCP \(\leq_p\)TSP
    • 补成完全图，原来的边设为1，补上的边设为2，若HCP成立，则TSP的k取为|v|即可
    • 实例的转化为多项式时间

最大团问题（clique problem）

  • 给出G和k
  • 问是否能选出至少k个点使得两两之间都有边相连（为团）

顶点覆盖问题（vertex cover problem）

  • 给出G和k
  • 是否有一个点集保证每条边至少有一个端点被选中
  • clique problem \(\leq_p\) vertex cover problem
    • 边集互补
    • 点集C在G里是团当且仅当在V-C在G'里是顶点覆盖

习题

1.If L1 ≤p L2 and L2∈NP, then L1∈NP.

T，注意<=p等价于reduce to，复杂的如果是Np，那么简单的也是NP

2.All NP-complete problems are NP problems. T

3.All the languages can be decided by a non-deterministic machine.

F，不确定图灵机可以用来验证NP问题的解是否是正确的，确定图灵机可以用来求解P问题。NP hard问题无法通过不确定图灵机验证

4.All NP problems can be solved in polynomial time in a non-deterministic machine. T

5.If a problem can be solved by dynamic programming, it must be solved in polynomial time.

F，0-1背包问题可以用DP解，但是复杂度不是多项式的, 原因是输入的数据不是多项式的。

6.Among the following problems, __ is NOT an NP-complete problem.

A.Vertex cover problem

B.Hamiltonian cycle problem

C.Halting problem

D.Satisfiability problem

D SAT问题是第一个被证明的NPC问题，A是NPC问题，B是汉密尔顿回路，NPC问题。C停机问题是不可解的，选C

7.Suppose Q is a problem in NP, but not necessarily NP-complete. Which of the following is FALSE?

A.A polynomial-time algorithm for SAT would sufficiently imply a polynomial-time algorithm for Q.

B.A polynomial-time algorithm for Q would sufficiently imply a polynomial-time algorithm for SAT.

C.If Q ∉P, then P≠NP.

D.If Q is NP-hard, then Q is NP-complete.

看上面的图，SAT是NPC问题，如果解决了，可以解决所有NP问题

B， Q不一定是NPC的，所以不对，C，如果Q不是P，那么说明NP没有被解决，D，NP-hard和NP交集是NPC

8.A language L belongs to NP iff there exist a two-input polynomial-time algorithm A that verifies language L in polynomial time.

T， 这是ppt上的

9.Given that problem A is NP-complete. If problem B is in NP and can be polynomially reduced to problem A, then problem B is NP-complete.

B<= A，但是A是NPC问题，A<=B才能说明B也是NPC问题。

10.All decidable problems are NP problems.

F，还有NP hard问题

11.All NP problems are decidable.

T, 可以通过不确定图灵机判断

12.To prove problem B is NP-complete, we can use a NP-complete problem A and use a polynomial-time reduction algorithm to transform an instance of problem B to an instance of problem A.

F, 应该不是一个实例，而是整个问题

13.If P = NP then the Shortest-Path (finding the shortest path between a pair of given vertices in a given graph) problem is NP-complete.

T, P=NP说明所有的NP问题均可解，所有的NPC问题可解，NP=NPC