[Proof Complexity] a preprint

Jan Krajicek krajicek at karlin.mff.cuni.cz
Wed Apr 20 08:27:29 CEST 2016

  Dear colleagues,

  a new preprint coauthored by Igor C. Oliveira
and myself:

  "Unprovability of circuit upper bounds
   in Cook's theory PV"

is available through his or mine web pages:



We establish unconditionally
that for every $k \geq 1$ there is a language 
L in P such that it is consistent with Cook's theory PV 
that L has no size O(n^k) circuits. 
Our argument is non-constructive and does not provide 
an explicit description of this language.

We will appreciate comments on all aspects of 
the paper.



More information about the Proof-Complexity mailing list