Unprovability of circuit upper bounds in Cook's theory PV

Jan Krajicek; Igor C. Oliveira

doi:10.23638/LMCS-13(1:4)2017

Jan Krajicek ; Igor C. Oliveira - Unprovability of circuit upper bounds in Cook's theory PV

lmcs:3119 - Logical Methods in Computer Science, February 3, 2017, Volume 13, Issue 1 - https://doi.org/10.23638/LMCS-13(1:4)2017

Unprovability of circuit upper bounds in Cook's theory PVArticle

Authors: 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.

https://doi.org/10.23638/LMCS-13(1:4)2017

Source: arXiv.org:1605.00263

Volume: Volume 13, Issue 1

Published on: February 3, 2017

Accepted on: February 3, 2017

Submitted on: February 3, 2017

Keywords: Mathematics - Logic,Computer Science - Computational Complexity,03F30, 68Q15,F.4.1

Licence: arXiv.org - Non-exclusive license to distribute