Skip to content
Browse chapters
Imports

General CIRCUIT-SAT to SAT

Facade for the textbook consistency-formula bridge from the honest general acyclic circuit language to SAT. It exports the semantic equivalence, the total raw encoding map, exact language preservation, and a polynomial output-size bound.

It also exports a concrete fixed multitape Turing machine computing the total map in polynomial time.