回答情况：
提问时间：
问题标签：
2回答
我有NP难题。假设我找到了一些多项式算法，它只找到该问题许多现有解决方案中的一个，但至少有一个解决方案(如果在问题中存在)。该算法是否被认为是NP=P问题的解决方案(如果该算法转化为数学证明)？
浏览 3提问于2010-10-12得票数 1
回答已采纳
据我所知，所有的NP-完全问题都是NP-难的，但有些NP-hard问题不是NP-完全的，并且NP-hard问题至少和NP-完全问题一样难。
这是不是意味着不是NP完全的NP-hard问题更难？
浏览 3提问于2010-09-28得票数 30
我写了一个启发式算法为装箱问题使用最佳拟合方法，itens S=(i1，...，in)，箱大小T，并希望创建一个真正的精确指数算法，它计算最优解(最小数量的箱来包装所有的iten)，但我不知道如何检查每种可能的包装，我在C中做。对不起，我的英语不好
浏览 1修改于2013-04-03得票数 0
回答已采纳
我有一个NP-hard优化问题，我将其形式化为混合整数线性规划(MILP)，并且正在使用解决(对于小输入)。
我理解NP-hard意味着没有多项式时间算法来解决这个问题，除非是P=NP。
浏览 6提问于2020-11-30得票数 0
我对NP-hard问题感到困惑。例如:停机问题只是NP难的，不是NP完全的。
但是为什么它不是NP完全的呢？
浏览 3修改于2011-04-14得票数 5
我对不可判定问题和NP困难问题之间的关系感到有点困惑。NP难题是否是不可判定问题的子集，或者它们是相同和相等的，还是它们不具有可比性？一些讨论会有很大的帮助！谢谢!
浏览 8修改于2012-05-08得票数 16
回答已采纳
由于任何NP困难问题都可以通过映射简化为任何其他NP困难问题，因此我的问题是前进一步；例如，算法的每一步:这也可以映射到其他NP困难问题吗？
浏览 1提问于2013-05-06得票数 1
我知道以前也有人问过类似的问题，网上有大量的资源，但我有一个略有不同的问题。我理解从HAM路径到最长路径的缩减。它依赖于两者都需要使用n-1个边。但是，如果在最长路径中给定的图的边权重为负值，会发生什么呢？那么最长的路径可以有n-2条边，但HAM仍然有n-1条边。
浏览 13修改于2018-12-05得票数 1
我的问题是:找到从节点A到节点B的最短路径，该路径通过未加权有向图的所有其他节点。我知道有这样一条路。它看起来和很相似，但是Graph的属性是不同的，有区别吗？
浏览 13修改于2017-06-12得票数 2
回答已采纳
3回答
如果我想证明一个问题是np-hard的，那么可以多次使用现有的np-hard问题吗？例如，在一个图中使用哈密顿圈n次，其中n是顶点的数量？或者我需要将图转换成可以通过使用一次的现有np-hard问题轻松解决的东西？
浏览 0提问于2012-01-09得票数 0
回答已采纳
有一个大小为arr的数组n。那么，有多少2^n子集的总乘积大于一个数字，比如说X？我认为类似于子集和的东西会起作用，但我现在并不这么认为。
浏览 1修改于2017-05-15得票数 2
我试着用一种直观的方式把我听到的P，NP，NP-Complete和NP-Hard包装在一起，这样我就不必记住它们的定义了。
浏览 2修改于2017-05-23得票数 1
对于连通的无向图，G = (V, E)查找包含所需顶点集D的minimum dominating set是否为NP-hard
浏览 1修改于2013-05-13得票数 0
我们在P，NP，co，NP-完全类和NP-Hard类中证明了一些问题.这些问题也有其时间复杂性的推论。我想知道我是否遗漏了关于这个主题的任何关键信息。
浏览 4提问于2022-02-07得票数 -1
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号