Name
Abstract | ||
|---|---|---|
We give a deterministic #SAT algorithm for de Morgan formulas of size up to $$n^{2.63}$$n2.63, which runs in time $$2^{n-n^{{\\varOmega }(1)}}$$2n-nΩ(1). This improves upon the deterministic #SAT algorithm of Chen et al. (Proceedings of the twenty-ninth annual IEEE conference on computational complexity, 2014), which has similar running time but works only for formulas of size less than $$n^{2.5}$$n2.5. Our new algorithm is based on the shrinkage of de Morgan formulas under random restrictions, shown by Paterson and Zwick (Random Struct Algorithms 4(2):135---150, 1993). 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 given deterministic polynomial-time formula-simplification algorithm. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/s00453-015-0020-z | Algorithmica |
Keywords | DocType | Volume |
de Morgan formulas,Random restrictions,Shrinkage exponent,Concentrated shrinkage,Algorithms from circuit lower bounds,Deterministic #SAT algorithms | Journal | 76.0 |
Issue | ISSN | Citations |
1 | 0178-4617 | 2 |
PageRank | References | Authors |
0.36 | 14 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ruiwen Chen | 1 | 35 | 4.97 |
| Valentine Kabanets | 2 | 562 | 35.38 |
| Nitin Saurabh | 3 | 5 | 3.81 |