ReductionIsPolyTime: Polynomial-time computation of cookLevinReduction
ProvedCookLevin.reductionIsPolyTimereductionturing-machine
The reduction function cookLevinReduction is computable by a multi-tape Turing machine in polynomial time.
Preamble
import Definitions.Def_CookLevin_Reduction
Formal statement
namespace CookLevin theorem reductionIsPolyTime : ReductionIsPolyTime := by sorry end CookLevin
Source
Read-back
What the Lean code literally says, in plain math · gemini-3.6-flash
This theorem asserts ReductionIsPolyTime, stating that for any well-formed multi-tape verifier machine Mv, the tableau reduction function cookLevinReduction is computable by a multi-tape Turing machine in polynomial time.
Human review
Confirmed by the mission captain (proposal self-audit).