问题标签 [np]

NP、NP-Complete和NP-Hard之间有什么区别？

我知道网上有很多资源。我想阅读您的解释，原因是它们可能与外面的不同，或者有些我不知道。

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

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

我知道 P=NP 到现在还没有解决，但是任何人都可以告诉我以下内容：目前最有希望的数学/计算机科学方法可以帮助解决这个问题吗？或者，到目前为止，甚至没有任何已知的可能有用的方法吗？有没有关于这个主题的（免费）纲要，我可以在其中找到在该领域完成的所有/大部分研究？

给定一组项目，每个项目都有一个值，确定要包含在集合中的每个项目的数量，以使总值小于或等于给定限制，并且总值尽可能大。

例子：

我正在寻找一种算法（如背包或装箱）来确定组合。任何帮助表示赞赏。

试图复习计算理论，但不确定解决方案：

我有一种感觉，这可能与找到一个 NP 问题并找到一个减少因子 α 的问题有关。

以下哪项是对问题 X 的最准确分类？

• X 在 NP
• X 在 P 中
• X 在 O(n ² )
• X 在 Θ(n ² ) 中。

如果有人能向我解释这个问题的答案，我将不胜感激？

我相信它是NP或P，但我真的不确定

有许多已知是 NP-hard 的优化问题，例如旅行商问题、MAX-SAT 或寻找图的最小色数。鉴于此类问题，我很好奇以下问题的复杂性：

给定一个 NP-hard 优化问题和一个候选解 S，S 是该问题的最优解吗？

直觉上，这似乎很难 co-NP，因为通过猜测更好的解决方案并将其用作见证来反驳优化问题的答案很容易，但我不知道如何证明这一点。事实上，我真的不知道如何推理这个问题的复杂性。

有谁知道这个决策问题的复杂性有什么好的下限？知道这是否是 co-NP 难、PSPACE 难等会非常有趣。

我最近阅读了有关NP和P的文章。那么寻找给定单词组合的问题是NP问题吗？例如，给定单词anto，结果可以是 anot,toan 等。据我所知，只要我们可以在多项式时间内检查问题的解决方案，就意味着它属于 NP。那么组合问题属于NP吗？

这只是为了知道我是否已经很好地理解了NP和P。

将任何问题拆分为 NP 和 P 的主要意图或主要用途是什么？这是否有任何历史原因，还是他们创造了这些概念来帮助我们？如果是这样，这些对我们有什么帮助？

假设您必须实现一个工具来有效地解决一个 NP 难题，内存使用量不可避免地可能会激增（在某些情况下输出大小与输入大小成指数关系），并且您特别关心该工具在运行时的性能时间。一旦知道了基础理论，源代码也必须是可读和可理解的，这一要求与工具本身的效率一样重要。

我个人认为 3 种语言可能适合这三个需求：c++、scala、java。它们都提供了对数据类型的正确抽象，从而可以比较不同的结构或将相同的算法（这也很重要）应用于不同的数据类型。

C++ 具有静态编译和优化的优点，并且通过函数内联（如果数据结构和算法设计仔细）和其他优化技术，可以在保持相当好的可读性的同时实现接近纯 C 的性能。如果您还非常注意数据表示，则可以优化缓存性能，当缓存未命中率较低时，速度可以提高几个数量级。

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

我对 scala 的担忧与 Java 或多或少相同，而且除非我对编译器和标准库有深入的了解，否则我无法控制语言的优化方式。但是很好：我得到了一个非常干净的语法:)

你对这个话题有什么看法？你已经不得不处理这个问题了吗？您会用这些语言中的任何一种实现具有此类属性和要求的算法，还是会提出其他建议？你会如何比较它们？