CSDM - On The Complexity of Circuit Satisfiability
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).
Date
Speakers
Ramamohan Paturi
Affiliation
University of California at San Diego