Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > BRUTE FORCE SEARCH:
Reports tagged with brute force search:
TR13-108 | 9th August 2013
Rahul Santhanam, Ryan Williams

New Algorithms for QBF Satisfiability and Implications for Circuit Complexity

Revisions: 1

We revisit the complexity of the satisfiability problem for quantified Boolean formulas. We show that satisfiability
of quantified CNFs of size $\poly(n)$ on $n$ variables with $O(1)$
quantifier blocks can be solved in time $2^{n-n^{\Omega(1)}}$ by zero-error
randomized algorithms. This is the first known improvement over brute force search in ... more >>>




ISSN 1433-8092 | Imprint