Unprovability of circuit upper bounds in Cook's theory PV

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.

Saved in:
Bibliographic Details
Published in:Logical methods in computer science 2017-01, Vol.13, Issue 1
Main Authors: Jan Krajicek, Igor C. Oliveira
Format: Article
Language:English
Subjects:
03f30, 68q15
computer science - computational complexity
f.4.1
mathematics - logic
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1860-5974
DOI:10.23638/LMCS-13(1:4)2017