EUVIMEDEUVIMED entdecken
Crossref

Reverse Mathematics of Complexity Lower Bounds

Lijie Chen, Jiatu Li, Igor Oliveira

SIAM Journal on Computing · 31.10.2026 · 55 (5) · FOCS24-316-FOCS24-364

DOI: 10.1137/24m1717865 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 29.04.2026. Verfasst von Lijie Chen und 2 weiteren Autor:innen. Die Arbeit nennt 75 Literaturangaben. Gefördert von: Miller Research, MIT Akamai Presidential Fellowship, Royal Society University.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Reverse mathematics is a program in mathematical logic that seeks to determine which axioms are necessary to prove a given theorem. In this work, we systematically explore the reverse mathematics of complexity lower bounds. We explore reversals in the setting of bounded arithmetic, with Cook’s theory [Formula: see text] as the base theory, and show that several natural lower bound statements about communication complexity, error correcting codes, and Turing machines are equivalent to widely investigated combinatorial principles such as the weak pigeonhole principle for polynomial-time functions and its variants. As a consequence, complexity lower bounds can be formally seen as fundamental mathematical axioms with far-reaching implications. The proof-theoretic equivalence between complexity lower bound statements and combinatorial principles yields several new implications for the (un)provability of lower bounds. Among other results, we derive the following consequences: (1) Under a plausible cryptographic assumption, the classical single-tape Turing machine [Formula: see text]-time lower bound for Palindrome is unprovable in Jeřábek’s theory [Formula: see text]. The conditional unprovability of this simple lower bound goes against the intuition shared by some researchers that most complexity lower bounds could be established in [Formula: see text]. (2) While [Formula: see text] proves one-way communication lower bounds for set disjointness, it does not prove one-way communication lower bounds for Equality, under a plausible cryptographic assumption. (3) An amplification phenomenon connected to the (un)provability of some lower bounds, under which a quantitatively weak [Formula: see text] lower bound is provable if and only if a stronger (and often tight) [Formula: see text] lower bound is provable. (4) Feasibly definable randomized algorithms can be feasibly defined deterministically ([Formula: see text] is [Formula: see text]-conservative over [Formula: see text]) if and only if one-way communication complexity lower bound for set disjointness are provable in [Formula: see text].

Förderung

  • Miller Research
  • MIT Akamai Presidential Fellowship
  • Royal Society University
  • National Science Foundation
  • University of Warwick
  • UKRI Frontier Research Guarantee

Zitieren

APA

Chen, L., Li, J., & Oliveira, I. (2026). Reverse Mathematics of Complexity Lower Bounds. SIAM Journal on Computing, 55(5), FOCS24-316-FOCS24-364. https://doi.org/10.1137/24m1717865

Vancouver

Chen L, Li J, Oliveira I. Reverse Mathematics of Complexity Lower Bounds. SIAM Journal on Computing. 2026;55(5):FOCS24-316-FOCS24-364. doi:10.1137/24m1717865

BibTeX
@article{Chen2026,
  author = {Chen, Lijie and Li, Jiatu and Oliveira, Igor},
  title = {Reverse Mathematics of Complexity Lower Bounds},
  journal = {SIAM Journal on Computing},
  year = {2026},
  volume = {55},
  number = {5},
  pages = {FOCS24--316--FOCS24--364},
  doi = {10.1137/24m1717865}
}
Kostenlos starten →