Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR16-071 | 1st May 2016 17:20

Unprovability of circuit upper bounds in Cook's theory PV

RSS-Feed




TR16-071
Authors: Jan Krajicek, Igor Carboni Oliveira
Publication: 1st May 2016 17:59
Downloads: 498
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint