Polynomial-time languages in the Cook–Levin cost model
DefinitionAggCG_Supplement_InPalgorithm-configurationcomputational-complexitymachine-learningoptimizationp2o-gran-per-chapterp2o-plan-paperp2o-v1
A Boolean language is in when a polynomial-time computable total map returns the one-bit answer true exactly on the strings belonging to the language.
Definition code
import Mathlib import Definitions.Def_CookLevin_Complexity namespace AggCG.Supplement /-- Membership in the class P on the CookLevin cost model: a polynomial-time computable map answers `[true]` exactly on the members (Sharma, *Computational Complexity of Data-Driven Configuration for Integer Programming, Clustering, and Learning Algorithms*, STOC 2027 submission (manuscript sha256 f7ea0248…), Theorem G.1, p.41, PDF p.42: "width-one probe ERM ∈ P"). **Formalization Note** The CookLevin layer has no class P; this is the same shape as the published `AggCG.PEqNP`, which quantifies over exactly such maps. -/ def InP (L : CookLevin.Language) : Prop := ∃ f : List Bool → List Bool, CookLevin.IsPolyTimeComputable f ∧ ∀ x, L x ↔ f x = [true] end AggCG.Supplement
Source
Sharma, STOC 2027 submission (manuscript sha256 f7ea0248…), Theorem G.1, p.41, PDF p.42