问题标签 [np-complete]

我有一个问题，它是子集和问题的一个非常明显的例子：

“给定 [-65000,65000] 范围内的整数列表，如果列表的任何子集求和为零，则函数返回 true。否则返回 false。”

我想问的是更多的解释而不是解决方案。

这是我在考虑问题的复杂性之前提出的一个特定于实例的解决方案。

• 对数组 A[] 进行排序，并在排序期间将每个元素与计数器 'extSum' (O(NLogN)) 相加
• 定义指针 low = A[0] 和 high = A[n-1]
• 这是决定代码：
• /li>

首先，这个解决方案是否正确？我做了一些测试，但我不确定......看起来太容易了......
这段代码的时间复杂度不是O（n ^ 2）吗？

我已经阅读了各种 DP 解决方案，我想了解的是，对于我面临的问题的具体实例，它们比这种天真的和直观的解决方案要好得多。我知道我的方法可以改进很多，但在时间复杂度方面没有什么大不了的......

谢谢你的澄清

编辑：一个明显的优化是，在排序时，如果找到 0，函数会立即返回 true ......但这仅适用于数组中有 0 的特定情况。

我有以下NP完全问题：

鉴于：

• N × N 场中的一组位置，
• 一组 m 个节点，和
• 节点的连接图（即无向图，其边表示每对相互接触的节点），以及
• 接触范围 R（与 N × N 字段的长度单位相同），

找到与连接图相关的字段中节点的放置（即放置节点，使任何接触的对比 R 更近，而任何不接触的对比 R 更远），或表明这种放置不存在。

这个问题可以简化为一个众所周知的NP完全问题吗？

（也可以考虑问题的优化版本，即找到最优化的放置）

我理解为什么有界度生成树被认为是具有一个或 2 度的 NP 完全（它是哈密顿路径问题的一个实例），但我不明白为什么这适用于度数 > 2。如果有人可以解释这是为什么度数 > 2 的 NP 完全问题，这将是最有帮助的

我们知道 3SAT ≤p 3COLOR（即 3SAT 是多项式时间可简化为 3COLOR）。谁能给出一个简短的论据，为什么 3COLOR ≤p 3SAT？并给出一个实际的库克减少表明 3COLOR ≤p 3SAT 请。

大家好，我有一个问题。我想知道是否有人知道如何证明它。

这是问题：子集和问题被证明是NP完全的。输入是一系列正数 w1, ... ,wn, W，其中 W 是目标权重。问题是判断是否存在一组权重 F ⊆ {1, ... ,n} 使得一些权重之和等于目标权重（即 w1 + ... + wi = W
） Restricted Subset Sum 问题可以像 Subset Sum 一样定义，但额外要求目标权重小于所有权重总和的一半。（如果失败，则必须立即拒绝输入。）证明 Restricted Subset Sum 是 NP-complete。
谢谢你。

问题：给定一组必修课和选修课，每门课程仅在特定时间段（有 7 个时间段）提供，生成所有可能的时间表。

例子：

对于必修课：

• MAT101 - 1、2、5
• HIS102 - 2、4、6
• ENG105 - 3、6、7

和选修课：

• LIT103 - 3、4、6
• CHE101 - 7、1、2
• 生物 101 - 5、4、7
• MAT201 - 6、5、1
• ANT201 - 1

（并非每门选修课都必须包含在时间表中）

可能的解决方案之一是：

1. MAT101 [必修]
2. HIS102 [强制性]
3. LIT103
4. 生物101
5. MAT201
6. ENG105 [必修]
7. 车101

用 PHP 编写它的最有效方法是什么？

我目前正在尝试开发一个蛮力解决方案，但这是一项非常乏味的任务，我正在寻找更有效的方法来做到这一点。我发现这是一个 NP 完全问题，并搜索了有助于解决此类问题的 PHP 类，但恐怕目前没有这样的类可用。

如果一个已知为 NP-Complete 的问题 A 可以在多项式时间内简化为另一个问题 B，则 B 是 (A) NP-Complete (B) NP-hard

