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

groundedproofs/Lax345332Proofs/Final.lean · lax-345332

What this proof establishes

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 4 of this submission's paper

Description

The reduction is a word RAM program on the zeros and ones of its input: a finite-state scan decodes the formula into arrays of literal indices, signs and clause numbers; one pass tabulates where each clause ends; the chain clauses are then written clause by clause and the cycle clauses position by position, each with its padding and its three gadgets, in the encoding's unary code. Polynomial time on the word RAM transfers to a Turing machine.