Core multi-tape Turing machine for conjunction of polynomial-time relations
ProvedCookLevin.polyTimeDecidable_and_core_machinecomplexitycook-levindecidable
If and are polynomial-time decidable, there exists a multi-tape machine with bound deciding .
Formal statement
import Definitions.Def_CookLevin_Basic
import Definitions.Def_CookLevin_Satisfiability
import Definitions.Def_CookLevin_Complexity
import Definitions.Def_CookLevin_Verifier
open CookLevin
theorem CookLevin.polyTimeDecidable_and_core_machine (f g : List Bool → List Bool → Bool)
(hf : PolyTimeDecidable f) (hg : PolyTimeDecidable g) :
∃ M k G c d, TuringMachine k G M ∧ ∀ x w : List Bool, DecidesIn M k (boolsToSymbols x) (boolsToSymbols w) (polyBound c d (x.length + w.length)) (f x w && g x w) := by sorrySource