标签: np

我对NP难问题感到困惑.
NP中存在一些NP难题,称为NP-Complete,有些不在NP中.
例如:暂停问题只是NP难,而不是NP完全.
但为什么它不是NP完全？我的意思是,问题必须具备哪些属性才能成为
"NP难但不是NP完全问题"？

计算机科学中是否存在任何只能在双指数时间内解决的重大问题？如果它们存在,那么它们属于哪类问题？

我知道他们的完全对应物意味着NP - 完全是NP问题中最难的,并且共同NP完全意味着共同NP问题中最难的但是两者之间的区别是什么？我的教科书上写着"是的,没有被逆转",这并没有给我留下那么多线索.

我目前正在编写一个将学生映射到课程的程序.目前,我正在使用SAT-Solver,但我正在尝试实现一个多项式时间/非贪心算法,它解决了以下子问题:

• 有学生(50-150)
• 有科目(10-20),例如'数学','生物','艺术'
• 每个科目(至少一门)都有课程,例如'math-1','math-2','biology-1','art-1','art-2','art-3'
• 学生选择一些(固定的)科目(10-12),并且对于每个科目,学生必须被分配到现有的一门课程(如果可能的话).选择哪个课程'math-1'或'math-2'并不重要.
• 这些课程允许的学生人数最多(20-34)
• 每门课程都在一个固定的区块内(=时间段1到13)
• 学生可能不会被分配到同一区块的课程

我现在描述到目前为止我所做的事情.

(1)忽略课程 - 学生限制

我能够用匈牙利算法/二分匹配来解决这个问题.每个学生可以通过如下建模来单独计算:

• 左节点代表主题'数学','生物','艺术'(学生)
• 右节点表示块'1','2',....'13'
• 从"主题"到"阻止"的每个过程插入一条边

通过这种方式,学生被分配到课程的每个科目,而不参加同一区块的课程.但课程限制被忽略了.

(2)忽略学生的选定科目

我能够用max-flow-algorithm解决这个问题.对于每个学生,建模如下:

• 第1层:从源到每个学生,流量为13
• 第2层:从每个学生到他/她的个人区块,流量为1
• 第3层:从每个学生块到该块中的每个课程,流程为1
• 第4层:通过'max-student-limit'从每个球场到水槽

通过这种方式,学生选择任意课程,并且课程限制已满.但是他/她可能不幸并被分配到'数学-1','数学-2'和'数学-3'而无视主题'生物'和'艺术'.

(3)贪婪的匈牙利人

我的另一个想法是一次匹配一个学生与匈牙利算法并调整权重,以便"更多空课程"是首选.例如,可以建模:

• 左节点是学生的主题
• 右边节点是块
• 对于每个球场,插入一个边缘从主体到球场的块重量=自由座位数

然后计算最大权重匹配.

我真的很感激任何建议/帮助.

谢谢!

假设您必须实现一个有效解决NP难问题的工具,不可避免的内存使用量爆炸(输出大小在某些情况下指数输入大小)并且您特别关注此工具在运行时的性能时间.一旦知道了基础理论,源代码也必须是可读和可理解的,并且这个要求与工具本身的效率同样重要.

我个人认为3种语言可能适合这三个要求:c ++,scala,java.它们都提供了对数据类型的正确抽象,使得可以比较不同的结构或将相同的算法(这也很重要)应用于不同的数据类型.

C++具有静态编译和优化的优点,并且通过函数内联(如果数据结构和算法经过精心设计)和其他优化技术,可以在保持相当好的可读性的同时实现接近纯C的性能.如果您在数据表示中也非常谨慎,则可以优化缓存性能,当缓存未命中率较低时,缓存性能可以获得数量级的速度.

Java是JIT编译的,它允许在运行时应用优化,并且在这类算法中可能在不同的运行之间具有不同的行为,这可能是一个加号.我担心这样的方法可能会受到垃圾收集器的影响,但是在这种算法的情况下,通常连续分配内存并且Java堆性能比C/C++好得多,如果你在语言中实现自己的内存管理器,你可以甚至达到很好的效率.相反,这种方法无法内联方法调用(这会导致巨大的性能损失)并且无法控制缓存性能.在专业人士中,语法比C++更好,更清晰.

我对scala的担忧与Java大致相同,而且我无法控制语言的优化程度,除非我对编译器和标准库有深入的了解.但是好吧:我得到一个非常干净的语法:)

你对这个问题有什么看法？你有没有必须处理这个？您是否会使用这些语言中的任何一种语言实现具有此类属性和要求的算法,或者您会建议其他什么？你会如何比较它们？

我试图理解NP-Complete和NP-Hard之间的区别.

以下是我的理解

NP-Hard问题是在多项式时间内无法解决的问题,但可以在多项式时间内验证.
NP-Complete问题是NP中的问题,也是NP-Hard问题.

以上定义是否正确？如果是这样,那么问题不是NP而是NP-Hard.难道它们不会比NP完全问题更难,说它们只能在指数时间内得到解决和验证吗？

我对这三个类别的理解是否正确？

为了表明问题X是NP:

1. 表明X可以在多项式时间内确定性地验证(或者X可以使用NTM解决)

要显示问题,X是NP-Complete:

1. 表明X可以在多项式时间内确定性地验证(或者X可以使用NTM解决)
2. 表明给定已知的NP-C问题L,L≤pX
3. 证明给定一个已知的NP-C问题L,X≤pL(这一步是否必要？如果是这样,这是区分纯NP-Hard问题与NP-C问题的原因吗？)

为了表明问题X是NP-Hard:

1. 表明给定已知的NP-C问题L,L≤pX

我有以下操作来添加一个状态，显示一个数据帧列的列中的任何字符串出现在另一个数据帧的指定列中。它看起来像这样：

df_one['Status'] = np.where(df_one.A.isin(df_two.A), 'Matched','Unmatched')

如果字符串大小写不同，这将不匹配。是否可以在不区分大小写的情况下执行此操作？

此外，是否有可能回归“匹配”时的值df_one.A从全字符串结尾df_two.A？例如 df_one.A abcdefghijkl -> df_two.A ijkl = 'Matched'

我正在从这里（第 8、9 页）阅读有关 NP 硬度的信息，并且在注释中，作者将 3-SAT 形式的问题简化为可用于解决最大独立集问题的图形。

在示例中，作者将以下 3-SAT 问题转换为图形。3-SAT 问题是：

(a ? b ? c) ? (b ? ~c ? ~d) ? (~a ? c ? d) ? (a ? ~b ? ~d)

生成的等效图为：

作者指出，如果满足以下条件，则两个节点通过边连接：

1. 它们对应于同一子句中的文字
2. 它们对应于一个变量及其逆。

我无法理解作者是如何提出这些规则的。

• 为什么我们需要在变量和它的逆之间画边？
• 假设有两个子句，子句 1 有 (a,b,~c) 和子句 2 有 (~a,b,c) 连接子句 1 到子句 2，为什么我们必须连接 a 和 ~a？为什么我们不能将 a（第 1 条）与 c（第 2 条）连接起来？

NP-complete的定义是

如果是,问题是NP完全

1. 它属于NP类
2. NP中的所有其他问题多项式转换为它

因此,如果NP中的所有其他问题转化为NP完全问题,那么这是否也意味着所有NP问题也是NP完全的？如果它们是相同的,那么对两者进行分类有什么意义呢？

换句话说,如果我们有NP问题那么通过(2)这个问题可以转化为NP完全问题.因此,NP问题现在是NP完全的,NP = NP完全.这两个类都是等价的.

试图为自己澄清这一点.