np-complete

1热度

1回答

假设一个为O（n 2 ）-time的α-近似算法存在对于以下每个对的两个问题中的一个：点覆盖和独立设置独立设置并派最大流和最小割这是否保证一个为O（n ）时间阿尔法近似算法存在的对中的其他问题？我知道Clique减少为独立集，而独立集又减少到顶点覆盖。

1热度

1回答

库克定理

我读了这本书计算机和难解性 - NP完整性理论指南 Garey和Johnson为我的算法课程;然而，一年后，在回顾这些材料时，我意识到我从来没有真正理解库克定理。关于这个证明，我理解为什么SAT首先被证明是NP（NP-complete的第一个要求），但是我正在努力通过证明在其他NP问题下的“其他”NP完全问题“遗传”多项式转换为SAT。我在想，如果有人能在一个更淡化的方式解释，这或许会澄清这部

0热度

1回答

子集和多个目标的复杂性

NP-Complete或P中存在以下问题吗？输入：正整数{A1，的集合S A2，...，AN）和一个正整数中号问题：是否存在S的一个子集S”，使得S中的所有元素'总和为M-1，M或M + 1。我的猜测是它在NP-Complete中并且与子集和有关。不过，我很难减少子集和来解决这个问题。

0热度

1回答

是否有可能找到解决NP完全问题的概率？

标题涵盖了整个问题。是否有可能推导出一个函数来肯定地说，一个NP完全问题的建议解决方案有百分之一百的机会是正确的？

1热度

1回答

类布尔到布尔可满足性[多项式时间减少]第2部分

我问几天前，一个关于如何将大学课堂排序问题转换为布尔可满足性问题的问题。（Class Scheduling to Boolean satisfiability [Polynomial-time reduction]）我通过@Amit回答谁是非常优雅，易于代码。基本上，他的答案是这样的：他不考虑课程，而是考虑时间间隔。因此，对于第i个课程，他只是指出了本课程的所有可能的时间间隔。当每个课程至

-2热度

1回答

如果P！= NP，P是否比非P问题多，反之亦然？

如果P！= NP，那么比SuperPolynomial问题还有更多的多项式问题，反之亦然？

0热度

1回答

给定图的顶点的k-着色计算（k-1） - 着色

图的着色顶点是NP完全的常见知识。也知道有高效的贪婪算法可以得到一个近似的解决方案。为什么不使用这些随机贪婪算法来计算k种颜色的着色，然后使用一些较慢的算法来减少k？在我的情况下，我知道足够的颜色图G的最小数量 - 让我们把它称为K.我也设法实现SL算法给我（K + 2） - 着色。一种颜色只用于给一个顶点着色，所以我设法通过手动重新着色一些其他节点来移除它。因此，我有（K + 1）着色，并

-2热度

1回答

查找最小集合覆盖的最快算法

找到最小集合覆盖的最省时和最正确的算法是什么？我不需要代码本身。我想要一个解释或伪代码如何工作。对于一个例子，我们有 Set S = {1,2,3,..,12} Subsets S1 = {1,2,3,4,5,6}, S2 = {5,6,7,8,9}, S3 = {1,4,7,10}, S4={2,5,7,8,11} S5 = {3,6,9,12}, S6 = {10,11} 的分

2热度

1回答

一组顶点不交叠循环，以便每个顶点属于一个循环

这里我有一个有向图G.我需要确定是否存在一组顶点不交集循环，以便每个顶点属于一个循环。我不确定这是否可以在多项式时间或如果它的NP完成？任何人都可以向我指出正确的方向吗？

1热度

1回答

在多项式时间内寻找最大团体的顶点

假设你有一个黑盒子，它可以在不变的时间内解决团体问题。给黑箱一个带有界限k的无向图G，它输出“是”或“否”，图G有一个至少有k个顶点的团。你会如何使用这个黑匣子在多项式时间内找到最大派系的顶点？