Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR16-071 | 1st May 2016 17:20

#### Unprovability of circuit upper bounds in Cook's theory PV

TR16-071
Authors: Jan Krajicek, Igor Carboni Oliveira
Publication: 1st May 2016 17:59
We establish unconditionally that for every integer $k \geq 1$ there is a language $L \in P$ such that it is consistent with Cook's theory PV that $L \notin SIZE(n^k)$. Our argument is non-constructive and does not provide an explicit description of this language.