## An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas

#### Ruiwen Chen, Valentine Kabanets, and Nitin Saurabh

### Abstract

We give a deterministic #SAT algorithm for de Morgan formulas of size up to $n^{2.63}$, which runs in time $2^{n-n^{\Omega(1)}}$. This improves
upon the deterministic #SAT algorithm of Chen *et al.*, which has similar running time but works only for formulas of size less than $n^{2.5}$.

Our new algorithm is based on the shrinkage of de Morgan formulas under random restrictions, shown by Paterson and Zwick.
We prove a *concentrated* and *constructive* version of their shrinkage result. Namely, we give a deterministic polynomial-time algorithm that selects
variables in a given de Morgan formula so that, *with high probability* over the random assignments to the chosen variables, the original formula shrinks in size, when simplified
using a *deterministic polynomial-time* formula-simplification algorithm.

### Versions

- journal version
*Algorithmica*, 2015. -
extended abstract in
*Proceedings of the Thirty-Ninth International Symposium on Mathematical Foundations of Computer Science (MFCS'14),*pages 165-176, 2014. -
preliminary version in
*Electronic Colloquium on Computational Complexity*ECCC-TR13-150.