<p>It's of the order 2^{0.30897m}, see <a href="http://logic.pdmi.ras.ru/~hirsch/abstracts/sodafull.html">http://logic.pdmi.ras.ru/~hirsch/abstracts/sodafull.html</a></p>

<p>(I am not aware of improvements for the number of clauses.)</p>

CC BY-SA 3.0
2015-10-14T12:19:09.743Z
2015-10-14T12:19:09.743Z
hirsch
<p>What's the best upper bounds based on number of clauses? In <a href="https://cstheory.stackexchange.com/questions/1060/best-upper-bounds-on-sat">this</a> question shown fastest algorithms for SAT, but there bounds depends from number of variables ( $O(const^n)$ where n is number of variables).</p>

<p>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 <a href="http://arxiv.org/abs/1103.2165" rel="nofollow noreferrer">PPSZ for 3-SAT</a> can be bounded by $O(1.496^m)$. But I'm interested in algorithms which bounds "natively" depends from number of clauses.</p>

<cc.complexity-theory><sat><upper-bounds>
Best SAT upper bounds based on number of clauses
Alexey Kholodkov
# Best SAT upper bounds based on number of clauses

(Asked by: username_0 on 2015-09-22)

What's the best upper bounds based on number of clauses? In [this](https://cstheory.stackexchange.com/questions/1060/best-upper-bounds-on-sat) 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](http://arxiv.org/abs/1103.2165) can be bounded by $O(1.496^m)$. But I'm interested in algorithms which bounds "natively" depends from number of clauses.

**Tags:** cc.complexity-theory, sat, upper-bounds


---

## 1 answers

### Answer by username_1 on 2015-10-14. Score: 6 | Accepted answer

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

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


---

