Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR12-071 | 29th May 2012 10:20

A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis

TR12-071
Authors: Kazuhisa Seto, Suguru Tamaki
Publication: 29th May 2012 15:22
For formulas of size at most $cn$, our algorithm runs in time $2^{(1-\mu_c)n}$ for some constant $\mu_c>0$.