Skip to content
  1. CLRS-Lean
  2. Chapter 34. NP-Completeness
  3. 34.4. NP-Completeness Proofs
  4. 34.4. General Acyclic Boolean Circuits
  5. 34.4. General Circuit Satisfiability to SAT
  6. 34.4. General Circuit-to-SAT Reduction Machine
  7. 34.4. Guarded Circuit Work Encoding
Browse chapters
Imports
import CLRSLean.Chapter_34.Section_34_4_NP_Completeness_Proofs.GeneralCircuit.ToSAT.Machine.InternalEncoding.Basic import CLRSLean.Chapter_34.Section_34_4_NP_Completeness_Proofs.GeneralCircuit.ToSAT.Machine.InternalEncoding.Parser import CLRSLean.Chapter_34.Section_34_4_NP_Completeness_Proofs.GeneralCircuit.ToSAT.Machine.InternalEncoding.RoundTrip import CLRSLean.Chapter_34.Section_34_4_NP_Completeness_Proofs.GeneralCircuit.ToSAT.Machine.InternalEncoding.Length

Internal encoding for the concrete general-circuit-to-SAT machine

This facade exports the guarded finite alphabet, its complete parser, exact round-trip theorems, and the quadratic size bounds used by the later TM2 controllers.