algorithm - k-CNF 在子句数量的线性时间内的解决方案，它会是一个解决方案吗？或者它应该与不同变量的数量成线性关系

Question

我有一个解决方案，它对CNF公式中的子句数量具有线性时间复杂度，即O（c ^ 2 X n），使得n是CNF公式中不同变量的数量，是否会考虑这个解决方案是否作为 K-CNF 的线性解？由于子句的数量可能是 c = 2^n 算法应该使其线性以解决 K-CNF 的实变量是多少？可以是C吗？或者应该是n？或者是什么？

我没有正确理解 CNF 复杂性问题

Answer 1

在复杂性理论中，算法的运行时间通常是作为输入长度（以位为单位）的函数来衡量的。因此，例如，如果您的算法的运行时间与子句数量呈线性关系，因为子句数量是输入大小的线性函数，那么您的算法将是 k-SAT 的线性时间解。

k-SAT 的线性时间算法将是理论 CS 的重大突破。您是否对其进行了广泛的测试？SAT 求解器每年都会举办（曾经？）比赛，看看他们在大量输入上的表现如何。如果您还没有下载一些测试用例，您可能想从那里下载一些测试用例，以在过去 50 年左右组装的困难用例上验证您的算法。