NP、NP-Complete和NP-Hard之间有什么区别？
NP、NP-Complete和NP-Hard有什么不同之处？ 我知道网上有很多资源。我想读一下你的解释，因为它们可能与其他地方的不同，或者有一些我不知道的东西。
生成方程式以获得最接近所需结果的值，存在速度问题。
我正在编写一些测验游戏，并需要电脑在玩家无法解决问题时解决1个问题。 已知数据： 可供使用的6个数字列表，例如4、8、6、2、15、50。 目标值，在0＜value＜1000的范围内，例如590。 可以使用的运算符为除法、加法、乘法和减法。 可以使用括号。 生成数学表达式，使其结果等...
NP难优化问题的解决方案验证的复杂性？
有许多优化问题已知是NP难的，例如旅行商问题，MAX-SAT问题或者寻找图的最小色数。针对这种问题，我对以下问题的复杂性很感兴趣： 给定一个NP难的优化问题和一个候选解S，S是否是该问题的最优解？ 直觉上，这个问题可能是co-NP难的，因为可以通过猜测更好的解并将其作为证人来轻易地...
旅行商问题中NP-hard和NP-Complete的混淆
旅行推销员优化问题（TSP-OPT）是一个NP难问题，而旅行推销员问题（TSP）则是NP完全问题。然而，由于如果能在多项式时间内解决TSP问题，那么也能解决TSP-OPT问题，因此TSP-OPT可以被约化为TSP(1)。我原以为在A可以被约化为B的情况下，B必须和甚至比A更难。但是从下面的参考...
为什么分解质因数属于NP问题，而不属于P问题？
因式分解：给定整数N，找到两个小于N的正整数a和b（1 < a, b < N），使得它们的乘积等于N。如果这样的a和b不存在，那么N是一个质数。 我知道判断质数可以用P算法，但为什么不能用这种方法做因式分解呢？ 这是我的算法：For each a = 1 ... sqrt(N) ...
寻找满足特定条件的子集
我有几个数字数组（每个数组的元素只能取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...
完全带权图和哈密顿回路
我在期中考试中遇到了一个问题。有人能解释一下答案吗？ 问题A：给定一个完全加权图G，找到一条带有最小权重的哈密顿回路。 问题B：给定一个完全加权图G和实数R，G是否有一条带有最大权重为R的哈密顿回路？ 假设有一台机器可以解决问题B。如果每次给出G和实数R来解决问题A，我们最多可以调用多少...
P=NP：最有前途的方法是什么？
我知道到目前为止还没有解决P=NP问题，但是有人能告诉我一些关于以下内容的信息吗？目前最有前途的数学/计算机科学方法是什么，可以帮助解决这个问题吗？或者现在甚至没有这样的方法被认为是潜在有用的吗？是否有任何（免费的）汇编关于这个主题，在那里我可以找到所有/大部分研究在这个领域完成？
NP和NP-complete问题是什么？
我很难理解什么是非确定性多项式时间问题和NP完全问题。我了解什么是多项式时间可解问题，并在维基百科上看到了关于NP问题的介绍。阅读后，我尝试考虑一些示例问题。据我所知，对于无向图中的深度优先搜索而言，由于每个决策都可以被非确定地做出（即如果我做错了一个决定，我可以尝试一些其他选择），因此它是N...
最大独立集算法
我不相信存在一种算法，可以在二分图中找到最大独立顶点集，除了通过暴力方法找到所有可能的独立集合中的最大值。 我想知道如何编写伪代码来查找所有可能的顶点集。 假设有一个具有4个蓝色顶点和4个红色顶点的二分图。目前，我会使用以下方法： Start with an arbitrary blue...