固定子集大小的求和子集
子集和问题指的是： 给定一组整数，是否存在一个非空子集其总和为零？ 通常情况下，这个问题是NP完全问题。不过我很好奇这个稍微变换一下的问题的复杂度是否已知： 给定一组整数，是否有一个大小为k的子集其总和为零？ 例如，如果k=1，你可以进行二分查找并在O(log n)...
为什么 P ⊆ co-NP？
我看到过一些地方简单地陈述了P是NP和co-NP的交集的子集这一事实。显示P是NP的子集的证明并不难找到。因此，为了展示它是交集的子集，唯一剩下要做的就是展示P是co-NP的子集。那么，这种证明可能是什么样子的呢？非常感谢！
有可判定的决策问题，但不属于NP吗？
这是我的第一个stackoverflow问题，请温柔点。如果这个问题已经被讨论过了，我提前道歉...我看了一些NP的帖子，但没有找到一个令人心动的答案（如果有什么的话，我想到了一些新问题）。简而言之： 是否存在可判定但不在NP中的决策问题？ 如果是，那么要求解的问题是否比等效的决策问题更难...
旅行商问题中NP-hard和NP-Complete的混淆
旅行推销员优化问题（TSP-OPT）是一个NP难问题，而旅行推销员问题（TSP）则是NP完全问题。然而，由于如果能在多项式时间内解决TSP问题，那么也能解决TSP-OPT问题，因此TSP-OPT可以被约化为TSP(1)。我原以为在A可以被约化为B的情况下，B必须和甚至比A更难。但是从下面的参考...
这个问题是否可以在多项式时间（或伪多项式时间）内解决？
我正在尝试设计一个合理的算法来解决这个问题： 假设您有一堆球。每个球至少有一种颜色，但也可以是多彩的。每个球都有一个重量和一个与之关联的价值。还有一堆盒子，它们各自只有一种颜色。每个盒子都有一个最大的装载球数。目标是在保持总重量不超过W的情况下最大化盒子中的总价值，唯一的规则是： 为了将一...
生成方程式以获得最接近所需结果的值，存在速度问题。
我正在编写一些测验游戏，并需要电脑在玩家无法解决问题时解决1个问题。 已知数据： 可供使用的6个数字列表，例如4、8、6、2、15、50。 目标值，在0＜value＜1000的范围内，例如590。 可以使用的运算符为除法、加法、乘法和减法。 可以使用括号。 生成数学表达式，使其结果等...
NP-Complete与NP-Hard的区别
我正在尝试理解NP-Complete和NP-Hard之间的区别。 以下是我的理解 NP-Hard问题是指不能在多项式时间内求解，但可以在多项式时间内验证的问题。 NP-Complete问题是指属于NP且也是NP-Hard问题。 上述定义是否正确？如果是这样，那么不在NP中但N...
创建学校课程表的算法
我一直在想是否有已知的算法来创建学校课程表。基本上，它是关于优化给定班级-科目-教师关联下的“时间分散”（教师和班级均适用）。我们可以假设在输入时，我们有班级、课程主题和与之相关联的教师集合，并且课程表应该在早上8点到下午4点之间。 我猜可能没有精确的算法，但也许有人知道一个良好的近似值或开...
我需要解决一个NP-hard问题。有希望吗？
有很多现实世界的问题被证明是NP -hard的。如果我们假设P ≠ NP，那么这些问题就没有多项式时间算法。 如果你必须解决其中一个问题，是否有希望能够有效地解决？还是你只是运气不佳？
一些排序算法可以是P，NP或NP-Complete吗？
经过一些阅读，我感到很困惑： P在NP中，而NP在NP-Complete中。那么所有的P都可能在NP和NP-Complete中吗？ 这是否意味着有可能存在既是NP又是NP-Complete的排序算法？ 希望这不会听起来太蠢。