P问题,NP问题,NPC问题,NPH问题概念。’0/1背包判定问题是NPC问题‘和‘0/1背包问题是NPH问题但不是NPC问题’以及碰撞集是NPC问题‘证明。

概念


  • P问题:如果一个问题能找到在多项式时间内解决它的算法,那么该问题是P问题。
  • NP问题:如果可以在多项式时间内验证一个问题的解的正确性,那么该问题是NP问题。
  •  NPC问题:一个NPC问题需要同时满足两个条件:(1)该问题是NP问题;(2)NP里所有问题可以在多项式时间内归约到该问题。
  •  NPH问题:满足NPC中的条件(2)的问题,就是NPH问题。NPC问题是NPH问题的子集。


题1、0/1背包判定问题是NPC问题

题:已知带权集合的划分问题是 N PC 问题, 试证明 0/1 背包判定问题是 N PC 问题.

问题描述例:给定一个有限集合 X,对每一个 x\in X,对应一个值 w(x)\in Z^{+},和相应的值 p(x)\in Z^{+}。另外,还有一个容量约束 M\in Z^{+} 和一个价值目标 K\in Z^{+} 。

:是否存在X的一个子集X',使得\sum_{x\in X'}^{}w(x) \leq M,而且\sum_{x\in X'}^{}p(x) \geq K

解答:

        step1:证明0/1 背包判定问题是NP问题

        给定集合X的一个子集X',判定\sum_{x\in X'}^{}w(x) \leq M并且\sum_{x\in X'}^{}p(x) \geq K,仅需2*(|X'| - 1)次的加法运算,其中|X'|表示X'的元素个数,时间复杂度是:T(n) = O(|X'| - 1),即在多项式时间内完成判定,所以0/1背包判定问题是NP问题。

        step2:考虑特殊情况,令所有w(x) = p(x),并且取M=K=\frac{1}{2}\sum_{x\in X'}^{}w(x)。这个0/1背包判定问题回答“是”,当且仅当集合X划分问题回答“是”。已知划分问题为NPC问题,故0/1 背包判定问题是 N PC 问题。


题2、0/1背包问题是NPH问题

问题描述:有n个物品,它们有各自的体积w_{i}和价值p_{i},现有给定容量M的背包,如何让背包里装入的物品具有最大的价值总和?

解答:

        要得到max\sum_{i=1}^{n}x_{i}p_{i}   (s.t \sum_{i=1}^{n}x_{i}w_{i}\leq M),需要比较所有的X=(x_{1},x_{2},...,x_{n})x_{i}\in\left \{ 0,1 \right \},这有2^{n}个可能,以比较为基础的求最大问题复杂度下界O(n),故本问题时间复杂度是O(2^{n}),不存在多项式时间的算法,所以0/1背包问题不是NPC问题。

但0/1背包判定问题是NPC问题,0/1背包问题不比其更容易,所以,它是NPH问题。


题3:碰撞集(相遇集)是NPC问题证明。

问题描述:给一组集合\left \{ S_{1}, S_{2},..., S_{n} \right \}和预算b,问是否存在一个集合H满足|H|\leq b,此集合和所有的S_{i}相交为\varnothing,其中|H|是集合H的元素个数。

解答:

        step1:验证碰撞集为NP问题,只需要验证|H|\leq b,且集合H与任意S_{i}相交不为\varnothing,显然知时间复杂度为O(n|H||S|),在多项式时间内可以完成,故碰撞集是NP问题。

        step2:已知顶点覆盖(vertex cover)问题是NPC问题,归约至目标问题:

        (1)构建图G为碰撞集的映射:其中图G的每一个点对应碰撞集的每个元素,每条边对应S_{i}

        (2)b个点的vertex cover 集 对应规模大小为b的碰撞集 :对于每一条边,至少有一个端点在b个点的vertex cover集 中,所以这个集合和S_{i}相交不为\varnothing,此集合对应碰撞集。

        (3)规模大小为b的碰撞集对应b个点的vertex cover集:任意的S_{i}和碰撞集相交不为\varnothing,则对应每条边支少有一个端点被选中,此碰撞集对应vertex cover 集。

综上所述,顶点覆盖问题可以归约到碰撞集,因此碰撞集也是NPC问题。

碰撞集问题借鉴

背包问题借鉴

相关推荐

  1. npm install老卡住什么问题

    2024-04-02 14:00:01       27 阅读
  2. NPM运行保存问题解决

    2024-04-02 14:00:01       16 阅读
  3. npm run lint 格式化问题

    2024-04-02 14:00:01       6 阅读
  4. node.js npm 版本匹配问题

    2024-04-02 14:00:01       21 阅读
  5. 01背包问题dp

    2024-04-02 14:00:01       6 阅读
  6. 01背包问题

    2024-04-02 14:00:01       5 阅读

最近更新

  1. android 内存优化

    2024-04-02 14:00:01       0 阅读
  2. oracle控制文件的管理

    2024-04-02 14:00:01       0 阅读
  3. el-table 表格从下往上滚动,触底自动请求新数据

    2024-04-02 14:00:01       0 阅读
  4. jQuery高级使用

    2024-04-02 14:00:01       0 阅读
  5. 多线程批量导入mysql

    2024-04-02 14:00:01       0 阅读
  6. vue2 mixins混入

    2024-04-02 14:00:01       0 阅读
  7. HashTable和ConcurrentHashMap的区别

    2024-04-02 14:00:01       0 阅读
  8. 前端错误监控的方法有哪些

    2024-04-02 14:00:01       0 阅读

热门阅读

  1. 洛谷 1803.凌乱的yyy

    2024-04-02 14:00:01       5 阅读
  2. Git学习

    Git学习

    2024-04-02 14:00:01      4 阅读
  3. 关于 MySQL 优化(详解)

    2024-04-02 14:00:01       4 阅读
  4. 面试题:Spring Boot中如何实现健康检查与监控

    2024-04-02 14:00:01       5 阅读
  5. FastAPI+React全栈开发19 React Hooks事件和状态

    2024-04-02 14:00:01       5 阅读
  6. Linux查询mac物理地址

    2024-04-02 14:00:01       4 阅读
  7. 单例模式:确保一个类只有一个实例的设计模式

    2024-04-02 14:00:01       5 阅读
  8. [TS面试]TS中使用Union Types时注意事项?

    2024-04-02 14:00:01       4 阅读
  9. 一点点的金融

    2024-04-02 14:00:01       3 阅读