Circuit Satisfiability¶
The existence of an external Boolean input valuation that drives a finite acyclic gate circuit's designated output to true.
Core Idea¶
Circuit satisfiability asks whether any external input assignment makes a finite acyclic Boolean gate circuit's designated output true. The circuit stays fixed; internal wires obey its gates. One successful input proves yes. No successful input means no, without requiring a solver or witness as part of the question.[ref-0f715c5b1c1f][ref-f44f45620f13]
Scope of Application¶
- Verifier circuit. For a fixed problem instance, satisfiability asks whether some candidate witness is accepted.[^ref-0f715c5b1c1f]
- Combinational hardware miter. A difference circuit asks whether two designs disagree on any common input; a yes verdict establishes that an inequivalence witness exists.[^ref-7036b3e94ff9]
Both use the same external-input existence test. Formula-shaped circuits are included, while shared gate graphs need not be formulas.[^ref-f44f45620f13]
Clarity¶
A failed input rules out only that input. An unsatisfiability proof rules out every input. A gate-variable translation to a formula must constrain internal variables to follow the gates, or it can produce a false witness.[^ref-0f715c5b1c1f] A yes answer for a miter means disagreement; whether that is desirable depends on the application.[^ref-7036b3e94ff9]
Manages Complexity¶
Keep five roles separate: acyclic gate circuit, variable external inputs, gate-consistent evaluation, designated Boolean output, and existential yes/no verdict. Gate basis, fan-out and solving method may vary. A CNF encoding translates the question; a solver answers it. Neither defines it.[ref-0f715c5b1c1f][ref-f44f45620f13]
Abstract Reasoning¶
Identify the circuit's input bits and output gate. Check finite Boolean acyclic structure, then ask whether a coherent evaluation under some external input yields one. A witness proves yes; several failed attempts do not prove no. A formula encoding or miter must preserve that existence condition.[ref-0f715c5b1c1f][ref-7036b3e94ff9]
Knowledge Transfer¶
The verifier and miter cases instantiate a total Boolean-valued Function (Mapping) from well-formed circuit descriptions to existence verdicts. Output one means acceptance in the first case and disagreement in the second. The gate circuit and external-input quantifier remain essential; general feasibility without them is a neighboring idea.[ref-0f715c5b1c1f][ref-7036b3e94ff9]
Relationships to Other Abstractions¶
Current abstraction Circuit Satisfiability Domain-specific
Parents (1) — more general patterns this builds on
-
Circuit Satisfiability is a kind of Function (Mapping) Prime
Circuit satisfiability is the Boolean-valued mapping on well-formed acyclic gate-circuit descriptions that tests for any external input producing output one.
Hierarchy path (1) — routes to 1 parentless root
- Circuit Satisfiability → Function (Mapping)
Neighborhood in Abstraction Space¶
Circuit Satisfiability sits in a sparse region of the domain-specific corpus (65th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Computational Complexity & Hardness (18 abstractions)
Nearest neighbors
- Comparator-circuit complexity class CC — 0.87
- NOR logic — 0.86
- Logical NOR — 0.84
- Boolean circuit — 0.84
- Deferred Measurement Principle — 0.83
Computed from structural-signature embeddings · 2026-10-17
References¶
[^ref-0f715c5b1c1f]: Anup Rao. Lecture 8 (NP-complete programs). CSE 431, University of Washington, January 26, 2023. One-based PDF p. 1, Definition 1 and Theorem 3; p. 2, formula fan-out definition; p. 3, Theorem 5 gate-variable CNF construction. Full teaching text inspected; not an original Cook/Levin research paper.
[^ref-7036b3e94ff9]: Satrajit Chatterjee, Alan Mishchenko, Robert Brayton, and Andreas Kuehlmann. On Resolution Proofs for Combinational Equivalence. Proceedings of the 44th Design Automation Conference (DAC), 2007, pp. 600–605. Printed pp. 600–601 / one-based PDF pp. 1–2, abstract, Figure 1 and §§2.1–2.4. Full original author-hosted text inspected; the figure is a documented example, not an observed production trace.
[^ref-f44f45620f13]: Jason Ku and Yun William Yu. Class 4 Scribe Notes, 6.890. Massachusetts Institute of Technology, September 16, 2014. One-based PDF p. 1, §2, Circuit SAT bullets. Ku and Yu are the notetakers; Erik Demaine is the instructor. Full university-hosted course notes inspected for the acyclic gate-DAG and reuse characterization; the printed 2014 date is used rather than the URL directory's spring19 label.