UNPROVABILITY OF CIRCUIT UPPER BOUNDS IN COOK'S THEORY PV

Abstract

We establish tmconditionally that for every integer k >= 1 there is a language L is an element of P such that it is consistent with Cook's theory PV that L is not an element of SIZE(n(k)). Our argument is non-constructive and does not provide an explicit description of this language.

Keywords

• UNPROVABILITY
• CIRCUIT
• UPPER
• BOUNDS
• COOKS
• THEORY