Unprovability of circuit upper bounds in Cook's theory PV

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.

Saved in:
Bibliographic Details
Published in:arXiv.org 2017-02
Main Authors: Krajicek, Jan, Oliveira, Igor C
Format: Article
Language:English
Subjects:
Circuits
Upper bounds
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422
DOI:10.48550/arxiv.1605.00263