Tseytin transformation
Jump to navigation
Jump to search
English
[edit]Alternative forms
[edit]Etymology
[edit]Named after G. S. Tseytin.
Proper noun
[edit]- A transformation that, given an arbitrary combinatorial logic circuit, produces an equisatisfiable Boolean formula in conjunctive normal form, the length of the formula being linear in the size of the circuit.