theory - NP-完全归约(理论上)

Question

我想嵌入 3 个 NP-Complete 问题(其中 2 个已知是 NP-Complete，其中 1 个是我自己的想法)。我看到了“this question”并得到了关于从理论上重新解释嵌入问题的想法:

• 服务员是小偷。
• 表已存储。
• 食物是具有不同重量的贵重元素。
• 小偷在盗窃前就知道所有元素的价格和重量。
• 他的目标是最有效的抢劫(使用最大容量的背包，获得最有值(value)的元素)抢劫(至少获得 1 件元素)所有商店(完成抢劫之旅的最短路径，也访问每个商店 1 次)。<

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

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

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

所以我的问题是:

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

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

Answer 1

好吧，这只是一点难以理解，但我想我明白了要点。

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

我认为您指的是“嵌入”一个 NP 完全问题的想法是找到多时间减少；我有 written that up pretty completely SO 的其他地方。