# Sat instance size and definition of TIME(f(n))

Sat usually is defined as the language of a 'reasonable' encoding of satisfable Cnf formulas over n variables.

Question: a Cnf formula over n variable with m clauses has a size (as a function of n) that can be exponential. Let N be the size of an instance of Sat. So N is in O(n+m) and if m is not polynomial in n it's size is exponential in n. If all of the above is correct, an algorithm that test all 2^n possible values of the variable and test for each of them the O(2^n) clauses is an O(N) algorithm so Sat is in P.

Ok. Something is wrong, but I don't understand why. Moreover since most of the functions over {0,1}^n require a formula of size O(2^n/n) I assume that most of the formula requires m to be exponential in n.

Please if someone could point me in why this is not the case..

• The running time of an algorithm is measured as a function of input size. The input size could be exponential in the number of variables, but it could also be much smaller. A SAT algorithm has to work on all instances. Its running time is measured in the worst case. The $2^n$ algorithm would only be polynomial if the number of clauses is exponential; but this doesn’t have to be the case. – Yuval Filmus Nov 23 '18 at 2:39

Thanks Yuval Filmus, ok, so for each $$N$$, the set of Instances of SAT of size $$N$$, could be exponential in $$n$$, but this is not the worst case, since the real problem happens to be when $$m$$ is polinomially related to $$n$$. Perfect, but, for the Theorem of Shannon of 1979 allmost all boolean functions requires a circuit of size at least $$O(2^n/n)$$ and so a formula of size at least the same order. So, for big $$n$$ I expect SAT easy not only on average, but as the Theorem states 'allmost all'. I understand now better why it is so interesting to catch hard SAT instances when $$n$$ grows. The connection between Shannon Theorem and the complexity of SAT have ever been explored.?