A Satisfiability Algorithm for AC⁰

الأصل · EN

We consider the problem of efficiently enumerating the satisfying assignments to ⁰ circuits. We give a zero-error randomized algorithm which takes an ⁰ circuit as input and constructs a set of restrictions which partition {0,1}ⁿ so that under each restriction the value of the circuit is constant. Let d denote the depth of the circuit and cn denote the number of gates. This algorithm runs in time |C| 2ⁿ⁽¹⁻μᶜ.ᵈ⁾ where |C| is the size of the circuit for μc,d ≥ 1/[c + d d]ᵈ⁻¹ with probability at least 1-2⁻ⁿ. As a result, we get improved exponential time algorithms for ⁰ circuit satisfiability and for counting solutions. In addition, we get an improved bound on the correlation of ⁰ circuits with parity. As an important component of our analysis, we extend the Håstad Switching Lemma to handle multiple and.