有许多优化问题已知是NP难的,例如旅行商问题,MAX-SAT问题或者寻找图的最小色数。针对这种问题,我对以下问题的复杂性很感兴趣:
给定一个NP难的优化问题和一个候选解S,S是否是该问题的最优解?
直觉上,这个问题可能是co-NP难的,因为可以通过猜测更好的解并将其作为证人来轻易地反驳优化问题的答案,但我不知道如何证明。实际上,我不知道如何推理这个问题的复杂性。
有人知道这个决策问题的复杂性的任何良好下界吗?知道它是co-NP难,PSPACE-hard等会非常有意思。
有许多优化问题已知是NP难的,例如旅行商问题,MAX-SAT问题或者寻找图的最小色数。针对这种问题,我对以下问题的复杂性很感兴趣:
给定一个NP难的优化问题和一个候选解S,S是否是该问题的最优解?
直觉上,这个问题可能是co-NP难的,因为可以通过猜测更好的解并将其作为证人来轻易地反驳优化问题的答案,但我不知道如何证明。实际上,我不知道如何推理这个问题的复杂性。
有人知道这个决策问题的复杂性的任何良好下界吗?知道它是co-NP难,PSPACE-hard等会非常有意思。
d1 && d2 && d3 ... && dN && (S)
其中S为输入的否定形式。作为初始估价,我选择d1,…,dN = false,但是作为得分,我提供了一个函数,如果前N个子句都为false,则返回2N-1,否则返回满足的子句数。这样的函数只有在所有子句都被满足时才会返回2N,但很容易至少有N个不同的值。
恐怕除非对得分函数进行一些复杂的规则限制,否则这就是我们能得到的最好结果。除非您认为NP难优化问题的定义是“给定候选解S,我们可以在多项式时间内验证S是否最优”,在这种情况下,“最优”显然是P,但并不好玩:/
NP-hard问题是“至少与NP中最难的问题一样难”。
NP-hard问题示例:停机问题(程序A是否可以停止?):)
假设您有一个候选解决方案:“不,程序A无法停止”。我们知道,您无法验证它-这是不可判定的。
甚至您也无法检查“是的,程序A会停止”,因为它可能需要永远的时间,所以也是不可判定的。
因为S是一个候选解决方案;假设没有其他的S可以被证明比S更贪心或不够优秀。那么,S目前必须是该问题最优解。