🧩 Constraint Solving POTD:Problem of the Day: Circuit Satisfiability (CSAT)

[github-actions[bot]]

Problem Statement

Circuit Satisfiability asks: given a combinatorial digital circuit with boolean gates (AND, OR, NOT, XOR) and primary inputs, can we find an assignment of input values such that the circuit outputs true?

Concrete Instance

Consider a small circuit with 3 inputs (a, b, c) and the following logic:

• x = a AND b
• y = NOT c
• output = x OR y

Question: Is there an input assignment that makes output = true?

Answer: Yes. For example, a = true, b = true, c = true yields x = true, y = false, output = true.

Input/Output Specification

• Input: A combinatorial logic circuit (acyclic) represented as gates and connections
• Output: Either a satisfying assignment (inputs that make the circuit output true) or UNSAT (no such assignment exists)

---

Why It Matters

Circuit Satisfiability is the foundation of formal hardware verification. Design engineers use SAT solvers to check correctness properties before silicon hits the fab—catching bugs worth millions of dollars. This problem also connects classical SAT to real circuit design through gate-level synthesis, security vulnerabilities (hardware trojans), and equivalence checking between two circuit designs.

In cryptography and security, CSAT helps identify whether a circuit implementation is secure against certain attacks. In compiler optimization, it powers peephole optimizations that verify code transformations preserve semantics.

---

Modeling Approaches

Approach 1: Direct Boolean Satisfiability (SAT Encoding)

Represent each gate as a clause. For an AND gate z = x AND y, enforce three clauses in Conjunctive Normal Form (CNF):

• (¬x ∨ ¬y ∨ z) — if x and y are both true, z must be true
• (x ∨ ¬z) — if z is false, x must be false
• (y ∨ ¬z) — if z is false, y must be false

Decision Variables: Boolean variable per gate and input.

Propagation: Modern SAT solvers (DPLL with conflict-driven clause learning) use unit propagation and learned clauses to prune the search space exponentially.

Trade-offs:

• ✅ Highly optimized solvers (MiniSat, Lingeling, CaDiCaL) available
• ✅ Explosive propagation on structured problems
• ❌ CNF translation can expand the formula (auxiliary variables needed)
• ❌ Pure CNF loses gate structure information

---

Approach 2: Constraint Programming with Reification

Model gates as global constraints with reification. For AND:

• reified_and(x, y, z) ← a constraint encapsulating z ↔ (x AND y)

Use constraint propagation to enforce bounds on gate outputs based on input domains.

Decision Variables: Domain variables per gate (initially {0, 1})

Propagation: Arc consistency (AC) and specialized global constraint propagators eliminate inconsistent values more efficiently than clause unit propagation in some cases.

Trade-offs:

• ✅ Preserves gate semantics; easier to extend with custom constraints
• ✅ Stronger domain-level propagation on mixed problems
• ❌ General CP is slower on pure propositional circuits than specialized SAT
• ❌ Fewer industrial-strength solvers optimized for this encoding

---

Example SAT Model (DIMACS CNF Format)

For the circuit output = (a AND b) OR (NOT c):

c Example: (a AND b) OR (NOT c)
c Variables: 1=a, 2=b, 3=c, 4=x (a AND b), 5=y (NOT c), 6=output
p cnf 6 8
c x = a AND b
1 -4 0      c a ∨ ¬x
2 -4 0      c b ∨ ¬x
4 -1 -2 0   c x ∨ ¬a ∨ ¬b
c y = NOT c
-3 -5 0     c ¬c ∨ ¬y
3 5 0       c c ∨ y
c output = x OR y
4 5 -6 0    c x ∨ y ∨ ¬output
-4 6 0      c ¬x ∨ output
-5 6 0      c ¬y ∨ output

A SAT solver would find an assignment like {a=1, b=1, c=1, x=1, y=0, output=1}.

---

Key Techniques

1. Conflict-Driven Clause Learning (CDCL)

Modern SAT solvers don't just fail and backtrack—they learn from conflicts. When a partial assignment leads to a contradiction, the solver derives a learned clause that prevents exploring similar dead ends. This exponential speedup is why modern SAT solvers solve circuits with millions of gates.

2. Circuit-Aware Heuristics

Some SAT solvers (e.g., MiniSat variants for hardware) exploit circuit structure:

• Topological ordering: Prioritize variables by gate dependencies (fanout, fan-in)
• Decision heuristics: Assign inputs before internal gates (variable-state independent decaying sum, VSIDS)
• Pure literals: If a variable appears only in one polarity, assign it immediately

3. Symmetry & Structural Redundancy Detection

Circuits often have symmetries (e.g., identical sub-circuits). Preprocessing tools detect and break symmetries, or solvers exploit them to prune symmetric search branches. This can reduce search space by orders of magnitude.

---

Challenge Corner

🧠 Open Questions for You:

1. Optimization: Can you model circuit satisfiability with fewer boolean variables than the number of gates? (Hint: think about which internal gate outputs you actually need to represent.)

2. Incremental Verification: Suppose you have a large circuit and you want to check satisfiability for many different output constraints (e.g., "make output_A true," then "make output_B true"). How would you reuse the SAT solver state between queries?

3. Synthesis Dual: CSAT checks if a circuit can produce a given output. The dual problem is circuit synthesis: given a specification, generate a circuit that satisfies it. How might you use a CSAT solver to drive circuit synthesis?

---

References

1. Handbook of Satisfiability (2nd ed., 2021)
   Biere, Heule, van Maaren, Walsh (eds.) — Chapter on SAT techniques and industrial applications. (www.bookdepository.com/redacted)

2. Using SAT Solvers for Verification
   Kroening & Strichman (2016) — "Decision Procedures: An Algorithmic Point of View." Excellent on connecting SAT to hardware verification and formal methods.

3. ABC Hardware Synthesis Tool
   Berkeley Logic Synthesis (BLSS) — Practical open-source tool using SAT-based circuit optimization and verification. See ABC tutorial at https://github.com/berkeley-abc/abc

4. Recent Advances in SAT Solvers
   SAT Competition archives ((www.satcompetition.org/redacted) — Real benchmarks from circuit verification, cryptanalysis, and formal methods. Great source for learning what problems push SAT solvers to their limits.

---

Next time: Share your insights on the challenge corner questions in the discussion comments!

Generated by 🧩 Constraint Solving — Problem of the Day · 8.58 AIC · ⌖ 15.3 AIC · ⊞ 5.8K · ◷

• expires on Jul 1, 2026, 4:15 AM UTC-08:00

[github-actions[bot]]

This discussion has been marked as outdated by Constraint Solving — Problem of the Day.

A newer discussion is available at Discussion #41423.