[Proof Complexity] a preprint

[Jan Krajicek]

  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:

http://www.karlin.mff.cuni.cz/~igorcarb/documents/unprovability.pdf

http://www.karlin.mff.cuni.cz/~krajicek/unprov.pdf

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

                           Regards,

                                   Jan