Efficient polynomial lengths in Cook TM model
ProvedCritWinSpin.p4c_1_1_ii_effpolycomplexitypolynomial-timeturing-machine
Every univariate polynomial a * d^b + c with natural coefficients has EffPoly length via an explicit polynomial-time one-tape Cook Turing machine.
Preamble
import Mathlib import Definitions.Def_CookPvsNP_defs import Definitions.Def_QuantumPRC_IsPolyFamily open CookPvsNP QuantumPRC set_option autoImplicit false
Formal statement
namespace CritWinSpin theorem p4c_1_1_ii_effpoly : ∀ a b c : ℕ, EffPoly (fun d => a * d ^ b + c) := by sorry end CritWinSpin
Source
CritWinSpin