NP难优化问题的解决方案验证的复杂性？

Question

有许多优化问题已知是NP难的，例如旅行商问题，MAX-SAT问题或者寻找图的最小色数。针对这种问题，我对以下问题的复杂性很感兴趣：

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

直觉上，这个问题可能是co-NP难的，因为可以通过猜测更好的解并将其作为证人来轻易地反驳优化问题的答案，但我不知道如何证明。实际上，我不知道如何推理这个问题的复杂性。

有人知道这个决策问题的复杂性的任何良好下界吗？知道它是co-NP难，PSPACE-hard等会非常有意思。

- templatetypedef

---

假设优化问题的决策变量是NP完全问题，你已经概述了一个证明，证实最优解在coNP中。最直接的硬度结果路径将是从coNP难问题进行多项式时间的归约，但这样的归约会有困难，即找到要验证的解决方案。我上过研究生级别的复杂性课程，并认为这适用于计算理论。 - userOVER9000

如果优化问题是一个正整数最小化问题（即答案总是一个正整数），你可以使用“IsOptimal”验证器进行二分查找，因此看起来这也是NP-Hard的... - Aryabhatta

@Moron：这一定是这样吗？请注意，问题需要一个实际的候选解决方案，而不仅仅是它的“值”。 - mhum

@mhum：我说的是值就是解决方案的情况（比如色数）。当然，如果你需要染色，这种方法就不起作用了。 - Aryabhatta

@蠢货：确实，我将问题解释为说，“解决方案”，比如色数，指的是实际上的着色方法，而不仅仅是色数本身。我从提问者使用猜测的解决方案推断出该问题在co-NP中的部分得到了这种解释。 - mhum

Answer 1

“NP-hard优化问题”这个术语似乎过于宽泛，难以找到令人满意的答案。例如，我看不出为什么不能将决策问题视为NP-hard优化问题——如果你考虑MAX-CNF-SAT问题，并将解作为floor(k/N)进行评分，其中k是满足子句的数量，N是实例中子句的总数（这显然可以在多项式时间内计算），那么任何能使此公式得到1的赋值都必须满足整个公式。因此，假设我们正在最大化floor(k/N)，并将其称为FLOOR-CNF-SAT优化问题：）

这意味着您可以将TAUTOLOGY问题简化为所述的优化问题——对输入取反，并添加任何解作为S。您甚至可以添加一个虚拟变量，以确保初始解在FLOOR-CNF-SAT问题中得到0。否定在多项式时间内完成。

然后，如果所提出的问题的求解器认为S不是最优解，那么必须明确存在一种赋值方式，根据我们精心设计的函数得到1，从而满足整个公式——进而提供了一种不满足TAUTOLOGY原始输入的赋值方式。

通过稍微作弊（使用人工制作的优化问题），我们已经确定了“是否最优”的问题为co-NP完全问题，因为可以轻松证明TAUTOLOGY是co-NP完全问题。

根据你自己的论点，“是否最优”的决策问题是co-NP-hard问题，因为作为证人，你只需要一个更好的解——评分S，评分证人并进行比较。

我对这种简化并不感到满意，但我很难改进这个问题类。如果您要求存在得分任意高而不仅仅是{0,1}的实例，则可以使用N * floor(k/N)。该类的改进可能是仅在每个K都存在至少K个解的实例时才将问题视为NP-hard优化问题。

我认为我仍然可以通过作弊来解决这个问题：

考虑一种将N个虚拟变量添加到TAUTOLOGY输入中的简化方式，如下所示：

d1 && d2 && d3 ... && dN && (S)

其中S为输入的否定形式。作为初始估价，我选择d1，…，dN = false，但是作为得分，我提供了一个函数，如果前N个子句都为false，则返回2N-1，否则返回满足的子句数。这样的函数只有在所有子句都被满足时才会返回2N，但很容易至少有N个不同的值。

恐怕除非对得分函数进行一些复杂的规则限制，否则这就是我们能得到的最好结果。除非您认为NP难优化问题的定义是“给定候选解S，我们可以在多项式时间内验证S是否最优”，在这种情况下，“最优”显然是P，但并不好玩:/

- t.dubrownik

Answer 2

NP-hard问题是“至少与NP中最难的问题一样难”。

NP-hard问题示例：停机问题（程序A是否可以停止？）:)

假设您有一个候选解决方案：“不，程序A无法停止”。我们知道，您无法验证它-这是不可判定的。

甚至您也无法检查“是的，程序A会停止”，因为它可能需要永远的时间，所以也是不可判定的。

- Marcin Krupowicz

---

停机问题不是NP难的。它是不可判定的（一般而言）。但是，如何验证旅行推销员的路线是否为最短长度？它应该可以在多项式时间内进行验证。 - phkahler

如果我错了，请纠正我，但我认为停机问题是 NP 难的，因为任何 NP 问题都可以在多项式时间内约化为它。你不必在 NP 中才能成为 NP 难问题。我对此有误吗？ - templatetypedef

而且要明确的是，处于NP和NP-hard问题中的问题是NP完全问题。 - Marcin Krupowicz

停机问题既是不可判定的，又是NP难问题。它们并不是互斥的。 - userOVER9000

显然，停机问题是NP难的：给定任何一个NP问题，我编写一个程序，系统地尝试所有可能的证明，直到找到一个证明可以证明答案是YES。然后我使用停机问题的解决方案来判断这个程序是否会停机，从而证明答案是YES（如果程序停机）或NO（如果程序永远不会停机）。无法判定并不意味着它是NP难的。能够解决NP中的任何问题（以及许多其他问题）才使其成为NP难的。 - gnasher729

Answer 3

因为S是一个候选解决方案；假设没有其他的S可以被证明比S更贪心或不够优秀。那么，S目前必须是该问题最优解。

- Suroot