Propositional Logic Time complexity

If i have a propositional logic formula, every time i add a variable the number of interpretation grow up by 2.

So if i have a propositional formula with 3 variables i have 8 interpretations.

So, is the time complexity of the SAT problem of propositional logic a $O(2^{x})$ ?

Your question hints at multiple misconceptions which I'm going to address.


If i have a propositional logic formula, every time i add a variable the number of interpretation grow up by 2.

First, let's be clear about terminology.

• variable vs literal -- the formula $a \lor b \land a$ has three literals but two variables.

• model vs interpretation -- every logical formula has exactly one of two possible interpretations, true and false.

It would be correct to say: the number of models grows exponentially (with base 2) in the number of variables.


So, is the time complexity of the SAT problem of propositional logic a $O(2^x)$?

No, that does not follow.

• What is $x$? In complexity theory, we usually express complexity in the input length. So if $x$ is the number of literals, that thought makes sense; if it's the number of variables, it does not. However, in the worst cases (if we consider search space alone), the number of variables and literals is the same.

• The number of possible models (e.g. valuations of the variables) alone is not trivially an upper bound on the complexity. The brute-force algorithm also has to evaluate the formula for every candidate, so you have to add a linear factor at least (depends on the computational model and cost model you use).

-
When somebody says, "the complexity is X" that implies a lower bound in addition to an upper bound. Your observation does not provide a lower bound, even after correction.

That is because the size of the search space does not correlate with solving complexity. Take sorting, for instance: finding the correct permutation has a search space of size $n!$ and yet we can solve the problem in linearithmic time. SSSPP is another common example.

StackExchange Computer Science Q#88755, answer score: 5