3

我想嵌入 3 个 NP-Complete 问题（其中 2 个已知是 NP-Complete，其中 1 个是我自己的想法）。我看到了“这个问题”，并在理论上重新解释了嵌入问题：

  • 服务员就是小偷。
  • 桌子是商店。
  • 食物是具有不同重量的有价值的物品。
  • 小偷在抢劫之前知道所有物品的价格和重量。
  • 他的目标是最有效的抢劫（使用的背包的最大容量，获得最有价值的物品）抢劫（至少获得 1 件物品）所有商店（完成抢劫之旅的最短路径，也访问每个商店 1 次）。

这部分是嵌入 2 个 NP-Complete 问题。

我的想法是，更多的物品意味着更多的袋子重量。更大的袋子重量会成倍地减慢小偷的速度。所以小偷的另一个目标应该是尽快完成抢劫。

此时，我不确定我的想法是否真的是 NP-Complete。也许，“重力”不仅仅是一个 NP 完全问题。但也许是在旅行推销员和背包问题的背景下。

所以我的问题是：

  1. 小偷NP的减速也完全吗？

  2. 是否有可能将这三个嵌入式问题简化为一个简单的 NP 完全问题？

4

5 回答 5

2

好的，这有点难以理解，但我想我明白了要点。

XKCD 动画片向您展示了使现实生活中的问题成为 NP 完全问题是多么容易。（当然，由于大多数菜单的项目数量较少且价格统一，因此也很容易表明存在一个微不足道的答案。）

我认为您所指的“嵌入”一个NP完全问题的想法是找到一个多时间减少；我已经在SO的其他地方完全写了。

于 2009-02-12T16:20:11.103 回答
1

这有点令人困惑，但这是我对一些可能问题的回答。

两个 NP 完全问题的组合将是 NP 完全的。事实上，一个 NP 完全问题与任何其他问题的组合将是 NP 完全的。

我不知道如何评估重力问题本身是否是 NP 完全的，因为它本身不是。如果点之间的时间取决于距离和背包重量，那么它是 NP 完全的，因为它是旅行推销员问题的一部分。如果没有，那么正确的解决方案是拾取从最轻到最重的物体。

组合问题是两个问题的组合（偷哪些物品，走哪条路线），对我来说，这两个问题看起来并不比这两个问题更有趣，因为你可以解决一个问题而不必担心另一个问题。添加与权重相关的延迟可以将问题耦合在一起，因此它们不是独立的，但是您需要一个评估函数，而不是您可以多快提交最佳盗窃（最佳盗窃是它自己的问题，然后它只是一个修改后的 TSP）。

你也不能解决问题，把它们结合起来，把它们复杂化，然后再做一个更简单的问题。

于 2009-02-12T17:06:32.647 回答
0

老实说，我不知道你在问什么。但您可能会问如何通过将一个问题 NP 完全转换为另一个 NP 完全问题来证明它。

答案是您编写一个在多项式时间内运行的算法，将问题转换为已知的 NP 完全问题，然后编写另一个多项式算法将解决方案转换回来。

有关详细信息，请阅读一本不错的教科书或查看Wikipedia 页面。

于 2009-02-12T16:18:02.670 回答
0

感谢有用的评论，卡通给了我一个关于嵌入问题的想法。我写的时候有点着急，所以写错了很多。我的主要语言也不是英语，所以编辑让我的问题更容易理解。我还想要更多的集思广益的评论。

查理马丁，感谢您的链接。

于 2009-02-12T16:29:38.773 回答
0

携带额外重量的成本本身不是问题，而是旅行商问题的边缘权重的参数化。

这个问题的决策版本仍然是 NP 完全的，因为 a）我们仍然可以快速检查给定的游览成本是否小于 k，因此它在 NP 中，并且 b）哈密顿循环仍然减少到我们的 TSP 与携带成本（因为我们只是将所有边权重设置为 1，并将所有携带成本设置为 0）。

换句话说，持有成本只是让我们的 TSP 变得更难，所以它仍然是 NP 难的（并且可以用来解决任何 NP 完全问题），但它并没有让我们无法快速检查提出的解决方案变得足够困难到决策问题：“这次旅行的成本是否低于 c？”，所以它仍然是 NP 完全的。

背包问题的（NP-complete）决策版本是独立的，可以用 TSP 问题顺序求解。

所以整个问题是 NP 完全的，如果我们将 TSP 问题和背包问题归约为 SAT（通常不会在这个方向上进行归约，但理论上是可能的），那么我们可以将两者一起编码为一个 SAT 实例.

于 2009-02-12T18:27:15.090 回答