[Rule] CircuitSAT to Satisfiability #970
Description
Source: CircuitSAT
Target: Satisfiability
Motivation: CircuitSAT currently has no reduction path into the main SAT branch. Adding CircuitSAT → Satisfiability via the Tseitin transformation connects it to the existing SAT neighborhood (which already reaches MaximumIndependentSet, KColoring, KSatisfiability, MinimumDominatingSet, etc.) and complements the existing reverse rule Satisfiability → CircuitSAT.
Reference: Tseitin, G. S. (1968). "On the complexity of derivation in propositional calculus." Studies in Mathematics and Mathematical Logic, Part II, pp. 115–125; Cook (1971); Garey & Johnson, LO1.
GJ Source Entry
[LO1] SATISFIABILITY
INSTANCE: Set U of variables, collection C of clauses over U.
QUESTION: Is there a satisfying truth assignment for C?
Reference: [Cook, 1971]. The original NP-completeness proof.
The Tseitin transformation is the standard polynomial-time circuit-to-CNF conversion underlying Cook's theorem and all modern SAT solvers.
Reduction Algorithm
Given a CircuitSAT instance (circuit with assignments of the form o₁, ..., oₘ = e), construct a Satisfiability instance as follows.
Step 1 — Preprocess. For every assignment, simplify constant subexpressions and rewrite n-ary AND, OR, XOR as balanced binary trees. For each non-leaf subexpression occurrence α, introduce a fresh SAT variable v_α. Original circuit variables are reused directly as SAT variables.
Step 2 — Gate-definition clauses (Tseitin encoding). For each subexpression variable v_α:
| Gate | Clauses | Count |
|---|---|---|
| v_α = NOT a | (¬v_α ∨ ¬a), (v_α ∨ a) | 2 clauses, 4 literals |
| v_α = a AND b | (¬v_α ∨ a), (¬v_α ∨ b), (v_α ∨ ¬a ∨ ¬b) | 3 clauses, 7 literals |
| v_α = a OR b | (v_α ∨ ¬a), (v_α ∨ ¬b), (¬v_α ∨ a ∨ b) | 3 clauses, 7 literals |
| v_α = a XOR b | (¬a ∨ ¬b ∨ ¬v_α), (a ∨ b ∨ ¬v_α), (a ∨ ¬b ∨ v_α), (¬a ∨ b ∨ v_α) | 4 clauses, 12 literals |
These clauses force v_α = α for any satisfying assignment.
Step 3 — Output-equivalence clauses. Let z_e be the SAT variable for the root of right-hand side e. For each output oᵢ in assignment o₁,...,oₘ = e, add equivalence clauses:
- (¬oᵢ ∨ z_e), (oᵢ ∨ ¬z_e)
If a right-hand side simplifies to a constant: o = true becomes unit clause (o); o = false becomes (¬o).
Step 4 — Assemble. The target Satisfiability instance uses all original circuit variables + all fresh gate variables as SAT variables, and all clauses from Steps 2–3.
Solution extraction: Restrict the SAT assignment to the original circuit input variables. Discard Tseitin gate variables.
Correctness
(Forward) A satisfying circuit assignment uniquely determines every Tseitin variable (each equals its subexpression value), satisfying all gate-definition and output-equivalence clauses.
(Backward) Gate-definition clauses force each fresh variable to equal its subexpression value; output-equivalence clauses force each declared output to match. Restricting to original variables yields a valid circuit solution.
Size Overhead
| Target metric (code name) | Expression |
|---|---|
num_vars |
num_variables + num_assignments |
num_clauses |
3 * num_assignments + num_variables |
Note: num_assignments in CircuitSAT bounds the number of gates after flattening. The exact clause count depends on gate composition (2 per NOT, 3 per AND/OR, 4 per XOR, 2 per output binding), all of which are O(num_assignments). The overhead expressions are safe upper bounds.
Example
Source circuit (CircuitSAT):
r = (x1 AND x2) OR (NOT x3 AND x4)
4 input variables (x1, x2, x3, x4), 1 output (r), 4 binary gates after flattening.
Preprocessing — fresh gate variables:
- a = x1 AND x2
- b = NOT x3
- c = b AND x4
- d = a OR c
SAT variables: x1, x2, x3, x4, r, a, b, c, d — 9 total (5 original + 4 fresh).
Tseitin clauses (Step 2):
| Gate | Clauses |
|---|---|
| a = x1 AND x2 | (¬a ∨ x1), (¬a ∨ x2), (a ∨ ¬x1 ∨ ¬x2) |
| b = NOT x3 | (¬b ∨ ¬x3), (b ∨ x3) |
| c = b AND x4 | (¬c ∨ b), (¬c ∨ x4), (c ∨ ¬b ∨ ¬x4) |
| d = a OR c | (d ∨ ¬a), (d ∨ ¬c), (¬d ∨ a ∨ c) |
Output-equivalence clause (Step 3): r ↔ d: (¬r ∨ d), (r ∨ ¬d)
Total: 9 variables, 12 clauses.
Satisfying assignment: x1=1, x2=1, x3=0, x4=1 → a=1, b=1, c=1, d=1, r=1.
All 12 clauses verified satisfied. Restricting: x1=1, x2=1, x3=0, x4=1, r=1.
Unsatisfiable circuit: r = x AND (NOT x). Tseitin yields clauses (¬a ∨ x), (¬a ∨ ¬x), (a ∨ ...) plus (r) unit clause. Clause (¬a ∨ x) and (¬a ∨ ¬x) force a=0, but output requires r=a=1 — contradiction, correctly unsatisfiable.
Validation Method
- Closed-loop test: reduce CircuitSAT to Satisfiability, solve SAT with brute force, extract assignment on original circuit variables, verify all source circuit assignments are satisfied
- Test cases: single NOT gate, nested AND/OR, XOR gate, multiple chained assignments, unsatisfiable circuit (x AND NOT x)
- Cross-check generated clause counts against the structural formulas
References
- Tseitin, G. S. (1968). "On the complexity of derivation in propositional calculus." Studies in Mathematics and Mathematical Logic, Part II, pp. 115–125.
- Cook, S. A. (1971). "The Complexity of Theorem Proving Procedures." STOC, pp. 151–158.
- Manolios, P. and Vroon, D. (2007). "Efficient Circuit to CNF Conversion." SAT 2007, LNCS 4501, pp. 4–9.