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

Watch Online
Hi-Res	352.29 MB
Lo-Res	196.44 MB
Slides	337.97 KB