Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > BOOLEAN FORMULA:
Reports tagged with boolean formula:
TR15-099 | 12th June 2015
Ruiwen Chen

#### Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases

We give a \#SAT algorithm for boolean formulas over arbitrary finite bases. Let $B_k$ be the basis composed of all boolean functions on at most $k$ inputs. For $B_k$-formulas on $n$ inputs of size $cn$, our algorithm runs in time $2^{n(1-\delta_{c,k})}$ for $\delta_{c,k} = c^{-O(c^2k2^k)}$. We also show the average-case ... more >>>

ISSN 1433-8092 | Imprint