On the complexity of circuit satisfiability
Ramamohan Paturi, Pavel Pudlák · 2010
In this paper, we are concerned with the exponential complexity of the Circuit Satisfiability (CktSat) problem and more generally with the exponential complexity of NP-complete problems. Over the past 15 years or so, researchers have obtained a number of exponential-time algorithms with improved running times for exactly solving a variety of NP-complete problems. The improvements are typically in the form of better exponents compared to exhaustive search. Our goal is to develop techniques to prove specific lower bounds on the exponents under plausible complexity assumptions. We consider natural, though restricted, algorithmic paradigms and prove upper bounds on the success probability. Our approach has the advantage of clarifying the relative power of various algorithmic paradigms. Our main technique is 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-α n for α 2-α n.