NP-完全还原（理论上）
我想嵌入3个NP完全问题（其中2个已知是NP完全问题，其中1个是我自己的想法）。 我看到“这个问题”并了解了如何重新解释嵌入问题理论：
- 服务员就是小偷。
- 桌子是商店。
- 食物是具有不同重量的贵重物品。
- 小偷在抢劫前就知道所有物品的价格和重量。
- 他的目标是最有效的抢劫（使用背包的最大容量，得到最有价值的物品），抢劫（得到至少 1 件物品）所有商店（完成抢劫之旅的最短路线，也访问每个商店 1 次）。
这部分嵌入了 2 个 NP 完全问题。
我的想法是，更多的物品意味着更多的行李重量。 袋子重量越大，窃贼的速度就会成倍下降。 因此，小偷的另一个目标应该是尽快完成抢劫。
此时，我不确定我的想法是否真的是NP完全的。 也许，“引力”不仅仅是一个NP完全问题。 但也许是在旅行推销员和背包问题的背景下。
所以我的问题是：
小偷的减速也是NP完全的吗？
是否可以将这三个嵌入式问题简化为一个简单的 NP 完全问题？
I want to embed 3 NP-Complete problems(2 of them are known to be NP-Complete, 1 of them is my own idea). I saw "this question" and got idea about reinterpreting embedding problems in theory:
- The Waiter is The Thief.
- Tables are store.
- Foods are valued items which has different weight.
- Thief know all the items' price and weight before the robbery.
- His target is most efficient robbery(max capacity of knapsack used, most valued items got) with robbing(getting at least 1 item) all stores(shortest way to completing robbery tour, also visit each store 1 time).
This part is embedding 2 NP-Complete problems.
My idea is, that more items mean more bag weight. More bag weight slow downs the thief exponentially. So another target of the thief should be finishing the robbery as quickly as he/she can.
At this time, I'm not sure that my idea is actually NP-Complete. Maybe, "gravity" is not a NP-Complete Problem alone. But maybe it is in this context of the travelling salesman and knapsack problem.
So my questions are:
Is the slowing down of the thief NP-complete, too?
Is it possible to reduce those three embedded problems to a simple NP-complete problem?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
携带额外重量的成本本身并不是一个问题，而是旅行商问题的边权重的参数化。
这个问题的决策版本仍然是 NP 完全的，因为 a）我们仍然可以快速检查给定旅行的成本是否小于 k，因此它是 NP 的，并且 b）哈密顿循环仍然减少到我们的 TSP 与承载成本（因为我们只是在减少过程中将所有边权重设置为 1，并将所有承载成本设置为 0）。
换句话说，持有成本只是让我们的 TSP 变得更难，所以它仍然是 NP 困难的（并且可以用来解决任何 NP 完全问题），但它并没有使它变得足够困难，以至于我们无法快速检查建议的解决方案对于决策问题：“这次旅行的成本是否低于 c？”，所以它仍然是 NP 完全的。
背包问题的（NP 完全）决策版本是独立的，并且可以与 TSP 问题顺序求解。
所以整个问题是NP完全的，如果我们减少TSP问题和Knapsack问题
SAT 的问题（通常不会在这个方向上进行归约，但理论上是可能的），然后我们可以将两者一起编码为一个 SAT 实例。
The cost of carrying extra weight is not a problem by itself, but rather a parameterization of the edge-weights of your Traveling Salesman Problem.
The decision version of this problem is still NP-complete, because a) we can still check quickly if a given tour has cost less than k so it is in NP, and b) Hamiltonian Cycle still reduces to our TSP with carrying costs (since we just set all edge weights to 1 and all carrying costs to 0 in the reduction).
In other words, the carrying costs just made our TSP harder, so it is still NP-hard (and can be used to solve any NP-complete problem), but it did not make it hard enough that we cannot quickly check a proposed solution to the decision problem: "Does this tour cost less than c?", so it is still NP-complete.
The (NP-complete) decision version of the Knapsack problem is independent, and can be solved sequentially with the TSP problem.
So the entire problem is NP-complete, and if we reduce the TSP problem and the Knapsack
problems to SAT (reduction normally isn't done in this direction but it is theoretically possible), then we can encode the two together as one SAT instance.
好吧，这有点难以理解，但我想我已经明白了要点。
XKCD 漫画向您展示了将现实生活中的问题变成 NP 完全问题是多么容易。 （当然，由于大多数菜单都有少量的项目和统一的价格，因此也很容易表明存在一个微不足道的答案。）
我认为您指的是“嵌入”NP完全问题的想法to 是寻找聚合时间减少； 我已经在其他地方写得很完整。
Okay, that was just a bit tough to follow, but I think I'm getting the gist.
The XKCD cartoon is showing you how easy it is to make a real-life problem NP-complete. (Of course, since most menus have a small number of items and a uniform set of prices, it's also easy to show that there is a trivial answer.)
The idea of "embedding" an NP-complete problem I think you're referring to is finding a poly-time reduction; I've written that up pretty completely elsewhere on SO.
这有点令人困惑，但以下是我对一些可能问题的回答。
两个 NP 完全问题的组合将是 NP 完全问题。 事实上，NP 完全问题与任何其他问题的组合都将是 NP 完全问题。
我不知道如何评估重力问题本身是否是 NP 完全的，因为它本身不是。 如果点之间的时间取决于距离和背包重量，那么它是 NP 完全的，因为它是旅行商问题的一部分。 如果没有，那么正确的解决方案是拾取从最轻到最重的物体。
组合问题是两个问题的组合（哪些对象要窃取，以及采取哪条路线），对我来说，它看起来并不比单独的两个问题更有趣，因为您可以解决一个问题而不用担心另一个问题。 添加与重量相关的延迟可以将问题耦合起来，因此它们不是独立的，但是您需要一个评估函数，而不是可以以多快的速度实施最佳盗窃（最佳盗窃是它自己的问题，然后它只是修改后的 TSP）。
你也不可能解决问题，将它们耦合起来，使它们复杂化，然后再提出一个更简单的问题。
This is a bit confusing, but here are my answers to some possible questions.
The combination of two NP-complete problems is going to be NP-complete. In fact, the combination of an NP-complete problem with any other problem is going to be NP-complete.
I don't see how to evaluate whether the gravity problem is NP-complete on its own, because it isn't on its own. If the time between points depends on distance as well as backpack weight, then it's NP-complete because it's part of the Traveling Salesman problem. If it doesn't, then the right solution is to pick up objects lightest to heaviest.
The combined problem is a combination of two problems (which objects to steal, and which route to take), and doesn't look any more interesting to me than the two separately, since you can solve one without worrying about the other. Adding weight-dependent delays can couple the problems so they aren't independent, but you need an evaluation function other than how fast you can commit the optimum theft (the optimum theft is its own problem, and then it's just a modified TSP).
Nor are you going to be able to take problems, couple them, complicate them, and then make a simpler problem in general.
老实说，我不知道你在问什么。 但你可能会问如何通过将一个问题转换为另一个 NP 完全问题来证明它是 NP 完全的。
答案是，您编写一个在多项式时间内运行的算法，将问题转换为已知的 NP 完全问题，然后编写另一个多项式算法将解决方案转换回来。
有关更多详细信息，请阅读一本不错的教科书或参阅维基百科页面。
I honestly have no idea what you are asking. But it might be you are asking how you prove one problem NP-complete by converting it to another NP-complete problem.
The answer to this is that you write an algorithm which runs in polynomial time to convert the problem to a known NP-complete problem, then another polynomial algorithm to convert the solution back.
For more details read a decent textbook or see the Wikipedia page.
感谢您提供有用的评论，Cartoon 给了我关于嵌入问题的想法。 我写的时候有点急，所以写错了很多。 我的主要语言也不是英语，所以编辑让我的问题更容易理解。 我还想发表更多意见，以进行更多的头脑风暴。
Thanks for helpful comments, Cartoon gave me an idea about embedding problems. I was bit hurry when I was writing, so I did many writing mistakes. My main language is not English too, so editors made my question more understandable. I also want another comments to more brainstorming.