我有几个数字数组(每个数组的元素只能取0或1),如下: v1: 1; 0; 0; 1; 1; v2: 0; 1; 0; 0; 1; v3: 1; 1; 0; 1; 0; v4: 1; 0; 0; 1; 0; v5: 1; 1; 0; 1; 1; v6: 1; 1; 0; 1; 1...
有些NP难问题也是固定参数可解的,即FPT。维基百科将一个问题描述为固定参数可解的,如果存在一种算法可以在时间f(k) · |x|O(1)内解决它。 这是什么意思?这个概念有什么用处?
有许多优化问题已知是NP难的,例如旅行商问题,MAX-SAT问题或者寻找图的最小色数。针对这种问题,我对以下问题的复杂性很感兴趣: 给定一个NP难的优化问题和一个候选解S,S是否是该问题的最优解? 直觉上,这个问题可能是co-NP难的,因为可以通过猜测更好的解并将其作为证人来轻易地...
我看到过一些地方简单地陈述了P是NP和co-NP的交集的子集这一事实。显示P是NP的子集的证明并不难找到。因此,为了展示它是交集的子集,唯一剩下要做的就是展示P是co-NP的子集。那么,这种证明可能是什么样子的呢?非常感谢!
这是我的第一个stackoverflow问题,请温柔点。如果这个问题已经被讨论过了,我提前道歉...我看了一些NP的帖子,但没有找到一个令人心动的答案(如果有什么的话,我想到了一些新问题)。简而言之: 是否存在可判定但不在NP中的决策问题? 如果是,那么要求解的问题是否比等效的决策问题更难...
我正在尝试设计一个合理的算法来解决这个问题: 假设您有一堆球。每个球至少有一种颜色,但也可以是多彩的。每个球都有一个重量和一个与之关联的价值。还有一堆盒子,它们各自只有一种颜色。每个盒子都有一个最大的装载球数。目标是在保持总重量不超过W的情况下最大化盒子中的总价值,唯一的规则是: 为了将一...
我知道到目前为止还没有解决P=NP问题,但是有人能告诉我一些关于以下内容的信息吗?目前最有前途的数学/计算机科学方法是什么,可以帮助解决这个问题吗?或者现在甚至没有这样的方法被认为是潜在有用的吗?是否有任何(免费的)汇编关于这个主题,在那里我可以找到所有/大部分研究在这个领域完成?
我正在尝试理解NP-Complete和NP-Hard之间的区别。 以下是我的理解 NP-Hard问题是指不能在多项式时间内求解,但可以在多项式时间内验证的问题。 NP-Complete问题是指属于NP且也是NP-Hard问题。 上述定义是否正确?如果是这样,那么不在NP中但N...
我很难理解什么是非确定性多项式时间问题和NP完全问题。我了解什么是多项式时间可解问题,并在维基百科上看到了关于NP问题的介绍。阅读后,我尝试考虑一些示例问题。据我所知,对于无向图中的深度优先搜索而言,由于每个决策都可以被非确定地做出(即如果我做错了一个决定,我可以尝试一些其他选择),因此它是N...
我在期中考试中遇到了一个问题。有人能解释一下答案吗? 问题A:给定一个完全加权图G,找到一条带有最小权重的哈密顿回路。 问题B:给定一个完全加权图G和实数R,G是否有一条带有最大权重为R的哈密顿回路? 假设有一台机器可以解决问题B。如果每次给出G和实数R来解决问题A,我们最多可以调用多少...