博客

卡普的21个NP完全问题-问题描述

  • Post author:
  • Post category:其他


以下部分为卡普21个问题的名称（来自于维基百科https://zh.wikipedia.org/wiki/%E5%8D%A1%E6%99%AE%E7%9A%84%E4%BA%8C%E5%8D%81%E4%B8%80%E5%80%8BNP-%E5%AE%8C%E5%85%A8%E5%95%8F%E9%A1%8C）

卡普的21个问题列表如下，多数以问题的原名，加上巢状排版表示出这些问题归约的方向。举例，

背包问题

（Knapsack）是NP-完全问题的证明，是从

精确覆盖问题

归约到背包问题，因此背包问题列为精确覆盖问题的子项。

##########################################################################################################

问题描述：

布尔可满足性问题：

给定一个布尔方程， 判断是否存在一组布尔变量的真值指派使整个方程为真的问题

0-1整数规划

给定一个整数矩阵C和一个整数向量d，判断是否存在一个0-1向量x，使得Cx=d

分团问题

给定无向图G和正整数k，判定G中是否包含有大小为k的集团。

Set packing

给定一个有限集合S和一些S的子集，求问是否可以其中的k个子集，它们两两不相交。

最小顶点覆盖问题

给定图 G=(V,E)和数k，判定是否存在包含大小至多为k的顶点覆盖。

集合覆盖问题

给定全集U，以及一个包含n个集合且这n个集合的并集为全集的集合S。集合覆盖问题要找到S的一个最小的子集，使得他们的并集等于全集。

反馈点集问题

给定有向图H和整数k，判定是否存在集合R⊆V，其中有向图H中的每个有向环都包含R中的一个点。

反馈弧集问题

给定有向图H和整数k，判定是否存在集合S⊆E，其中有向图H中的每个有向环都包含E中的一个边。

有向哈密尔顿环

给定有向图H，判定其是否经过图中每个顶点且仅一次的回路。

无向哈密尔顿环

给定无向图G=(V,E)，判定其是否经过图中每个顶点且仅一次的回路。

每句话至多3个变量的布尔可满足性问题

给定三元合取范式f，对布尔表达式f中的布尔变量赋值，是否可使f的真知为真。

图着色问题

给定无向图G=(V,E),用k中颜色为V中的每一个定点分配一种颜色，使得不会有两个相邻定点具有同一种颜色。

分团覆盖问题

给定无向图G’和整数k，判定N’是k的联合，并且是较少团。

精确覆盖问题

给定了一个全集S以及它的m个子集S1、S2、..Sm以后，要求出一组子集，使这组子集的并等于原来的全集S，且各子集两两不交。

Hitting set 问题

给定一个由 n 个元组组成的有限集合 S ={S1 , …, Sn}, 元组中的元素取自符号集 U ={u1 , …, um}, 判定集合U 是否存在一个子集 U′, U′≤k ,使得对于 S 中的任何一个元组 Si, 满足 Si ∩U′≠φ

Steiner tree 问题

给定无向图 G=(V E)及子集 R ⊆V 图中每条边权值wr∈R+。找出连接R中所有顶点且边权值之和最小的树。

三维匹配问题


存在一个集合


M


⊆


W×X×Y


，并且


W


，


X


，


Y


为不想交的集合，


|W|=|X|=|Y|=q


。判定是否存在一个集合


M’


⊆


M


，使得


|M’|=q


，并且


M’


在


W


，


X


，


Y


三维上不存在交集。

背包问题

给定的整数 Cj,j=1,2,…n和b，判定是否存在{1,2,…,n}的子集B，使得(C1+C2+…+Cj) =b

Job sequence问题

给定m个性能相同的处理器，n个作业J1,J2,…Jn，每个作业的运行时间t1,t2,…tn以及时间T，是否可以调度这m个处理器，使得他们最多在时间T里完成这n个作业。

划分问题

给定一个具有n个整数的集合S，是否能把S划分成两个子集S1和S2，使得S1中的整数之和等于S2中的整数之和

最大割问题

给定无向图G，有权函数w：A->Z。判定是否有集合S ⊆N使得：