-1
$\begingroup$

Hi I understood it is not currently possible to solve SAT in polynomial time. Does this mean we can not currently solve an expression with n different boolean variables or with m different symbols in the expression in polynomial time with respect to n?

For example :

( A or B ) and ( not not A and B )

The different number of boolean variables here n is 2 but the number of symbols m is 13.

Improve this question
$\endgroup$
3
  • $\begingroup$ It is known that the 3-SAT problem is as hard as m-SAT so the expression length is unimportant. $\endgroup$
    – user16034
    May 5 at 11:48
  • $\begingroup$ @Yves Daoust Yeah I am afraid I dont know either of those :), you can stil formulate an answer and I will upvote you. It might help other noobs alike me. $\endgroup$
    – Jip Helsen
    May 5 at 14:32
  • $\begingroup$ This is not an answer, just a comment about $m$. $\endgroup$
    – user16034
    May 5 at 14:52

1 Answer 1

Reset to default
1
$\begingroup$

In general, asymptotic complexity concerns itself with the size of the input. In this case, the number of input symbols. SAT is thus not polynomially solvable in the worst case as a function of the number of symbols.

It is also not polynomially solvable with respect to the number of unique variables. This is trivially so, as this is clearly upper bounded by the size of the input.

However, SAT is tractable in the special case that the number of unique variables is low. That is, it's Fixed Parameter Tractable with respect to that parameter. Indeed, we can try each assignment to the variables (of which there are an exponential amount w.r.t. the number of unique variables) and verify whether they satisfy the whole formula (which is linear in the size of the formula). Thus with $n$ unique variables and $m$ total symbols, SAT is solvable in O($2^n$m).

Improve this answer
$\endgroup$
2
  • $\begingroup$ "SAT is thus not polynomially solvable in the worst case as a function of the number of symbols." Uhm, you know something we don't? $\endgroup$
    – Andrej Bauer
    May 5 at 17:50
  • $\begingroup$ Standard caveats of complexity theory still apply* ;) $\endgroup$
    – ADdV
    May 6 at 9:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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