6
$\begingroup$

What's the best upper bounds based on number of clauses? In this question shown fastest algorithms for SAT, but there bounds depends from number of variables ( $O(const^n)$ where n is number of variables).

I know that variables bounds can be converted to clauses bounds. If k-SAT formula contains $m$ clauses then $n \leq \frac{k * m}{2}$, consequently if algorithm bounded by $O(const^n)$, it also bounded by $O(const^ \frac{k * m}{2}) = O((const^ \frac{k}{2})^m)$. In that way PPSZ for 3-SAT can be bounded by $O(1.496^m)$. But I'm interested in algorithms which bounds "natively" depends from number of clauses.

$\endgroup$
1

1 Answer 1

6
$\begingroup$

It's of the order 2^{0.30897m}, see http://logic.pdmi.ras.ru/~hirsch/abstracts/sodafull.html

(I am not aware of improvements for the number of clauses.)

$\endgroup$

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.