无论问题 B 是否在 NP 中，都没有给出任何内容。我很困惑，因为在 Hopcraft 和 Ullman 书中给出了一个定理，如果一个 NP 完全问题 P1 可以在多项式时间内简化为问题 P2，那么 P2 是 NP 完全的。但它也要求一个问题是 NP 完全的，它应该属于 NP 类。伙计们帮助理解这个概念。

我认为哈密顿循环问题可以概括为：

给定一个无向图G = (V, E)，哈密顿回路是一次G遍历每个顶点的G一次且仅一次。

现在，我想做的就是减少我的问题。我的问题是：

给定一个加权无向图G、整数k和 中的顶点u, v ，G是否有一条G从u到的简单路径v ，总权重至少为k？

所以知道哈密顿循环问题是NP完全的，通过将这个问题简化为哈密顿，这个问题也被证明是NP完全的。我的问题是将其简化为哈密顿量的功能。

1. 最大的问题是哈密顿问题不处理边权重，所以我必须将我的图转换为没有任何权重的图。
2. 最重要的是，这个问题有一个指定的开始和结束（u 和 v），而哈密顿量找到一个循环，所以任何开始都与结束相同。

对于（1），我正在考虑通过一个图表，其中所有总权重小于 k 的简单路径都被取出。对于（2），我认为这不是一个真正的问题，因为如果存在哈密顿循环，那么从 u 到 v 的简单路径可以从中切出。

所以，我真正的问题是：

1. 我的解决方案会给我正确的答案吗？
2. 如果是，那么我怎样才能取出将产生总重量小于 k 的简单路径的边缘而不影响实际解决方案可能需要这些边缘之一的可能性？因为如果一条边 e 被取出是因为它为 E 的一个子集产生了一个权重 < k 的简单路径，它仍然可以用于具有不同边组合的简单路径以产生一个权重 >= k 的路径。

谢谢！

我们将 ROMAN-SUBSET 定义为以下问题：

输入：有向图 G = ( V , E ) 和一个正整数 k

输出：如果存在 V 的子集 R 使得 | 右 | <= k ，并且使得 G 中的每个有向电路都包含至少一个来自 R 的顶点，则输出应为“TRUE”，否则应为“FALSE”。

假设顶点覆盖 (VC) 问题是 NP 完全的，我必须证明 ROMAN-SUBSET 也是 NP 完全的。据我了解，这意味着获取 VC 输入，对其进行修改，然后显示将其插入 ROMAN-SUBSET 算法将产生 VC 问题的结果。

我很难进行转型。我知道VC的输入是一个图G和一个整数k，问题是是否存在一个覆盖G中每条边的V的子集R，使得|R| <= k。很明显，从 ROM 到 VC，R 和 k 是相似的，但我的困难是确定如何转换图形，以便每个有向循环（对于 ROM）中的 1 个顶点对应于每条边（对于 VC）。如何修改图表以证明 VC 可以简化为 ROM？

谢谢！

这很难，所以所有的帮助真的很感激！

我知道它是 NP-Complete，因此无法在多项式时间内解决，但在分析中寻求帮助，它减少到什么类型的 NP-Complete 问题，它提醒你的类似问题等等。

故事如下。我拥有一家拥有n辆卡车的冰淇淋卡车业务。我有m个站点进行交货。每个位置m _i都有p _i个人在等我。买了冰淇淋后，每个人都离开了。随着越来越多的人排队购买冰淇淋，pi 会随着时间的推移而增加_。

我如何才能确定接下来将卡车送到哪里以便在任何一天最大化我的利润？

要记住的事情：

• 两辆卡车在同一时间停在同一地点只会获得一次利润，即人们在一辆卡车到达后离开
• 卡车需要时间从一个地点到达另一个地点
• p _i在每个站点随时间增加，但某些站点的增长速度比其他站点快，即某些位置靠近商场（位置、位置、位置）

我尝试将其简化为多机调度问题、旅行销售人员问题、ILP 等，但主要问题是每个位置的p _i（即 TSP 中的距离或调度问题中的作业长度）是不断增加。

提前致谢！