Polynomial-time Turing-machine construction of the five-state grid tensor table
ProvedResultantVNP.grid_table_polytimecomplexitycomputabilitypermanentturing-machine
The map from n, encoded in unary, to the bit string gridTableCode n is computable by a finite TM2 Turing machine in time polynomial in n. This is exactly the computational clause of Lemma 3.3. A proof must provide the finite machine, a polynomial time bound, and its output correctness; a bound on the output size alone does not suffice.
Preamble
import Mathlib import Definitions.Def_ResultantVNP_gridTableCode
Formal statement
theorem ResultantVNP.grid_table_polytime :
Nonempty (Turing.TM2ComputableInPolyTime Computability.unaryEncodeNat id ResultantVNP.gridTableCode) := by sorrySource
Bhargav–Curticapean–Jindal–Shukla, Multivariate Resultants: Complexity and Applications to Real Feasibility, STOC 2027 paper #1103, Lemma 3.3 computational clause and Appendix A.1.