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