Why Frontier LLMs Cannot Solve Open Theoretical Computer Science Conjectures
A 100-task benchmark for theoretical computer science uses machine-verifiable proofs, counterexamples, and algorithm analyses to test whether leading LLMs can conduct real research. The results show that models perform reasonably well on known theorems and structured reasoning tasks, but none can independently solve open conjectures that have remained unresolved for decades. The evaluation clarifies the boundary between solving exercises and doing original research, and it suggests where LLMs can serve as reliable research assistants—and where human verification remains essential.
1. Background: When “AI Conquers Mathematics” Becomes a Hot Topic
Over the past year or two, discussion of whether AI will replace mathematical research has continued to heat up. Mathematics has become a preferred battleground for several reasons, but the most important is its built-in verification advantage: proving a theorem can be extremely difficult, while checking whether a proof is correct is often much cheaper. It is a bit like Sudoku—filling in the answer is hard, but once it is filled in, checking whether it is right is straightforward. As a result, among all research fields, mathematics is the easiest place to produce “undisputed” AI scorecards, and the corresponding marketing and publicity tend to be the most intense.
Yet amid the noise about AI “disrupting” mathematical research, a paper co-authored by a Turing Award winner, a prominent large-model entrepreneur, and scholars from universities and research institutions offered a sobering counterpoint. The study designed a benchmark specifically for Theoretical Computer Science (TCS) to systematically test whether the strongest current large language models possess genuine research capabilities.
The conclusion was not optimistic: for open conjectures in theoretical computer science that have remained unresolved for decades, none of the tested models could independently produce a solution. The result is a reminder that even as models climb the leaderboards on public benchmarks, they are still a considerable distance from independently conducting frontier research.
2. Core Question: Does “Good at Problems” Mean “Good at Research”?
2.1 Why a New Evaluation Method Is Needed
Benchmarks in the large-model field are refreshed almost every two months, and the number of leaderboards can be dizzying. But a closer look shows that most of them measure “problem-solving ability”—the ability to produce an expected answer after a given input. The upper bound of this kind of ability is roughly “problems humans already know how to solve.”
The nature of research is fundamentally different. Research has no prescribed steps and no standard-answer recipe. No one knows in advance whether it will succeed—sometimes even the person posing the question does not know the answer. A cooking analogy helps: solving a problem is like following a recipe, with ready-made steps and a standard taste that anyone can use to judge the result; research is like inventing a new dish from scratch, with no recipe to follow and no one knowing in advance what the dish should taste like.
2.2 The Grading Challenge: Who Verifies an “AI Proof”?
Research-style evaluation faces an even more difficult obstacle: grading. When a model claims to have cracked a conjecture that has remained open for decades, who verifies that what it wrote is correct? Manually checking a complex proof is extremely expensive and prone to subjective bias. If the result cannot be graded reliably, the evaluation loses its meaning.
This is why theoretical computer science became an ideal evaluation target, both by accident and by necessity. TCS sits at the intersection of mathematics and computer science. All of its problems revolve around computation, the core method of research is formal proof, and the correctness of most proofs can be checked automatically by machines. In other words, TCS naturally has the property of being “machine-gradable”—a key reason it stands out among many research directions.
A traffic analogy is useful: ordinary programmers are like drivers who care about engine performance and interior experience, while theoretical computer science researchers care about “traffic” itself—how fast can you actually get from point A to point B? Is there a route that is fundamentally impossible? These questions are abstract and fundamental, and their conclusions can be converted into verifiable formal propositions.
3. Benchmark Design: Only Machine-Gradable Problems
The core design philosophy of this benchmark is: the closer a problem is to real research, the harder it is to grade; therefore, we must find research-style problems whose conclusions can be verified by machines. Based on this principle, the benchmark contains 100 problems divided into four categories, corresponding to four typical forms of daily work for theoretical computer scientists.
3.1 Proving Existing Theorems
Models are asked to complete or reconstruct proofs of known classical theorems. This type of task is closest to “advanced problem solving,” but the difficulty is that the logical chain of the proof must be rigorous and complete; any gap will cause machine verification to fail. It tests the model’s systematic grasp of a theoretical system and the reliability of long-chain formal reasoning.
3.2 Conjecture Judgment and Counterexample Construction
Given a seemingly plausible proposition whose truth is unknown, the model must judge whether it holds; if it does not, the model must construct a counterexample. This goes beyond “recalling known conclusions”—judging an open problem often requires intuition, construction ability, and a deep understanding of the problem’s structure. Counterexample construction is especially difficult because the model must find, within a huge search space, the special case that “exactly breaks” the proposition.
3.3 Algorithm Design and Analysis
Models are asked to design algorithms for specific problems and provide correctness and complexity analyses. Grading for this type of task can be partially automated: whether the algorithm passes all test cases and whether the time complexity meets the requirement are objectively verifiable. It tests the model’s creative process from problem to solution, rather than reproduction of known algorithms.
3.4 Solving Open Conjectures
This is the hardest part of the entire benchmark: models are directly confronted with open conjectures that remain unsolved. These tasks can hardly be completed by “memorizing answers,” because the answers do not exist in the human knowledge base. The model must demonstrate genuine original research ability. The evaluation results show that this is precisely where all models failed completely.
The four task types form a capability spectrum from “mastering the known” to “exploring the unknown,” allowing the evaluation not only to produce an overall score but also to characterize specific weaknesses in models’ research capabilities.
4. Results and Interpretation
4.1 Main Findings
The evaluation shows that models already perform meaningfully in reproducing known theorems and completing medium-difficulty proofs, and some problems even reveal reasoning skills beyond expectations. But when faced with open conjectures requiring original breakthroughs, no model could independently provide a solution. This “strong early, weak late” distribution clearly marks the ceiling of current large-model research capability: they are excellent knowledge integrators and reasoning executors, but they are not yet discoverers of original theorems.
4.2 Why This Happens
From a technical perspective, the core capability of current large models is built on pattern learning from massive amounts of text, and their output is essentially high-probability sequence generation. This mechanism is extremely effective for “combining reasoning within a known paradigm,” but open conjectures often require breaking existing paradigms and inventing entirely new proof tools or problem representations—precisely the weak spot of statistical pattern learning. In addition, error accumulation in long-chain reasoning makes complex proofs prone to being “locally plausible but globally wrong” when written by a model.
4.3 Correcting the “AI Disrupts Mathematics” Narrative
The significance of this evaluation is not to disparage but to calibrate expectations. On the one hand, it confirms that large models are already practically useful as research assistants: literature review, proof draft generation, counterexample search, and idea inspiration can all be significantly more efficient. On the other hand, it uses empirical data to show that the narrative that “AI will soon independently solve the Millennium Prize problems” lacks support. For researchers, the more reasonable positioning is to treat large models as tireless but confidently error-prone junior collaborators—their outputs must undergo rigorous human or machine verification before entering a paper.
5. Implications and Outlook
The design philosophy of this benchmark has value beyond TCS itself: to build credible evaluations of research capability, the key is to find a task range that is “hard enough and objectively gradable.” In the future, more evaluation directions with machine verifiability may emerge, such as formal mathematics, cryptographic constructions, and protocol verification, forming a multidimensional picture of models’ research capabilities.
For enterprises and developers, this evaluation paradigm also suggests that when introducing large models into R&D workflows, they should prioritize stages where “results can be automatically checked” (such as test case generation, static code checking, and algorithm correctness verification), while retaining sufficient human review for stages where conclusions cannot be automatically verified. Matching capability with responsibility is the prerequisite for robust deployment of large-model technology.
In short, “being good at problems” and “being good at research” are separated by three thresholds: originality, verifiability, and long-horizon reasoning stability. The 100-task evaluation by Andrew Yao and Yang Zhilin’s teams delineates the current boundary of large-model capability—mathematicians can indeed breathe a sigh of relief for now, but the era of AI as a research assistant has only just begun.
