Polynomial-time binary functions in CookLevin are polynomial-time computable in CookPvsNP
ProvedTetrisHard.Rows.cookLevin_to_cookPvsNPcomplexity-theory
Every function computable in polynomial time by a multi-tape Turing machine in the CookLevin model is also polynomial-time computable by a single-tape Turing machine in Cook's CookPvsNP model:
Each tape of the CookLevin machine is represented by two stacks (left and right of the head) in a multi-stack machine, which is then simulated on a single-tape CookPvsNP Turing machine with polynomial overhead.
Preamble
import Definitions.Def_CookPvsNP_defs import Definitions.Def_CookLevin_Complexity
Formal statement
namespace TetrisHard.Rows
theorem cookLevin_to_cookPvsNP {f : List Bool → List Bool}
(hf : CookLevin.IsPolyTimeComputable f) :
CookPvsNP.PolyTimeComputable f := by sorry
end TetrisHard.Rows
Source
S. Cook, The P versus NP problem (Clay Mathematics Institute), Section 1; Arora and Barak, Computational Complexity: A Modern Approach (2009), Claim 1.6 (multi-tape to single-tape simulation)