在计算复杂度理论中,如果解决输入大小为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 的回答。
更新:
我在这里做了同样的问题:
https://cstheory.stackexchange.com/questions/18756/whats-the-meaning-of-input-size-for-3-sat
接受的答案对我有帮助。