如果我想证明一个问题是 np-hard 问题，可以多次使用现有的 np-hard 问题吗？例如在图中使用哈密顿循环 n 次，其中 n 是顶点数？或者我是否需要将图形转换为可以通过使用 1 次的现有 np-hard 问题轻松解决的东西？
问问题
333 次
3 回答
4
您需要显示确切的对立面。
如果你证明你可以用 NP-Hard 问题解决你的问题，那并不能证明任何事情。[您可以使用 SAT 解决 NP 中的所有问题，由Cook-Levin Theorem提出]。
您需要证明您的问题是否可以在多项式时间内解决 - NP-Hard 问题也是如此。这就是减少的实际作用。
例如：如果我可以证明我可以使用TSP解决最短路径- 它是否使最短路径 NP-Hard？当然不是！它仅表明 TSP 至少与最短路径一样难！
于 2012-01-09T13:40:31.693 回答
1
从巴黎经纽约到伦敦并不能证明这条路是最短的。
于 2012-01-09T14:10:41.397 回答
0
我不是数学家，但如果你能证明所讨论的问题至少与现有的已知 NP 难题或其倍数一样复杂，那么这应该是充分的证据吗？常识表明，如果给豹子剥皮比给两只猫剥皮更复杂，那么它比给一只猫剥皮更复杂，以此类推！
于 2012-01-09T13:36:48.660 回答