Certificate-oblivious formula round-trip output machine
ProvedCookLevin.formulaRoundTrip_certificate_oblivious_output_machinepolynomial-timesat-verifierturing-machine
There is a quadratic-time multi-tape Turing machine computing the canonical round-trip encoding of a binary CNF formula. Its halting state and designated output are independent of the certificate input. The statement intentionally does not require the full final tape configuration to be independent of the certificate, since untouched certificate cells may remain different.
Preamble
import Definitions.Def_CookLevin_Verifier
Formal statement
namespace CookLevin
theorem formulaRoundTrip_certificate_oblivious_output_machine :
∃ (M : Machine) (k G c1 : Nat),
TuringMachine k G M ∧
ComputesInTime M k (fun n => c1 * (n + 1) ^ 2)
(fun x => encodeFormula (decodeFormula x)) ∧
∀ x w : List Bool,
(execute M (startConfig2 k (boolsToSymbols x) (boolsToSymbols w))
(c1 * (x.length + 1) ^ 2)).1 = M.length ∧
outputOf k
(execute M (startConfig2 k (boolsToSymbols x) (boolsToSymbols w))
(c1 * (x.length + 1) ^ 2))
(c1 * (x.length + 1) ^ 2 + 2) = encodeFormula (decodeFormula x) := by sorry
end CookLevinSource