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