QBF Satisfiability Algorithms and Connections with Circuit Lower Bounds
summary
Gives a concrete algorithmic tradeoff: for QBF with k quantifier blocks over CNFs or small formulas the procedure achieves savings Ω(n^{1/(k+1)}) by splitting variables, brute forcing a short suffix to produce a depth-(k+2) circuit on n′ = n − n^{1/(k+2)} variables, and using a truth‑table lemma for AC^0 via the switching lemma to precompute values and memoize. Also proves that any uniform Ω(log n) savings independent of k would imply new non‑uniform boolean formula lower bounds (explicit superpolynomial formulas for NX).
AI-written summary · about