CONSISTENCY OF CIRCUIT LOWER BOUNDS WITH BOUNDED THEORIES
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F20%3A10420835" target="_blank" >RIV/00216208:11320/20:10420835 - isvavai.cz</a>
Result on the web
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=RcpDf4ka5Z" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=RcpDf4ka5Z</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.23638/LMCS-16(2:12)2020" target="_blank" >10.23638/LMCS-16(2:12)2020</a>
Alternative languages
Result language
angličtina
Original language name
CONSISTENCY OF CIRCUIT LOWER BOUNDS WITH BOUNDED THEORIES
Original language description
Proving that there are problems in P-NP that require boolean circuits of super-linear size is a major frontier in complexity theory. While such lower bounds are known for larger complexity classes, existing results only show that the corresponding problems are hard on infinitely many input lengths. For instance, proving almost-everywhere circuit lower bounds is open even for problems in MAEXP. Giving the notorious difficulty of proving lower bounds that hold for all large input lengths, we ask the following question: Can we show that a large set of techniques cannot prove that NP is easy infinitely often? Motivated by this and related questions about the interaction between mathematical proofs and computations, we investigate circuit complexity from the perspective of logic. Among other results, we prove that for any parameter k >= 1 it is consistent with theory T that computational class C not subset of i.o.SIZE(n(k)), where (T, C) is one of the pairs: T=T-2(1) and C = P-NP , T=S-2(1) and C = NP, T = PV and C = P. In other words, these theories cannot establish infinitely often circuit upper bounds for the corresponding problems. This is of interest because the weaker theory PV already formalizes sophisticated arguments, such as a proof of the PCP Theorem [Pic15b]. These consistency statements are unconditional and improve on earlier theorems of [KO17] and [BM18] on the consistency of lower bounds with PV.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10101 - Pure mathematics
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2020
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Logical Methods in Computer Science
ISSN
1860-5974
e-ISSN
—
Volume of the periodical
16
Issue of the periodical within the volume
2
Country of publishing house
DE - GERMANY
Number of pages
16
Pages from-to
12
UT code for WoS article
000549432200010
EID of the result in the Scopus database
2-s2.0-85087104274