问题标签 [np-complete]

我正在从 tardos 的算法设计书中阅读 NP 完整性，在证明子集总和是 NP 完全的部分，写到 -
为子集总和开发的算法的运行时间为 O(nW)。如果给出 100 个数字的实例，每个数字都是 100 位长，那么输入只有 100 * 100 = 10000 位，但 W 大约是 2^100。
我不明白这个说法，为什么是 W 2^100 ？base 对这个问题有什么影响，我的意思是，如果我们将其更改为其他 base x，W 会是 x^100 吗？如果我们将其更改为一元基数怎么办？
谢谢。

我真的很困惑为什么 2-CNF SAT 在 P 中，而 3-CNF SAT 在 NPC 中。我读过 CLRS，我了解他们如何证明 3-CNF SAT 在 NPC 中。我不能使用从 SAT 到 2-CNF-SAT 的相同可还原性来证明 2-CNF-SAT 在 NPC 中。我不明白为什么 2-CNF SAT 在 P 中。

SAT 是 NP-complete 的证明是一个建设性的证明，因此应该可以将其作为程序来实现。有人做过吗？

我正在寻找一个程序（编译器），它将程序（返回真或假）作为输入并输出 SAT 公式。

因此，例如，编译器可以将以下程序（以 pythonic 语法显示，但任何语言都可以）作为输入，并输出 SAT 公式。将 SAT 公式提供给 SAT 求解器将给出参数“证书”的解。在这种情况下，解将是 [False, True, True, True, False]，表示 {-3, -2, 5} 是一个解。

显然，输出的 SAT 公式会有其他辅助变量，因此编译器必须指出哪些变量对应于证书。

这样的编译器是否已经存在？它们中的任何一个都是开源的吗？

我有一个有向无环图，需要找到具有资源约束的最短路径。我的限制是所选路径必须具有最少数量的一组资源消耗。

目前我正在使用Yen 的 K 最短路径算法来计算 K 最短路径，然后只接受那些满足我的约束的路径。这里的问题在于猜测K，如果它被错误地选择了，可能会找不到可行的路径。

我发现了很多关于这个主题的文献，我认为这提供了一个很好的概述。但是，我正在努力理解它并找到一个能够实现的简洁算法（我正在使用 Python，但是任何清晰的算法想法都会很棒）。

我知道这个问题是 NP-Complete 的，因此我对任何好的近似算法以及精确方法都很感兴趣。

有人有什么好的建议吗？

如果我想证明一个问题是 np-hard 问题，可以多次使用现有的 np-hard 问题吗？例如在图中使用哈密顿循环 n 次，其中 n 是顶点数？或者我是否需要将图形转换为可以通过使用 1 次的现有 np-hard 问题轻松解决的东西？

我有一个随机的无向社交图。

如果可能的话，我想找到一条哈密顿路径。或者如果不可能（或者不可能在多项式时间内知道是否可能）一系列路径。在这个“路径系列”（所有 N 个节点只使用一次）中，我想最小化路径的数量并最大化路径的平均长度。（因此单个节点的 N 条路径没有平凡的解决方案）。

我已经为节点和边生成了一个邻接矩阵。

有什么建议么？指向正确方向的指针？我意识到这将需要启发式方法，因为问题的 NP 完全（？）性质，我可以接受“足够好”的答案。我也想在Java中做到这一点。

谢谢！

Wiki 说，当您将 poly time 中的 np 完成问题转换为 A 时， A 是 np 困难的。见http://en.wikipedia.org/wiki/NP-hard

但是下面的 pdf 说，当您在多项式时间内将 np 难题转换为问题 A 时，A 是 np - hard http://compgeom.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/21-nphard。 pdf

我应该相信哪一个？

我正在研究编译器/证明检查器，我想知道是否有这样的语法树，例如：

如果有办法检查Exprs 的 alpha 等价（等价模重命名）。然而，这Expr与 lambda 演算的不同之处在于 lambda 中的变量集是可交换的——即参数的顺序不会影响检查。

（但是，为了简单起见，Lambda ["x","y"] ...它与 不同Lambda ["x"] (Lambda ["y"] ...)，在这种情况下，顺序确实很重要）。

换句话说，给定两个Exprs，如何有效地找到从一个重命名到另一个的重命名？这种组合问题有 NP 完全问题的味道。

我需要帮助构建以下问题的算法。

我有一组点G可以“看到”其他点C。需要一种算法来从G中找到覆盖所有C的最小集合（G不一定是C的一部分）。

我有一种感觉，这应该通过动态编程来解决。但我对任何可以帮助我的解决方案/想法持开放态度。

谢谢！

编辑1：

我可能没有完全理解这个问题。

这些点位于具有地形高度的 3d 表面上。地形可能会在点之间上升到一定高度，使得一个点看不到另一个点。只要有直接的视线，无论距离多远，这些点都可以互相看到。

• 如果点a（从G）可以看到点b（从C）-并且点b可以看到d（从C），那么a可以看到d。不确定这是否有所作为。

• 如果只有a（来自G）可以看到b（来自C），我们必须选择a以覆盖所有C - 所以在使用贪心算法之前最好这样做。

根据新信息，仍在考虑是否还有其他差异。

考虑以下问题：

有 N 个硬币，编号为 1 到 N。

你看不到它们，但会得到关于它们的 M 事实，形式如下：

positions标识硬币的一个子集，并且num_heads是该子集中硬币正面的数量。

鉴于这些 M 事实，您需要计算出可能存在的最大正面数量。

这个问题是NP完全的吗？如果是，减少量是多少？如果不是，什么是多项式时间解？

例如：

与事实相匹配的头部最多的配置是：

所以答案是3个头。