11

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

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

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

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

4

3 回答 3

5

术语“NP 难优化问题”似乎有点过于宽泛，无法找到令人满意的答案。

例如，我看不出是什么排除了决策问题被视为 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 并因此满足整个公式的估值 - 反过来提供一个不满足原始输入的估值自言自语。

通过稍微作弊（使用人为设计的优化问题），我们将“最优”问题确定为 co-NP-complete，因为 TAUTOLOGY 很容易被证明是 co-NP-complete。

根据您自己的论点，“最优”决策问题是 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 个子句全部为假，则返回 2N - 1，否则返回满意子句的数量。如果所有子句都满足，这样的函数只会返回 2N，但很容易有至少 N 个不同的值。

恐怕在评分函数上没有一些复杂的规律性条件，这是我们能得到的最好的，除非你认为一个 NP-hard 优化问题的定义是“一个问题，给定一个候选解 S，我们可以在多项式时间验证 S 是否最优'，在这种情况下，'is-optimal' 显然是 P，而且一点也不好玩：/

于 2011-03-29T14:41:38.013 回答
2

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

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

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

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

于 2011-02-28T21:45:25.593 回答
0

因为 S 是候选解；假设没有其他 S 可以证明 S 是贪婪的或不如其他任何 S 最优的。它必须是 S 目前是该问题的 MOST 最优解。

于 2011-03-30T02:03:24.537 回答