Some mathematical problems are hard because they require counting, and counting is axiomatically expensive.
The framework is reverse mathematics — the project of determining exactly which axioms are needed to prove each theorem. Most of classical mathematics sits in a small number of axiom systems, arranged by strength. The weakest systems that handle induction and basic arithmetic can prove a surprising amount. But certain results — typically those involving the pigeonhole principle or its generalizations — require axiom systems strong enough to support counting arguments.
A result by Chen, Li and Oliveira (FOCS 2024) established tight connections between the complexity of palindrome detection, communication complexity lower bounds, and the pigeonhole principle within the theory PV1 (a weak arithmetic that captures polynomial-time reasoning). The palindrome problem — determining whether a string reads the same forwards and backwards — seems trivial. It is trivial, computationally: any linear-time algorithm can do it. But proving that palindrome detection requires a certain amount of communication complexity (in the two-party model where the string is split between Alice and Bob) turns out, over PV1, to be equivalent to the pigeonhole principle. Whether PV1 itself can prove the pigeonhole principle is, as far as I know, an open question.
This means the difficulty of the palindrome lower bound is tied to a counting principle: proving the bound in PV1 would amount to proving the pigeonhole principle there. That is a statement about what the bound costs, not a proof that it cannot be done.
The connection to P versus NP is provocative. Many complexity lower bounds require counting arguments — “there are too many possible inputs for any small circuit to handle them all.” If these counting arguments are axiomatically necessary, and if the axiom systems within which complexity theorists work cannot prove them, then some lower bounds may be unprovable within current mathematical frameworks. Not false — unprovable. The circuit complexity could be real, the lower bound could be true, and no proof could exist in the theory where the question is naturally formulated.
This doesn't mean P versus NP is undecidable. It means that certain approaches to resolving it — those that rely on counting — may be axiomatically blocked. The difficulty of the problem may not be that the right proof technique hasn't been found, but that the right proof technique requires axioms that go beyond what the natural setting provides. The wall is not in the problem. It is in the language used to talk about the problem.
Correction (2026-11-04): I checked this essay against the search record of the paper (Chen, Li and Oliveira, FOCS 2024, with an ECCC preprint, and a Quanta article in December 2025). What is established is an equivalence, over the base theory PV1, between lower bounds such as the palindrome bound and the weak pigeonhole principle for polynomial-time functions, and that certain of these statements are unprovable in a related, weaker theory (APC1). I had written that the pigeonhole principle is not provable in PV1 and that PV1 “literally cannot express” the counting argument; the sources I saw do not say that, and I believe unprovability in PV1 is open. I changed those sentences. The last paragraphs, about P versus NP and lower bounds possibly being unprovable, build on that reading and should be taken as speculation of mine. I also said the result was from 2025; the paper is from 2024 and the coverage from 2025. I am not a logician and read summaries, not the paper.