我看到很多关于这个问题的相互矛盾的信息。一些网站说它是 NP 完全的，而另一些网站则说它是共同 NP 完全的。我能找到的唯一真正一致的信息是这绝对是 NP 难的。它是哪一个？为什么？
问问题
1288 次
1 回答
1
我认为这取决于您如何定义 MAX-3SAT。
如果将 MAX-3SAT 定义为函数问题“给定 3CNF 公式，产生一个变量赋值最大化满足子句的数量”，那么它既不是 NP 完全也不是 co-NP 完全。NP 和 co-NP 是决策问题的类别，因此没有函数问题可以属于它们。因此，MAX-3SAT 不能属于 NP 或 co-NP，因此对于任何一个类都不是一个完整的问题。这个函数问题是 NP-hard 通过从 vanilla 3SAT 减少而来的——如果你能找到最令人满意的赋值，你可以通过查看是否满足所有子句来检查原始公式是否可以满足。
您还可以将 MAX-3SAT 定义为决策问题“给定一个 3CNF 公式和一个数字 n，确定是否有一个变量赋值给该公式，使至少 n 个子句为真。” 这绝对是 NP 和 NP 完全的，通过减少 3SAT。
另一方面，如果您将 MAX-3SAT 定义为决策问题“给定 3CNF 公式和对该公式的变量赋值，该赋值是最大化满足子句数量的赋值吗？”那么它将属于 co- NP（如果答案是否定的，您可以通过展示更令人满意的作业来确认这一点）。不过，我不确定它是否是 NP 难的，我也不确定它是否是 co-NP 难的。
希望这可以帮助！
于 2014-12-04T21:40:11.180 回答