Journal article · 2026 · Open access
Towards P≠NP from Extended Frege lower bounds
Journal of the ACM, 73(2), 1–27 · Published 19 March 2026 · DOI 10.1145/3801091
In brief
“Towards P≠NP from Extended Frege lower bounds” is a 2026 journal article by Ján Pich and Rahul Santhanam, published in Journal of the ACM. OpenAlex counts 5 citations as of 17 November 2026. It is open access under a CC BY licence: the full text is free to read at Journal of the ACM.
- Citations
- 5
- Most cited in
- 2026 (3)
- Field-weighted impact
- 4.75
- References
- 59
- Authors
- 2
Abstract
We give a new approach to the fundamental question of whether proof complexity lower bounds for concrete propositional proof systems imply super-polynomial Boolean circuit lower bounds. We observe that any general implication from proof complexity lower bounds for a propositional proof system to super-polynomial Boolean circuit lower bounds implies unconditionally that \({\sf NEXP}\) does not have Boolean circuits of polynomial size. We explore connections that are possible to establish without settling this long-standing and famously hard open question. For any poly-time computable function f , we define the witnessing formulas \(w_n^k(f)\) , which are propositional formulas stating that for any circuit C of size \(n^k\) on n variables and for any formula \(\phi\) of size n , either C computes a satisfying assignment to \(\phi\) or f verifiably refutes that C computes \({\sf SAT}\) on instances of length n . We show that if the witnessing formulas are tautologies, then any super-polynomial lower bound for Extended Frege augmented with \(w_n^k(f)\) axioms implies that \({\sf SAT}\) requires super-polynomial size Boolean circuits. We also give an unconditional equivalence between circuit lower bounds for the Discrete Logarithm problem and proof complexity lower bounds (for propositional formulas efficiently encoding the statement that the Discrete Logarithm problem is computable by small circuits) for a concretely defined strong (non-uniform) propositional proof system. We give consequences of our connections for the meta-mathematics of several major questions in computational complexity, including whether one-way functions can be based on the worst-case hardness of NP, whether there is a dichotomy between one-way functions and worst-case learning with membership queries over the uniform distribution, and whether there are feasibly constructible anti-checkers for Satisfiability. We show that for each of these questions, provability of a positive answer in essentially any standard mathematical theory would imply new connections between propositional proof complexity and circuit complexity. Our results rely on a new notion of “self-provability” of upper bounds, which might be independently interesting, and involve a novel application of random self-reducibility to proof complexity.
Cite this paper
Formatted from the catalogue record. Check names, capitals and page numbers against the paper before you submit.
APA 7
Pich, J., & Santhanam, R. (2026). Towards P≠NP from Extended Frege lower bounds. Journal of the ACM, 73(2), 1–27. https://doi.org/10.1145/3801091
MLA 9
Pich, Ján, and Rahul Santhanam. “Towards P≠NP from Extended Frege lower bounds.” Journal of the ACM, vol. 73, no. 2, 2026, pp. 1–27. https://doi.org/10.1145/3801091.
Chicago
Pich, Ján and Rahul Santhanam. 2026. “Towards P≠NP from Extended Frege lower bounds.” Journal of the ACM 73 (2): 1–27. https://doi.org/10.1145/3801091.
Harvard
Pich, J. and Santhanam, R. (2026) ‘Towards P≠NP from Extended Frege lower bounds’, Journal of the ACM, 73(2), pp. 1–27. doi:10.1145/3801091.
IEEE
J. Pich and R. Santhanam, “Towards P≠NP from Extended Frege lower bounds,” Journal of the ACM, vol. 73, no. 2, pp. 1–27, 2026, doi: 10.1145/3801091.
BibTeX
@article{pich2026towards,
title = {{Towards P≠NP from Extended Frege lower bounds}},
author = {Pich, Ján and Santhanam, Rahul},
journal = {Journal of the ACM},
year = {2026},
volume = {73},
number = {2},
pages = {1--27},
doi = {10.1145/3801091},
url = {https://doi.org/10.1145/3801091}
}
Download for a reference manager: BibTeX (.bib) · RIS for Zotero, Mendeley and EndNote (.ris)
Citations by year
| Year | Citations | Share of the best year |
|---|---|---|
| 2024 | 1 | |
| 2025 | 1 | |
| 2026 | 3 |
Its field-weighted citation impact is 4.75: it has been cited 4.75 times as often as the average work of the same field, type and year (1.00 is the world average).
Topic and keywords
Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- P versus NP
- propositional proof systems
- Boolean circuit lower bounds
- discrete logarithm problem
- one-way functions
- proof complexity
Work with this paper
Most-cited papers in Computer Science
- ImageNet classification with deep convolutional neural networksAlex Krizhevsky, Ilya Sutskever, Geoffrey E. Hinton · Communications of the ACM · 2017 · 114,726 citations
- Long Short-Term MemorySepp Hochreiter, Jürgen Schmidhuber · Neural Computation · 1997 · 109,097 citations
- A Mathematical Theory of CommunicationClaude E. Shannon · Bell System Technical Journal · 1948 · 91,736 citations
- Deep learningYann LeCun, Yoshua Bengio, Geoffrey E. Hinton · Nature · 2015 · 90,226 citations
- Faster R-CNN: Towards Real-Time Object Detection with Region Proposal NetworksShaoqing Ren, Kaiming He, Ross Girshick and 1 more · IEEE Transactions on Pattern Analysis and Machine Intelligence · 2016 · 74,143 citations
Questions about this paper
How do I cite this paper in APA style?
Pich, J., & Santhanam, R. (2026). Towards P≠NP from Extended Frege lower bounds. Journal of the ACM, 73(2), 1–27. https://doi.org/10.1145/3801091
How many times has this paper been cited?
5 times, according to OpenAlex on 17 November 2026. Google Scholar and Scopus count different sets of sources, so their numbers differ.
Is this paper free to read?
Yes. It is open access at Journal of the ACM: sign in and open the full text from this page.
Who wrote this paper?
Ján Pich, Rahul Santhanam.
What is the DOI of this paper?
10.1145/3801091, permanently at https://doi.org/10.1145/3801091. Sign in and open it from this page.
Bibliographic data from OpenAlex (CC0), last checked 17 November 2026. ResearchGuru does not host this paper; once you are signed in, the links open it at the publisher or the repository that does.