Np-硬度降低
如果我想证明一个问题是 np-hard 问题，可以多次使用现有的 np-hard 问题吗？例如，在图中使用哈密顿循环 n 次，其中 n 是顶点数？或者我是否需要将图转换为可以通过使用 1 次的现有 np-hard 问题轻松解决的东西？
If I want to show that a problem is np-hard is it ok to use a existing np-hard problem multiple times? For example use Hamiltonian Cycle n times in a graph where n is the number of vertices? Or do I need to transform the graph into something that can easily be solved by an existing np-hard problem used 1 time?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
你需要表现出完全相反的情况。
如果你证明你可以用 NP-Hard 问题解决你的问题，那并不能证明任何事情。 [你可以使用 SAT 解决 NP 中的每一个问题，通过 Cook-Levin 定理]。
您需要证明，如果您的问题可以在多项式时间内解决，那么 NP 困难问题也是如此。这就是减少的实际作用。
例如：如果我可以证明我可以使用 TSP - 它是否使最短路径成为NP-Hard？当然不是！它仅表明 TSP 至少与最短路径一样难！
You need to show the exact oposite.
It doesn't prove anything if you prove you can solve your problem with an NP-Hard problem. [You can solve every problem in NP using SAT, by Cook-Levin Theorem].
You need to show that if your problem is solvable in polynomial time - so is an NP-Hard problem. That what a reduction actually does.
For example: If I can show I can solve shortest path, using TSP - does it make shortest path NP-Hard? Of course not! It only shows TSP is at least as hard as shortest path!
从巴黎经纽约到伦敦并不能证明那条路是最短的。
traveling from paris to london via new york doesn't prove that that path is the shortest one.
我不是数学家，但如果你能证明所讨论的问题至少与现有的已知 NP 难题一样复杂或其倍数，那么这应该是足够的证明吗？
常识表明，如果剥一只豹子的皮比剥两只猫的皮更复杂，那么它就比剥一只猫的皮更复杂，依此类推！
I'm not a mathematician, but surely if you can prove that the problem in question is at least as complex as an existing known-to-be-NP-hard problem, or multiples thereof, than that should be sufficient proof?
Common sense would suggest that if skinning a leopard is more complex than skinning 2 cats, then its more complex than skinning one cat, and so on!