Unprovability of circuit upper bounds in Cook's theory PV
Authors: Jan Krajicek ; Igor C. Oliveira
NULL##NULL
Jan Krajicek;Igor C. Oliveira
We establish unconditionally that for every integer $k \geq 1$ there is a
language $L \in \mbox{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.