Lax Lean Archive

Proof of `The Reduction from Satisfiability to (3,4)-Satisfiability` (4th statement)

groundedproofs/Lax345332Proofs/Transform.lean · lax-345332

What this proof establishes

no assumptions

def✓Lax345332.Construction (4th statement)

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

In the paper

  • page 3 of this submission's paper

Description

Splitting: an assignment of FF is copied to every position and the link after a literal is set to "no literal so far is true"; conversely the cycle makes all copies of a variable equal, and a chain with all literals false propagates a true link into its last clause. Padding: the gadgets force the padding literals false, and can always be satisfied.