Can an AI work as a theoretical computer scientist? A paper co-signed by Andrew Yao and Yang Zhilin answers the question with an exam.
Theoretical computer science is the olympiad of mathematics in a specific sense. It studies the limits of computation rather than how to fix a computer: which problems can be solved quickly, and where the boundary of a mathematical proof sits. A group of frontier large language models, ChatGPT among them, has now sat that olympiad.
The paper comes from the team of Yao, a Turing Award winner, academician of the Chinese Academy of Sciences and dean of Tsinghua’s Institute for Interdisciplinary Information Sciences, with Kimi founder Yang Zhilin among the co-authors. Titled TCSExam, it sets out a unified examination that, the authors say, brings the entire research chain of theoretical computer science into one evaluation for the first time.
Four question types, all machine-checked
The exam has four categories, each machine-verified, and it was given to nine frontier models worldwide.
The first is theorem proving. A model receives a research-level theorem and must write a rigorous proof in Lean 4, an assistant that accepts only line-by-line logical steps and does not tolerate vague phrasing. Grading is done by the Lean kernel, which checks each line the way an automatic marker would.
The second is solver engineering. Rather than hard-coding an answer to one problem, the model must write a general solving program, which is then run against large amounts of test data, for example finding the largest clique or the best cut in a set of graphs. The program has to be reusable, so memorising answers does not work.
The third is construction. The model must produce a concrete mathematical object, such as a graph, a code or a geometric arrangement, and attach a certificate proving the object meets the requirement. The machine checks that the object and the certificate match.
The fourth is open conjecture. Models are handed problems that nobody has proved or disproved for decades and asked for a complete proof or a complete disproof, with a counterexample that demonstrably breaks the original claim.
Seventy per cent, unhinted
In theorem proving, the category that drew most attention, GPT-6 Astra worked under bare conditions: only the main theorem, no intermediate lemmas. It produced complete proofs for 14 of 20 problems, a 70 per cent success rate. Kimi K3.1 Pro placed second at 38.3 per cent, and several other models sat in single digits or scored zero.
The paper also tested what happens with help. Given intermediate lemmas and proof ideas, success rose noticeably: Kimi K3 went from 3 to 7 theorems solved, and DeepSeek V4.1 Flash from 0 to 6. The reading is that the models can reason, but need better scaffolding to do it.
In construction, the models did more than match human records. Kimi K3 produced a graph with 124 vertices and 630 edges containing neither a triangle nor a quadrilateral, beating the 629-edge reference record cited in the paper, and it produced a quantum error-correcting code that raised the minimum distance from 5 to 6. GPT-6 Astra proved an upper bound for binary codes: a code of length 22 and minimum distance 10 can hold at most 82 codewords, improving on the previously published 84. The paper cautions that these records need independent verification and that scoring functions can amplify or compress numerical differences, so it reports the raw mathematical parameters alongside.
The open conjectures are the honest part
The most revealing category is the open conjectures. Of 30 long-unsolved problems, only six submissions were accepted, and every one came from a model finding OpenAI’s already published counterexamples for the Ryser and MIRUP conjectures through web search and rewriting them as Lean proofs in the required format. In other words, the models did not think of them. They looked them up. The paper says future evaluations should test conjectures that remain open at the time, with the network disconnected. The remaining 28 had no complete solution.
Failed attempts were not worthless. Working on the Alon-Jaeger-Tarsi conjecture, GPT-6 Astra independently proved it holds over a finite field for all dimensions up to 9, extending the known range from 8, and the result was independently verified in Lean. The paper reports four further independently verifiable partial results.
The overall conclusion is that frontier AI already produces substantive work in research-level theorem proving, construction and solver engineering, but still falls short on genuinely open problems. Breaking a world-class mathematical conjecture unaided remains a long way off.
Editor’s note: This is an adapted translation of the original Sohu Tech report. It has been trimmed and restructured for readability for an international business audience. The full original (in Chinese) is at https://www.sohu.com/a/1099286071_211762.