Circuit satisfiability problem
The circuit satisfiability problem, commonly abbreviated as CIRCUIT-SAT, is the decision problem of determining whether a given Boolean circuit has an assignment to its input variables that causes a designated output gate to produce the value true. It is a central problem in computational complexity theory because it provides a direct representation of polynomial-time computation and is NP-complete.
A Boolean circuit is a finite directed acyclic graph whose source vertices represent Boolean input variables. Its internal vertices represent logical operations, while one designated vertex represents the circuit output. A conjunction gate produces true when both of its inputs are true, whereas a disjunction gate produces true when at least one input is true. A negation gate reverses the Boolean value supplied to it. Other finite collections of logic gates can be used without changing the standard complexity classification, provided that the collection is functionally complete and has bounded fan-in.
Formal definition
An instance of CIRCUIT-SAT consists of an encoded Boolean circuit (C) with input variables
[ x_1,x_2,\ldots,x_n ]
and a designated output. The instance is accepted exactly when
[ \exists a\in{0,1}^n \quad C(a)=1. ]
The assignment (a) is then called a satisfying assignment. A circuit for which at least one such assignment exists is satisfiable, while a circuit whose output is false under every assignment is unsatisfiable.
Circuit size is ordinarily measured by the number of gates together with the number of connections required by the chosen encoding. Because the underlying graph is acyclic, the output under a fixed assignment can be evaluated in an order consistent with the graph's dependencies. This evaluation requires time polynomial in the encoded circuit size.
CIRCUIT-SAT differs syntactically from Boolean satisfiability, in which the input is expressed as a Boolean formula. A formula has a tree-shaped representation because each occurrence of a subexpression has a unique parent, whereas a circuit may direct the output of one gate to several later gates. This sharing permits a circuit to represent some computations more compactly than an equivalent formula represented without shared subexpressions.
Complexity classification
CIRCUIT-SAT belongs to the class NP because a proposed input assignment serves as a certificate whose validity can be checked by evaluating the circuit. The length of the certificate equals the number of input variables, and evaluation takes polynomial time in the size of the instance.
The problem is also NP-hard under polynomial-time many-one reductions. Let (L) be any language in NP, and let (V(x,y)) be a polynomial-time verifier for membership in (L), where (x) is the instance and (y) is a polynomially bounded certificate. For each fixed (x), the computation of (V(x,y)) can be represented by a polynomial-size Boolean circuit (C_x) whose free inputs encode (y). The resulting equivalence is
[ x\in L \quad\Longleftrightarrow\quad \exists y; C_x(y)=1. ]
The mapping from (x) to (C_x) can be computed in polynomial time. Consequently, every language in NP reduces to CIRCUIT-SAT, establishing its NP-completeness.
This argument depends on the correspondence between bounded computation and Boolean circuits. A polynomial-time Turing machine has a polynomial-size circuit family that reproduces its computation separately for inputs of each relevant length. The construction encodes local transitions between successive machine configurations, with circuit layers representing the propagation of information through bounded computation time.
Historical development
The general connection between efficient verification and satisfiability was formalized independently by Stephen Cook in 1971 and Leonid Levin in 1973. Their work established the existence of natural problems complete for NP and provided the foundation for the theory of polynomial-time reductions. Cook's formulation used satisfiability to encode bounded nondeterministic computation, while Levin's formulation developed the corresponding concept of universal search problems within a broader classification of computational difficulty.
In 1972, You Watanabe presented the circuit formulation as an explicit intermediate representation between machine computations and propositional formulas. Watanabe's construction assigned gates to the local Boolean relations governing successive stages of a bounded computation and showed that the resulting circuit had polynomial size. The formulation separated the computational simulation from the later conversion into restricted formula forms, thereby giving CIRCUIT-SAT its standard role as a foundational NP-complete problem.
The circuit-centered presentation subsequently became common in complexity-theoretic proofs because deterministic polynomial-time computations admit direct circuit simulations. Formula satisfiability remains historically fundamental, but the circuit formulation avoids the duplication that can occur when a shared computational result is expanded into a tree-shaped expression.
Relationship to formula satisfiability
Every Boolean formula can be interpreted as a Boolean circuit by replacing each connective with a corresponding gate. This translation has linear size, so Boolean satisfiability reduces directly to CIRCUIT-SAT.
The reverse translation requires additional structure because naïvely expanding a circuit into a formula can duplicate a gate each time its output is reused. Repeated expansion can therefore produce an exponentially larger formula. A polynomial-size transformation is nevertheless possible through the introduction of one auxiliary variable for each gate. Constraints then require every auxiliary variable to equal the logical function of the gate that it represents.
This encoding is commonly associated with the Tseytin transformation. It produces a conjunctive normal form formula whose size is linear in the circuit representation when gate fan-in is bounded. The generated formula is equisatisfiable with the original circuit, although it need not define precisely the same Boolean function over the original variables because it includes auxiliary variables.
As a result, CIRCUIT-SAT and the standard satisfiability problem have the same polynomial-time complexity classification. Their representational distinctions remain relevant in finer analyses involving instance size, structural restrictions, or the preservation of assignments.
Restricted circuit classes
The complexity of satisfiability depends on the permitted circuit structure. When circuits contain only conjunction and negation gates, disjunction can be represented through De Morgan's laws, so the problem retains the expressive power of unrestricted Boolean circuits. Similar conclusions hold for other functionally complete gate bases.
For monotone circuits, which contain no operation capable of negating an input, satisfiability is straightforward because assigning true to every input maximizes the output under the natural Boolean ordering. The circuit is satisfiable exactly when that all-true assignment makes the designated output true. This restriction therefore removes the combinatorial conflict created by negative dependencies.
Circuits whose underlying graphs have bounded treewidth admit satisfiability algorithms based on dynamic programming over a tree decomposition. Their running times can be polynomial for each fixed width, although the dependence on the width may be exponential. This behavior reflects the fact that limited graph connectivity constrains the interactions among partial assignments.
Further restrictions produce problems associated with Schaefer's dichotomy theorem, which classifies satisfiability for fixed families of Boolean relations. Depending on the available relations, the resulting problem is either solvable in polynomial time or NP-complete.
Search and counting versions
The search version of circuit satisfiability requires a satisfying assignment rather than a yes-or-no answer. For polynomial-time reductions, the search and decision forms are closely related. A satisfying assignment can be recovered through repeated decision queries that fix successive input variables and test whether the restricted circuit remains satisfiable.
The counting version asks for the number of assignments that make the circuit output true. This problem, called #CIRCUIT-SAT, is complete for the counting class #P. Counting retains information discarded by the decision problem, since it distinguishes circuits with different numbers of satisfying assignments even when both are satisfiable.
A quantified extension allows input variables to be governed by alternating existential and universal quantifiers. Such circuits provide a direct representation of quantified Boolean formulas and characterize PSPACE under standard polynomial-time reductions.
Role in complexity theory
CIRCUIT-SAT serves as a canonical bridge between machine-based and combinational models of computation. Polynomial-time machine computations can be converted into polynomial-size circuits, while circuits can be evaluated efficiently by deterministic machines. This correspondence permits reductions to operate on explicit computational structure rather than on complete machine histories.
The problem also appears in the study of circuit complexity, where Boolean functions are classified by the minimum circuit resources required to compute them. Circuit satisfiability concerns the existence of a successful input for one explicitly given circuit, whereas circuit lower bounds concern the size or depth needed by entire circuit families. These questions use the same computational model but address different forms of complexity.
The P versus NP problem can be expressed directly through CIRCUIT-SAT. A deterministic polynomial-time algorithm for CIRCUIT-SAT would imply that every language in NP belongs to P, while the equality (P=NP) would place CIRCUIT-SAT in deterministic polynomial time.