Polynomial-time emission of the corrected counting tableau
ProvedCountOrderings.NFree.countedCookLevinReduction_polytimeFor a fixed well-formed verifier machine and fixed time and certificate bounds, the corrected Cook–Levin tableau code is computable in polynomial time on the published Cook–Levin model. Compared to the decision tableau, the code appends negative unit clauses for head positions at cell at every time and tape.
Preamble
import Definitions.Def_CountOrderings_NFree_CountingTableau
Formal statement
namespace CountOrderings.NFree
theorem countedCookLevinReduction_polytime
(M : CookLevin.Machine) (k G cw dw ct dt : ℕ)
(hwf : CookLevin.TuringMachine k G M) :
CookLevin.IsPolyTimeComputable
(countedCookLevinReduction M k G cw dw ct dt) := by sorry
end CountOrderings.NFreeSource
Cook–Levin tableau correspondence on the platform, https://prove2.me/theorems/b5d75d8e-6bbb-49a3-bd6d-e25ba880e328, counting refinement for the #X3C source of Theorem 6.3