In this paper, we are concerned with the exponential complexity of the Circuit Satisfiability (CktSat) problem. Our main technique is a a success probability amplification technique, called the Exponential Amplification Lemma, which shows that for any f(n,m)-size bounded probabilistic circuit family A that decides CktSat with success probability at least 2-\alpha n for \alpha less than 1 on inputs which are circuits of size m with n variables, there is another probabilistic circuit family B that decides CktSat with size roughly f(\alpha n,f(n,m)) and success probability about 2-\alpha^2n > 2-\alpha n. In contrast, the standard method for boosting success probability by repeated trials will improve it to (1-(1-2-\alpha n)t) (\approx t2-\alpha n for t = O(2\alpha n)) using circuits of size about tf(n,m).

Using this lemma, we derive tight bounds on the exponent of the success probability for deciding the CktSat problem in a variety of probabilistic computational models under complexity assumptions. For example, we show that the success probability cannot be better than 2-n+o(n) for deciding CktSat by probabilistic polynomial size circuits unless CktSat (thereby all of NP) for polynomial size instances can be decided by 2n\mu size deterministic circuits for some \mu less than 1, which is considered an unlikely event. As another example, we show that probabilistic quasilinear size circuits cannot achieve success probability better than 2-n+o(n) unless CktSat (as well as NP) has O(mO(lg lg m)) size deterministic circuits, which is very close to the statement NP \subseteq P/poly, an unlikely scenario.

Jointly with Pavel Pudlak, Institute of Mathematics, Academy of Sciences of the Czech Republic.