Unprovability of circuit upper bounds in Cook's theory PV

الأصل · EN

We establish unconditionally that for every integer k ≥ 1 there is a language L ∈ P such that it is consistent with Cook's theory PV that L ∉ Size(nᵏ). Our argument is non-constructive and does not provide an explicit description of this language.