Proof of `2-SAT Is in P`
groundedproofs/Lax117284Proofs/TwoSAT/Machine/FinalP.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 program on the length-prefixed word is a polynomial-time word RAM computation of the decision on the zeros and ones of the word, with all values polynomially bounded; the RAM/Turing equivalence of and the two translations of give a polynomial-time Turing machine on the binary word, and a machine writing the one bit of the answer is a machine for the class.