0
$\begingroup$

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..

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Nov 23 '18 at 2:39
0
$\begingroup$

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.?

$\endgroup$
  • $\begingroup$ This doesn't appear to be an answer to the question; it appears to be an attempt to engage in an interactive discussion with Yuval Filmus. We have strict quality standards on this site. Please reserve the 'Your Answer' box for material that directly answers the question. Don't use it to ask new questions or solicit further discussion. $\endgroup$ – D.W. Apr 23 at 5:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.