Proof of `Two-Satisfiability` (2nd statement)
groundedproofs/Lax117284Proofs/TwoSatBridge.lean · lax-117284
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.
Description
The formulas of this submission reduce to the 2-SAT of by renaming: the variable of every literal is replaced by the position of the first occurrence of that variable, so that the unary code of stays polynomial in the binary code of this submission, and renaming along an injection preserves satisfiability in both directions. A word that is not the code of a formula is sent to the code of a formula with one empty clause, which is unsatisfiable. The reduction is a word RAM program on the zeros and ones of its input, in the same way as the reductions of the theorems, and transfers to a Turing machine; 2-SAT of is in polynomial time by the algorithm of this submission, and polynomial time is closed under polynomial-time reductions.