CSDM - On The Complexity of Circuit Satisfiability

On The Complexity of Circuit Satisfiability - Ramamohan Paturi

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−o(n) when restricted to probabilistic
circuit families {Cn,m} where the size of Cn,m is bounded by 2o(n)poly(m).