Journal article · 2026 · Open access

Towards P≠NP from Extended Frege lower bounds

Ján Pich, Rahul Santhanam

Journal of the ACM, 73(2), 1–27 · Published 19 March 2026 · DOI 10.1145/3801091

Open full textCite this paper

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

YearCitationsShare of the best year
202411
202511
202633

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

All highly cited Computer Science papers

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.