问题标签 [np]

我对 NP 难题感到困惑。
一些 NP-hard 问题在 NP 中称为 NP-Complete，而有些则不在 NP 中。
例如：停机问题只是 NP-hard，而不是 NP-complete。
但为什么它不是 NP-complete 呢？我的意思是一个问题应该有什么属性才能被称为
“NP-hard但不是 NP-complete 问题”？

是否可以编写一个程序来打印从大小为 n 的输入数组中添加到 k 的所有对。如果有怎么办？我听说这个问题是NP-Complete。我想知道我们是否可以用典型的编程语言（如 C/C++）来解决这个问题

我是一名计算机科学专业的学生，​​我在理解基于验证器的 NP 问题定义时遇到了一些问题。

该定义说，如果可以在给定“证书”的情况下通过确定性图灵机在多项式时间内验证问题，则该问题存在于 NP 中。

但是，如果证书正是问题的解决方案，会发生什么？它只是一点点，它显然受到输入大小的多项式限制，并且显然可以在常数中验证，因此是多项式时间。

因此，每个决策问题都属于 NP。

我哪里错了？

这是我的第一个 stackoverflow 问题，所以要温柔。如果这已经被打死了，我提前道歉......我在 NP 上阅读了一些主题，但我没有找到对我的问题的诱人答案（如果有的话，我想出了一些新的）。简要地：

1. 是否存在可判定但在 NP 中不可判定的决策问题？
2. 如果是这样，要求解决方案的问题是否比等效的决策问题更难？

我怀疑第一个问题的答案是响亮的“是”，而第二个问题的答案是响亮的“不”。

在第一种情况下，一个示例问题可能是“给定集合 S、S 的子集 T 和域为 2^S 的函数 f，确定 T 是否使 f 最大化”。对于通用 S、T 和 f，如果不检查 S 的所有子集 X 的 f(X)，您甚至无法验证这一点，对吧？

在第二种情况下......好吧，我承认这更像是一种预感。出于某种原因，答案是否包含一位（用于决策问题）或任何（有限）位似乎并不重要......或者换句话说，为什么你不应该考虑TM 停止后留在磁带上的符号作为“答案”的一部分。

编辑：实际上，我有一个问题......你的构造如何精确地表明功能问题比决策问题“不难”？如果有的话，您已经证明回答函数问题并不比回答决策问题更容易......这是微不足道的。也许这是我以草率的方式提出问题的错。

给定 NP 中的 TM T1 解决了变量 X 的问题“X 是问题 P 的解决方案”并且（为了论证）固定 P，是否保证 NP 中会有一个 TM T2 在 T1 停止的任何地方停止，它在任何地方都以“停止接受”状态结束，并在磁带上留下例如 X 的二进制表示？

我正在努力理解什么是非确定性多项式时间问题和 NP 完全问题。我了解多项式时间可解决的问题，并在维基百科中看到了关于 NP 问题。在阅读完这篇文章后，我试图思考一些示例问题。据我了解，无向中的深度优先搜索是 NP 完全的，因为如果图很大（引用一个是如果图形大小很小，则为多项式。）

谁能在不使用太多数学的情况下用简单的例子简要解释所有这些 NP 术语？

在这个关于 NP、NP-hard 和 NP-complete 定义的问题的回答中，Jason 声称

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

虽然我同意停机问题在直觉上是一个比 NP 中的任何问题都“更难”的问题，但老实说，我无法提出一个正式的数学证明来证明停机问题是 NP 难的。特别是，我似乎无法找到从 NP 中的每个问题（或至少任何已知的 NP 完全问题）的实例到停止问题的多项式时间多对一映射。

是否有直接的证据证明停机问题是 NP 难的？

NP完全的定义是

一个问题是 NP 完全的，如果

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

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

换句话说，如果我们有一个 NP 问题，那么通过（2）这个问题可以转化为一个 NP 完全问题。因此，NP 问题现在是 NP-完全的，并且 NP = NP-完全。两个类是等价的。

只是想为自己澄清一下。

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

在构建这个库时，我使用单元测试来进行完整性检查（就像任何合适的开发人员一样）。我对我的单元测试有些谨慎，因为就其本质而言，近似算法可能不会返回正确的解决方案。目前我正在手动解决一些小实例，然后确保返回的结果与之匹配，但这是不可取的，在实现意义上也不可扩展。

对近似算法进行单元测试的最佳方法是什么？生成随机实例并确保返回的结果小于算法保证的界限？这似乎有误报（那个时候测试很幸运，不能保证所有实例都低于界限）。

我有以下NP完全问题：

鉴于：

• N × N 场中的一组位置，
• 一组 m 个节点，和
• 节点的连接图（即无向图，其边表示每对相互接触的节点），以及
• 接触范围 R（与 N × N 字段的长度单位相同），

找到与连接图相关的字段中节点的放置（即放置节点，使任何接触的对比 R 更近，而任何不接触的对比 R 更远），或表明这种放置不存在。

这个问题可以简化为一个众所周知的NP完全问题吗？

（也可以考虑问题的优化版本，即找到最优化的放置）

将无向图的每个节点与正权重相关联。顶点打包问题是找到具有最大权重和的节点的子集，这样就不会选择两个节点之间有一条边。

解决二部图的顶点打包问题的最有效方法是什么？我已经能够将其表述为具有两倍节点数的最大流量问题。有没有更有效、可能更直接的方法？