The foundations of computational complexity theory were just shaken.
Recent algorithmic breakthroughs generated by frontier AI models have shattered long-standing mathematical assumptions. Specifically, research models from Anthropic and OpenAI have concurrently refuted the Exponential Time Hypothesis (ETH), alongside the 3SUM and All-Pairs Shortest Paths (APSP) conjectures.
These are extraordinary, textbook-rewriting developments. However, concluding that decades of research built around these conjectures was pointless fundamentally misunderstands what that research actually proved -- and what makes theoretical inquiry valuable.
Many hardness results in computational complexity are framed as conditional implications:
“If problem A cannot be solved this quickly, then neither can problem B.”
The proof constructs a translation from A to B, carefully controlling how much the problem instance grows via this translation. We call this a reduction. A sufficiently fast algorithm for B would then give a sufficiently fast algorithm for A.
The hardness of A is a provisional assumption. The reduction itself is a proven, permanent mathematical fact.
Much of modern cryptography follows this exact same pattern. An efficient attack on a cryptographic scheme would yield an efficient algorithm for an underlying mathematical problem. The security conclusion depends on that problem being hard; the proof establishes the unbreakable connection between them.
When the assumption falls, something substantial is lost. We can no longer use it to justify a claimed computational barrier. But the reduction remains entirely correct. The relationship between the problems survives.
In fact, those very relationships are what allow an algorithmic breakthrough to spread from one problem to dozens of others. The new 3SUM and APSP work explicitly exploits previously known reductions to unlock further consequences. Mathematics developed to map hardness is the exact tool we need to exploit unexpected easiness.
There is a vital lesson here for how the scientific community communicates results.
Moving forward, we should explicitly state the exact mathematical relationship we actually prove, detailing its quantitative bounds. The conjecture-based hardness conclusion should follow strictly as a secondary corollary.
For a simple illustration, a sparse 3-SAT instance with n variables and a proportional number of constraints can be translated into a vertex-cover problem on a graph with a proportional number of vertices. That rigid control over size is what allows us to relate the running times. This translation remains deeply meaningful and potentially useful in a completely different context, regardless of whether ETH stands or falls.
Researchers often already state their results this way. We should give those relationships more importance, especially when explaining our work beyond our immediate community.
Fine-grained complexity gave researchers a reason to hunt for unusually economical (or fine-grained, as we like to call them) reductions. That exploration produced techniques and connections that might otherwise have remained undiscovered. A conjecture can be false and still have been a useful question to investigate. Its eventual refutation does not, by itself, make investigating it unreasonable.
This highlights a deeper concern regarding AI in pure research -- a vulnerability being highlighted by many mathematicians, but one that the broader community frequently misses.
If an AI system had simply supplied the final answer before this decades-long exploration began, which intermediate discoveries would we still have made? Which foundational questions would we have never thought to ask?
We cannot know. Earlier answers can open new directions, and AI can help explore them. But there is a distinct risk in treating a finished statement and proof as the absolute end of an inquiry. We may move on before discovering what else the question had to teach us. Even a correct proof can arrive far too early -- long before we have fully explored the surrounding landscape of ideas.
That possibility deserves serious attention as we decide how to integrate these systems into academic research. We must explicitly value the deep understanding developed through exploration alongside the raw answers obtained.
And we must remain curious, even when the answers surprise us.
Stay hungry. Stay foolish. Even if AI is smarter than you.
Beyond all this sometimes unwanted light, there will still be that familiar darkness: things we do not understand, questions we have not learned to ask, and room to find meaning for ourselves.
No comments:
Post a Comment