Jan Krajicek ; Igor C. Oliveira - Unprovability of circuit upper bounds in Cook's theory PV

lmcs:3119 - Logical Methods in Computer Science, February 3, 2017, Volume 13, Issue 1 - https://doi.org/10.23638/LMCS-13(1:4)2017
Unprovability of circuit upper bounds in Cook's theory PVArticle

Authors: Jan Krajicek ; Igor C. Oliveira

    We establish unconditionally that for every integer k≥1 there is a language L∈P such that it is consistent with Cook's theory PV that L∉Size(nk). Our argument is non-constructive and does not provide an explicit description of this language.

    https://doi.org/10.23638/LMCS-13(1:4)2017
    Source: arXiv.org:1605.00263
    Volume: Volume 13, Issue 1
    Published on: February 3, 2017
    Accepted on: February 3, 2017
    Submitted on: February 3, 2017
    Keywords: Mathematics - Logic,Computer Science - Computational Complexity,03F30, 68Q15,F.4.1
    Licence: arXiv.org - Non-exclusive license to distribute

    2 Documents citing this article

    Share and export

    Consultation statistics

    This page has been seen 2546 times.
    This article's PDF has been downloaded 671 times.