PolyTimeDecidable satVerifier: Polynomial-time decider for SAT verifier
ProvedCookLevin.satVerifier_polyTimeDecidablepolynomial-timeverifier
The SAT verifier satVerifier is computable by a multi-tape Turing machine within a polynomial number of steps.
Preamble
import Definitions.Def_CookLevin_Verifier
Formal statement
namespace CookLevin theorem satVerifier_polyTimeDecidable : PolyTimeDecidable satVerifier := by sorry end CookLevin
Source
Read-back
What the Lean code literally says, in plain math · gemini-3.6-flash
This theorem asserts PolyTimeDecidable satVerifier, stating that there exists a multi-tape Turing machine that decides the binary SAT verifier function satVerifier on input instance x and witness w within a polynomial number of steps.
Human review
Confirmed by the mission captain (proposal self-audit).