验证 NP 困难优化问题的解决方案的复杂性？
有许多已知的 NP 困难优化问题，例如旅行商问题、MAX-SAT 或查找图的最小色数。考虑到此类问题，我很好奇以下问题的复杂性：
给定一个 NP 难优化问题和一个候选解 S，S 是该问题的最优解吗？
直观上，这似乎可能是 co-NP 困难，因为通过猜测更好的解决方案并将其用作见证人很容易反驳优化问题的答案，但我不知道如何证明这一点。事实上，我真的不知道如何推理这个问题的复杂性。
有谁知道这个决策问题的复杂性有什么好的下限吗？知道这是否是 co-NP 困难、PSPACE 困难等将非常有趣。
There are many optimization problems that are known to be NP-hard, such as the traveling salesman problem, MAX-SAT, or finding the minimum chromatic number of a graph. Given a problem of this sort, I'm curious about the complexity of the following problem:
Given an NP-hard optimization problem and a candidate solution S, is S the optimal solution to the problem?
Intuitively, it seems like this might be co-NP hard, since it's easy to refute an answer to an optimization problem by guessing a better solution and using it as a witness, but I have no idea how to show this. In fact, I don't really know how to reason about the complexity of this problem.
Does anyone know of any good lower bounds on the complexity of this decision problem? Knowing whether this was co-NP hard, PSPACE-hard, etc. would be really interesting.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
“NP 难优化问题”这个术语似乎有点太宽泛，无法找到令人满意的答案。
例如，我看不出是什么阻止决策问题被视为 NP 难优化问题 - 如果您考虑 MAX-CNF-SAT 问题，其解决方案的评分为下限（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)。对该类的改进可能是仅将问题视为 NP 难优化问题，如果对于每个 K 存在一个实例，该实例具有至少 K 个解决方案，且所有解决方案的得分都不同。
我认为我仍然可以通过这种方式进行欺骗：
考虑将 N 个虚拟变量添加到 TAUTOLOGY 输入的减少，如下所示：
其中 S 是求反输入。作为初始评估，我选择 d1, ..., dN = false，但作为分数，我给出一个函数，如果前 N 个子句全部为 false，则返回 2N - 1，否则返回满足子句的数量。如果满足所有子句，这样的函数只会返回 2N，但很容易具有至少 N 个不同的值。
恐怕如果评分函数上没有一些复杂的规律性条件，这就是我们能得到的最好的结果，除非你认为 NP 难优化问题的定义是“一个问题，给定一个候选解 S，我们可以在多项式时间验证 S 是否最优”，在这种情况下“最优”显然是 P 并且一点也不有趣：/
The term 'NP-hard optimization problem' seems a bit too broad to let a satisfying answer be found.
For instance, I can't see what precludes decision problems from being considered NP-hard optimization problems - if you consider, say, the MAX-CNF-SAT problem with the solutions being scored as floor(k/N), where k is the number of satisfied clauses and N is the total number of clauses in the instance (which is clearly computable in polynomial time), then any valuation which yields a 1 in this formula will have to satisfy the whole formula. So let's assume that we are maximizing floor(k/N) and call this the FLOOR-CNF-SAT optimization problem:)
This implies you can reduce TAUTOLOGY to said optimization problem - negate the input and add any solution as S. You can even add a dummy variable to make sure the initial solution is gets a 0 in the FLOOR-CNF-SAT problem. Negation is polynomial in time.
Then if a solver for the proposed problem deems S to not be optimal, there must clearly be a valuation which yields a 1 according to our crafted function and thus satisfies the whole formula - in turn providing a valuation that does not satisfy the original input to TAUTOLOGY.
By cheating slightly (using an artificially crafted optimization problem) we have established the 'is optimal' problem as co-NP-complete, since TAUTOLOGY is easily shown to be co-NP-complete.
By your own argument the 'is optimal' decision problem is co-NP-hard, since as a witness you only need a better solution - score S, score the witness and compare.
I don't really feel great about this reduction but I can't easily improve on the problem class. If you require that there be instances which score arbitrarily high and not just {0, 1}, I could just use N * floor(k/N). An improvement to the class could be to only consider a problem an NP-hard optimization problem if for each K there exists an instance that has at least K solutions which all score differently.
I think I can still cheat my way through that:
Consider a reduction that adds N dummy variables to the TAUTOLOGY input as follows:
where S is the negated input. As an initial valuation I choose d1, ..., dN = false, but as a score I give a function that returns 2N - 1 if the first N clauses are all false, otherwise it returns the number of satisfied clauses. Such a function would only return 2N if all the clauses were satisfied but could easily have at least N distinct values.
I am afraid that without some complicated regularity conditions on the scoring function this is the best we can get, unless you consider the definition of an NP-hard optimization problem to be 'a problem for which, given a candidate solution S, we can in polynomial time verify whether S is optimal', in which case 'is-optimal' is clearly P and it's no fun at all:/
NP 难问题“至少与 NP 中最难的问题一样难”。
NP 难问题的示例：停止问题（程序 A 是否可以停止？）:)
假设您有一个候选解决方案：“不，程序 A 无法停止”。我们知道，你无法验证它——它是不可判定的。
你甚至无法检查“是的，程序 A 停止了”——因为它可能需要很长时间，所以它也是不可判定的。
NP-hard problem is "at least as hard as the hardest problems in NP".
Example of NP-hard problem: halting problem (whether program A can stop or not?) :)
Let's say you have a candidate solution: "no, program A can't stop". We know, that you can't verify it -- it's undecidable.
You can't even check if "yes, program A stops" -- because it may take forever, so it's also undecidable.
因为S是一个候选解；假设没有其他 S 可以被证明是贪婪的或不如任何其他 S 最优。那么 S 一定是当前问题的最优解。
Because S is a candidate solution; given that there are no other S in which S can be proven to be greedy or less optimal than any other S. It must be that S is at current the MOST optimal solution for the problem.