algorithm - 3-SAT 的 "input size"是什么意思？

Question

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

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

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

我的问题是:

Which is considered, in this particular 3-SAT problem, the input size 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的回答是好的。

更新:

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

https://cstheory.stackexchange.com/questions/18756/whats-the-meaning-of-input-size-for-3-sat

接受的答案对我有帮助。

Answer 1

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