标签: np

NP,NP-Complete和NP-Hard有什么区别？

我知道网上有很多资源.我想阅读你的解释,原因是它们可能与那些不同,或者有些东西我不知道.

我一直想知道是否有创建学校时间表算法的已知解决方案.基本上,它是关于优化给定班级 - 学科 - 教师协会的"小时分散"(在教师和班级案例中).我们可以假设我们在输入中有相互关联的课程,课程科目和教师,并且时间表应该适合在上午8点到下午4点之间.

我想可能没有准确的算法,但也许有人知道一个很好的近似或开发它的提示.

该款项子集的问题指出:

给定一组整数,是否有一个非空子集,其总和为零？

这个问题一般是NP完全的.我很好奇这个轻微变体的复杂性是否已知:

给定一组整数,是否有一个大小k的子集,其总和为零？

例如,如果k = 1,您可以执行二进制搜索以查找答案O(log n).如果k = 2,则可以将其归结为O(n log n)(例如,请参阅查找一个数组中的一对元素,其总和等于给定数字).如果k = 3,则可以这样做O(n^2)(例如,参见查找数组中的三个元素,其总和最接近给定数字).

是否有一个已知的界限可以作为一个函数放在这个问题上k？

作为动机,我正在考虑这个问题你如何将一个数组分成两部分,使这两部分具有相同的平均值？并试图确定它是否实际上是NP完全的.答案在于是否存在如上所述的公式.

除非采用一般解决方案,否则我非常有兴趣知道最佳约束k=4.

有许多现实世界的问题,结果证明是NP- hard.如果我们假设P ≠ NP,则对于这些问题没有任何多项式时间算法.

如果您必须解决其中一个问题,您是否有希望能够有效地解决这些问题？或者你只是运气不好？

在这个关于NP,NP-hard和NP-complete定义的问题的答案中,Jason提出了这样的主张

停止问题是经典的NP难问题.这是给出程序P和输入I的问题,它会停止吗？这是一个决策问题,但它不在NP中.很明显,任何NP完全问题都可以简化为这个问题.

虽然我同意停止问题在直觉上比NP中的任何问题都要困难得多,但老实说,我无法提出一个正式的数学证明,即停止问题是NP难的.特别是,我似乎无法找到从NP(或至少任何已知的NP完全问题)中的每个问题的实例到停止问题的多项式时间多对一映射.

是否有一个直截了当的证据表明停止问题是NP难的？

NP-hard的一些问题也是固定参数易处理的或FPT.维基百科将问题描述为固定参数易处理的问题,如果有一种算法可以在时间f(k)中解决它... | x | ^O(1).

这是什么意思？为什么这个概念有用？

我正在写一些问答游戏,如果玩家未能解决问题,需要计算机在测验中解决1个游戏.

鉴于数据:

1. 要使用的6个号码的列表,例如4,8,6,2,15,50.
2. 目标值,其中0 <值<1000,例如590.
3. 可用的操作是除法,加法,乘法和除法.
4. 可以使用括号.

生成数学表达式,其中评估与目标值相等或尽可能接近.例如,对于上面给出的数字,表达式可以是:(6 + 4)*50 + 15*(8-2)= 590

我的算法如下:

1. 从上面的(1)生成给定数字的所有子集的所有排列
2. 对于每个排列,生成所有括号和运算符组合
3. 算法运行时跟踪最接近的值

我想不出上面的蛮力算法的任何智能优化,这将使其加速数量级.此外,我必须优化最坏的情况,因为许多测验游戏将在服务器上同时运行.

今天为解决这个问题而编写的代码是(从项目中提取的相关内容):

from operator import add, sub, mul, div
import itertools


ops = ['+', '-', '/', '*']
op_map = {'+': add, '-': sub, '/': div, '*': mul}

# iterate over 1 permutation and generates parentheses and operator combinations
def iter_combinations(seq):
    if len(seq) == 1:
        yield seq[0], str(seq[0])
    else:
        for i in range(len(seq)):
            left, right = seq[:i], seq[i:]  # split input list at i`th …

我正在使用一些流行的python包作为基础,为图形和网络开发一个开源近似算法库.主要目标是在图形和网络上包含NP-Complete问题的最新近似算法.原因是1)我还没有看到一个很好的(现代)整合软件包来涵盖这个和2)它将是一个很好的教学工具,用于学习NP-Hard优化问题的近似算法.

在构建这个库时,我使用单元测试来进行健全性检查(正如任何适当的开发人员所做的那样).我对我的单元测试有些谨慎,因为它们本质上是近似算法可能无法返回正确的解决方案.目前我正在手工解决一些小实例,然后确保返回的结果与之匹配,但这在实现意义上是不可取的,也不是可扩展的.

单元测试近似算法的最佳方法是什么？生成随机实例并确保返回的结果小于算法保证的界限？这似乎有误报(测试时间很幸运,并不能保证所有实例都低于限制).

存在许多已知为NP难的优化问题,例如旅行商问题,MAX-SAT或找到图的最小色数.鉴于这种问题,我很好奇以下问题的复杂性:

鉴于NP难度优化问题和候选解决方案S,S是问题的最佳解决方案吗？

直观地说,似乎这可能是共同的NP难,因为通过猜测更好的解决方案并将其用作见证人来反驳优化问题的答案很容易,但我不知道如何展示这一点.事实上,我真的不知道如何推断这个问题的复杂性.

有谁知道这个决策问题的复杂性有任何好的下限？知道这是否是共同NP难,PSPACE-hard等会非常有趣.

我正在努力理解什么是不确定多项式时间问题和NP完全问题.我理解多项式时间可解决的问题,并在维基百科中看到NP问题.在阅读了这篇文章后,我试着想一些示例问题.据我了解,深度优先搜索的是无向的NP完全,因为每个决策都可以做出非决定性的(即如果我做出了错误的决定,我可以尝试其他选择)如果图表很大(cit是一个如果图形尺寸很小,则为多项式.)

任何人都可以用简单的例子简单地解释所有这些NP术语,而不需要使