algorithm - 3-SAT 的“输入大小”是什么意思？

Question

在计算复杂度理论中，如果解决输入大小为n的问题的计算次数以cf(n)为界，对于所有整数n，我们说算法的复杂度为O(f(n))，其中c是不依赖于n的正常数，并且f(n)是一个递增函数，与n一样趋于无穷大。

3 -SAT问题表述为：给定一个 CNF 表达式，其子句正好有 3 个文字，是否有一些 TRUE 和 FALSE 值分配给变量，这将使整个表达式为真？

例如，一个 CNF 表达式由涉及m个变量x1, ..., xm的k个子句组成。为了确定 3-SAT 是否具有多项式复杂度P(n)，我需要了解问题中的“什么是n ”这样简单的东西。

我的问题是：

在这个特定的 3-SAT问题中，输入大小n被认为是哪个？

是子句的数量k吗？或者是变量的数量m ？
或者n是k和m的某个函数？( n=f(k,m) )。

我在这个简单的问题上遇到了麻烦。

根据Timmie Smith的回答，我们可以考虑估计：

k <= constant * f(m)

其中m是 m 的多项式函数。
更准确地说，函数P(m)它可以被认为是指数3（即三次）。

因此，如果我们考虑 3-SAT 的复杂度f(k)，我们将有：

f(k, m)=f(P(m),m), (with P(m) = m^3).

因此，如果函数f在k和m中是多项式，那么实际上会在m中产生多项式。因此，通过将m视为输入大小，将估计给定算法是否是m中的多项式，以便了解 3-SAT 是否在 P 中。

如果您同意，我可以接受 Timmie 的回答。

更新：

我在这里做了同样的问题：

接受的答案对我有帮助。

score 3 · Accepted Answer

输入是变量的数量 m。这是因为给定 m 个变量可以形成的可能子句的数量是变量数量的多项式函数。

score 3 · Accepted Answer

我在卡内基梅隆大学的一些论文中看到了针对此类问题的“输入大小”的以下定义：

写下输入所需的位数

考虑到输入可以被压缩，这个定义对我来说很有意义，因为它是输入熵的一个很好的度量。

我的2美分！干杯！！

score 3 · Accepted Answer

输入大小是变量的数量m。

这样做的原因是解决问题需要遍历的搜索空间的大小完全由变量的数量决定：每个变量有两种可能的状态（1 或 0），搜索空间由所有可能的赋值组成. 蛮力算法只会测试所有可能的分配 ( 2^m) 以遍历搜索空间。尽管大多数 3-SAT 算法会受到子句数量的显着影响，但这不会影响潜在问题的复杂性。

因此，输入大小也是普通旧 SAT 的变量数，其中搜索空间看起来相同，尽管以非暴力方式解析子句的工作方式完全不同。

3 回答 3