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