SIGACT News Complexity Theory Column 124 <b>Meta-Mathematics of Computational Complexity Theory</b>

We survey results on the formalization and independence of mathematical statements related to major open problems in computational complexity theory. Our primary focus is on recent findings concerning the (un)provability of complexity bounds within theories of bounded arithmetic. This includes the techniques employed and related open problems, such as the (non)existence of a feasible proof that P = NP.

Authors

Institutions

Publication Details

Journal
ACM SIGACT News
Published
2025-03-24
DOI
https://doi.org/10.1145/3726856.3726862
Primary Topic
Computability, Logic, AI Algorithms
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

SIGACT News Complexity Theory Column 124 Meta-Mathematics of Computational Complexity Theory

Igor C. Oliveira
ACM SIGACT News
Computability, Logic, AI Algorithms
article

SIGACT News Complexity Theory Column 124 Meta-Mathematics of Computational Complexity Theory

Igor C. Oliveira
article en

Abstract

We survey results on the formalization and independence of mathematical statements related to major open problems in computational complexity theory. Our primary focus is on recent findings concerning the (un)provability of complexity bounds within theories of bounded arithmetic. This includes the techniques employed and related open problems, such as the (non)existence of a feasible proof that P = NP.

ACM SIGACT NewsVol. 56(1)
Herzliya Medical Center (IL)
Openalex Percentile: Top 93%
Computability, Logic, AI Algorithms
DOIOpen Access PDFOpenAlex
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

SIGACT News Complexity Theory Column 124 <b>Meta-Mathematics of Computational Complexity Theory</b> — Igor C. Oliveira · ACM SIGACT News (2025) | TGRS Research Map | TGRS