定义 SAT2016 = {\phi | \phi 是一个 CNF 公式，最多有 2016 个子句}。假设 P \neq NP，SAT2016 NP-complete 吗？
由于每个子句中的文字数量没有限制，因此尚不清楚是否存在多项式时间算法来检查具有恒定子句数量限制的公式的可满足性。
欢迎您的想法。
问问题
276 次
1 回答
0
SAT2016 在 P.
请注意，为了满足公式，您必须将 1 分配给每个子句的至少一个文字。每个子句最多包含2n文字。因此，从每个子句中选择单个文字的方法最多为(2n)^2016. 为了确定公式是否可满足，您应该（最多）迭代(2n)^2016可能性（从每个子句中选择一个文字）并检查每种可能性是否合法。也就是说，对于 2016 年文字的每个选择（每个子句中的一个），您应该检查 2016 年文字中的两个是否恰好是某个变量及其否定。如果是这种情况，您将继续选择 2016 年文字的下一个选择。如果你经历了所有(2n)^2016可能性并发现它们都包含冲突，您得出结论该公式不可满足。
由于存在最多的(2n)^2016可能性，并且检查给定的可能性需要恒定的时间（因为您只需要遍历一组 2016 年文字中的所有可能对），因此算法的运行时间是多项式 in n.
于 2016-06-07T09:52:15.440 回答