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

$\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, 2023 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, 2023 at 14:32
  • $\begingroup$ This is not an answer, just a comment about $m$. $\endgroup$
    – user16034
    May 5, 2023 at 14:52

1 Answer 1

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

$\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$ May 5, 2023 at 17:50
  • $\begingroup$ Standard caveats of complexity theory still apply* ;) $\endgroup$
    – ADdV
    May 6, 2023 at 9:53

Your Answer

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

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