np-complete

1热度

1回答

如果P不等于NP可以证明没有近似算法进入最佳顶点覆盖的k，其中k是一个固定的常数？

0热度

1回答

我读过多个答案，发现有向图中的所有循环都是NP完全的，但约翰逊的算法在图中找到所有简单循环，运行在O（（V + E）（C + 1））时间（其中C是图中强连通分量的数目），我认为这是多项式，因为E < = V^2和C变成O（V^3）的V，对吗？约翰逊的算法：http://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF

2热度

1回答

生成所有字符串排列NP完成？

通过尝试所有可能性，可以在O（n！）中计算给定字符串的所有字符串置换。现在，看看旅行商问题，我们可以通过尝试所有城市排列来解决它。假设我们有城市A，B和C. 假设我们从城市A开始。通过计算BC字符串的所有排列，我们得到ABC ACB，然后我们只求和（在多项式时间内，AB，CB和CA之间的距离为第一种情况...）因此，这不是所有字符串排列的旅行商问题的减少，并不是一个NP完整的问题？

2热度

1回答

NP完整吗？

决策问题：对于给定的图G和数字“a”，“b”，需要回答是否存在具有至少'b'大小的累积邻域的一组'a'顶点。我们如何证明这个问题是NPC？

0热度

1回答

超图的顶点着色，不均匀性限制NP-hard？

是一个超图的顶点着色，没有统一性限制NP-hard？我看过显示k-联合超图的顶点着色的论文是NP-hard。然而，我找不到任何明确说明在一般情况下（而不仅仅是k均匀）超图的顶点着色是否是NP难的来源。

1热度

1回答

颜色编码算法的最长路径

之前我想说清楚的是它是一个大学作业，我正在寻求帮助理解算法，以便能够实现它。所以我这项任务的是凸轮在这里找到： https://www.labri.fr/perso/dorbec/AA/projet-uno.pdf 基本上，我们有一组由2 INT一个代表的“卡”，表示卡的颜色，另一个用于数。要完成的工作是查找最长的卡片序列，例如UNO游戏中下一张卡片的颜色或颜色相同或编号相同。因为在诅咒中已经

1热度

2回答

提出多项式算法

给定n个检查，每个任意（整数）货币值，决定检查是否可以分成具有相同货币值的两个部分。我非常想到如何解决这个问题。有没有一种算法可以在多项式时间内解决这个问题，还是NP-Complete？

0热度

2回答

如果Y在多项式时间内可以归约为X，那么X至少和Y一样硬呢？

我很难理解两类问题的复杂性之间的关系，比如NP-hard和NP-complete问题。答案在https://stackoverflow.com/a/1857342/状态：直观地说，这些都是至少一样努力的NP完全问题的问题。请注意，NP-hard问题不必在NP和中，它们不必是决策问题。这里的确切定义是：问题X是NP难的，如果有一个NP完全问题Y，这样Y还原为X在多项式时间。如果问题Y可以在多

5热度

1回答

算法在处理器上调度作业

根据iehrlich的评论（感谢btw），术语“调度”可能是误导，这可能是一个更合适的描述：给定一个矩阵N * N，找到一个行排列，将产生最大的对角线总和。我有一组N个就业机会和N处理器。所有处理器可以彼此不同。对于每个（作业，处理器）对，我都具有在该处理器上运行该作业的性能。性能是在IPC（指令每周期）中测量的。我试图发现最大化IPC的整体和时间表（1对1的分配）。我可以通过检查所有可能的时

0热度

1回答

0,1背包减少子集总和

我知道如何将子集和减少到0,1背包。但是是否有可能将背包减少到子集总和？怎么样？