Translation from polynomial-time binary multitape computations to TM2
ProvedTuring.MultiTapeTM.computableInPolyTime_to_tm2complexity-theorysatisfiability
A polynomial-time binary multitape computation has a Mathlib TM2 implementation with the same input and output encoding.
Preamble
import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_PolyTime import Mathlib.Computability.TuringMachine.Computable
Formal statement
open Turing Turing.MultiTapeTM
theorem Turing.MultiTapeTM.computableInPolyTime_to_tm2 {α β : Type} {encIn : α ↪ List Bool}
{encOut : β ↪ List Bool} {f : α → β} (h : ComputableInPolyTime f encIn encOut) :
Nonempty (TM2ComputableInPolyTime encIn encOut f) := by sorrySource
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Lemma 11, Section 3.4.