Unprovability of circuit upper bounds in Cook's theory PV
oleh: Jan Krajicek, Igor C. Oliveira
| Format: | Article |
|---|---|
| Diterbitkan: | Logical Methods in Computer Science e.V. 2017-02-01 |
Deskripsi
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.