Polynomial-time implementation of the integer interpolation program
ProvedCountOrderings.NFree.interpolation_word_program_polytimeOn the published Cook–Levin machine model, the explicit packed-word postprocessor can be computed in polynomial time. Its algorithm forms the coefficient of the shifted Lagrange interpolation, using exact signed integer arithmetic and a single final division.
Preamble
import Definitions.Def_CountOrderings_NFree_InterpolationWordProgram import Definitions.Def_CookLevin_Complexity
Formal statement
namespace CountOrderings.NFree
theorem interpolation_word_program_polytime :
CookLevin.IsPolyTimeComputable interpolationWordProgram := by sorry
end CountOrderings.NFreeSource
Arenas, Schild and Subercaseaux, Hardness of Counting Orderings: Taking Gadget Amplification to the Limit, STOC 2027 submission #1207, https://github.com/sigact-stoc/stoc2027/releases/download/papers-2/1207.pdf, Appendix A.12