Np-硬度降维
Np-硬度降维
提问于 2012-01-09 21:30:11
如果我想证明一个问题是np-hard的，那么可以多次使用现有的np-hard问题吗？例如，在一个图中使用哈密顿圈n次，其中n是顶点的数量？或者我需要将图转换成可以通过使用一次的现有np-hard问题轻松解决的东西？
回答 3
Stack Overflow用户
回答已采纳
发布于 2012-01-09 21:40:32
你需要展示确切的对立面。
如果你证明你可以用NP-Hard问题来解决你的问题，这并不能证明任何事情。[您可以通过Cook-Levin Theorem使用SAT解决NP中的所有问题]。
你需要证明，如果你的问题在多项式时间内是可解的，那么NP-Hard问题也是如此。这就是缩减的实际作用。
例如:如果我能证明我可以用TSP解决shortest path问题--这会使最短路径变得NP困难吗？当然不是!它只表明TSP至少和最短路径一样难！
Stack Overflow用户
发布于 2012-01-09 22:10:41
从巴黎经纽约到伦敦并不能证明那条路是最短的。
Stack Overflow用户
发布于 2012-01-09 21:36:49
我不是一个数学家，但是如果你能证明这个问题至少和一个已知的NP难问题一样复杂，或者是它的倍数，那么这就应该是足够的证据了？常识表明，如果给一只豹剥皮比给两只猫剥皮更复杂，那么它就比给一只猫剥皮更复杂，以此类推！
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/8789166
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号