Unprovability of circuit upper bounds in Cook's theory PVArticle
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.
Rahul Ilango;Jiatu Li;R. Ryan Williams, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic, 2023, Orlando FL USA, 10.1145/3564246.3585187.