tem*_*def 11 algorithm complexity-theory lower-bound np
存在许多已知为NP难的优化问题,例如旅行商问题,MAX-SAT或找到图的最小色数.鉴于这种问题,我很好奇以下问题的复杂性:
鉴于NP难度优化问题和候选解决方案S,S是问题的最佳解决方案吗？
直观地说,似乎这可能是共同的NP难,因为通过猜测更好的解决方案并将其用作见证人来反驳优化问题的答案很容易,但我不知道如何展示这一点.事实上,我真的不知道如何推断这个问题的复杂性.
有谁知道这个决策问题的复杂性有任何好的下限？知道这是否是共同NP难,PSPACE-hard等会非常有趣.
小智 5
术语“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 并因此满足整个公式 - 反过来提供不满足原始输入的估值同义词。
通过稍微作弊（使用人工设计的优化问题），我们将“最优”问题确定为 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 并且一点也不有趣：/