Ramamohan Paturi

University of California at San Diego

October 12, 2009

We present a gap theorem regarding the complexity of the circuit satisfiability problem.

We prove that the success probability of deciding Circuit Satisfiability for deterministic

circuits with *n* variables and size *m* is either *2 ^{−n}* or

*2*when restricted to probabilistic

^{−o(n)}circuit families

*{C*where the size of C

_{n,m}}_{n,m}is bounded by 2

*.*

^{o(n)}poly(m)