Can AI Solve Open Problems on Its Own? Answers from a Theoretical Computer Science Exam

    A benchmark paper built around a theory of computer science (TCS) exam tests today's strongest large language models on machine-verifiable problems. None of the evaluated models could independently solve any of the open conjectures included. The paper is less interesting for that single score than for the evaluation methodology it demonstrates: problems must be machine-verifiable, answers must be machine-decidable, and scores must separate "can do exercises" from "can do research." This article walks through what TCS is, why leaderboards fail to measure research ability, how verification and solving asymmetry makes TCS unusually suitable for automated grading, what four tiers of problems revealed about model capability boundaries, and how engineering teams can reuse the approach to build their own verifiable evaluation sets with layered rubrics, contamination controls, reproducible pipelines, and scoring functions that resist gaming.

    1. An Unusual Exam

    A benchmark paper aimed at theoretical computer science drew attention to two names in its author list: a recipient of computer science’s highest award who leads an interdisciplinary information research institute at a top university, and the founder of a large-model startup. The five authors come from research institutions and large-model teams. In one sentence, the paper’s core contribution is this: they wrote an exam and gave it to the strongest large models available.

    The conclusion is a cold shower. On the open conjectures that remain unsolved to this day, not one participating model was able to crack one on its own.

    What theoretical computer science actually is

    TCS (Theoretical Computer Science) is not about fixing computers or writing code. It studies computation itself. A rough analogy: programmers are like drivers, concerned with the engine and the interior; TCS studies traffic itself — how fast you can theoretically get from point A to point B, which routes are provably impassable, and how far you can reach under a given resource budget.

    TCS sits at the intersection of mathematics and computer science. Everything revolves around computation, and the primary research tool is proof. This gives it a mathematical character: like Sudoku, filling the grid in is hard, but checking whether the filled grid is correct is easy. That is also why mathematics has long been the least controversial source of results for AI companies to report.

    2. Why Leaderboards Can’t Measure Research Capability

    Model leaderboards refresh roughly every two months, fast enough to be dizzying. But a leaderboard can only show that a model can solve exercises; it says little about research level.

    • Doing exercises is cooking from a recipe. The steps are ready-made and the criteria are explicit — nobody has ever seen a chocolate bar in a sweet-and-sour pork dish count as correct. Research has no prescribed steps, nobody can be sure in advance whether an approach will work, and for many problems even the person who posed them doesn’t know the answer.
    • Grading is harder than setting the exam. A model can produce hundreds of pages of “proof” in one pass. Who has time to check it page by page? It claims to have settled a conjecture that stood open for decades — who verifies that? Some AI teams have published hundreds of model-generated conjecture manuscripts; most of this output currently lacks rigorous verification.
    • Benchmark saturation and contamination. Problems repeatedly enter training corpora, so rising scores may reflect memorization rather than capability. Evaluation problems therefore need to be held privately, updated continuously, and paired with “control problems” whose answers are known, to calibrate results.

    The question this paper sets out to answer is simple: if you actually put AI to work on research, what does it accomplish? Its approach is equally direct — write only problems a machine can grade.

    3. Why TCS

    The more a problem resembles real research, the harder it is to score. TCS happens to be the exception: most of its conclusions can be verified by a machine.

    Behind this is the asymmetry between verification and solving. Some problems are extremely hard to solve, yet once a candidate answer is provided, checking it can be fast. This echoes a central proposition of computational complexity theory: NP is the class of problems whose candidate solutions can be verified in polynomial time — and whether P equals NP remains open. It is precisely this asymmetry that makes TCS research output, namely proofs, naturally suited to automated grading: you don’t have to read a paper word by word, you only need a verifier to check whether the proof holds.

    To turn this idea into an engineering artifact, an evaluation set generally needs to satisfy four conditions:

    1. Mechanically verifiable answers: scoring depends on an executable checking program, not on subjective human judgment.
    2. Unique or normalizable answers: results such as numbers, expressions, and complexity orders need a canonical form, so equivalent notations aren’t marked wrong.
    3. Layered difficulty: from textbook-level routine problems up to research-level open problems, so you can measure where a model’s capability boundary lies.
    4. Uncontaminated problem statements: problems are maintained privately and rotated periodically.

    A sketch of the flow:

    1. def evaluate(model, problem):
    2. raw = model.solve(problem.statement) # Generate a solution or proof
    3. answer = extract(raw) # Extract the final answer
    4. if problem.answer_checker:
    5. return problem.answer_checker(answer) # Answer checking: constant-time decision
    6. if problem.proof_verifier:
    7. return problem.proof_verifier(raw) # Proof verification: check reasoning step by step
    8. return HumanReview(raw) # Fallback: still cannot decide automatically

    It’s worth stressing that proof_verifier is not a simple string comparison. It decomposes a proof into checkable inference steps and confirms, step by step, whether each one is valid.

    4. Four Problem Categories, Four Kinds of Research Work

    The exam has 100 problems in four categories, corresponding to four activities theoretical computer scientists do day to day. Based on public information, they can be summarized as follows (the paper itself is authoritative on the exact classification):

    • Category 1: Routine research problems. Deterministic answers; tests command of definitions, theorems, and existing results. This is the capability baseline.
    • Category 2: Research problems requiring a complete proof. Not only the answer, but an argument for why it is correct; the focus is on whether the chain of reasoning is rigorous.
    • Category 3: Research problems spanning subfields. Covers different branches within TCS; tests breadth of knowledge and transfer ability.
    • Category 4: Open conjectures. Unsettled and without reference answers; tests the ability to “produce something new.”

    Discrimination across the four categories is highly asymmetric. The first two separate strong from weak models reasonably well; the fourth is a cliff. Not one of the strongest current models was able to independently solve an open conjecture.

    How to read the results

    First, the conclusion cannot be extrapolated directly to all branches of mathematics. Many TCS problems are carried by discrete combinatorial objects and have normalized answer forms, which happens to suit machine grading. Many conjectures in analysis, geometry, and other areas are hard to verify this way, and this paper’s findings do not cover them.

    Second, “solved independently” is a strict standard. Human-AI collaboration — where a model proposes candidate directions and a human then rigorously proves them — has value and risks that need separate assessment.

    Third, the models are not useless. They may supply valuable intermediate lemmas, find counterexamples, or shrink a search space. What they cannot yet do is close the full loop on their own: propose a conjecture, construct a proof, and withstand peer scrutiny.

    5. Implications for Enterprise Evaluation Practice

    If your team is also assessing whether large models can take on R&D work, this exam offers a methodology you can reuse directly.

    5.1 Split “research-level evaluation” into three layers

    Layer What it assesses Scoring method
    Baseline Accuracy on definitions, theorems, routine reasoning Compare answer against the standard result
    Advanced Whether it can construct a complete proof or find a counterexample Proof verifier plus human spot checks
    Frontier Whether it can produce new results or solve open problems Mostly human review; machine used only for first-pass filtering

    The key action is to record which layer each capability curve breaks down at. That is far more informative than a single aggregate score.

    5.2 Build a verifiable evaluation set

    • Solve-hard, verify-easy first: prioritize problems where solving is hard and verification is cheap.
    • Layered mix: baseline problems provide stability, advanced problems create discrimination, frontier problems reveal the ceiling.
    • Contamination resistance: keep a private problem bank, periodically release structurally similar variants, and watch for score gaps.
    • Multi-sample evaluation: sample each problem multiple times and report both pass rate and stability, so you can distinguish “got it right by luck” from “gets it right consistently.”

    5.3 Build an engineering pipeline for evaluation

    A working evaluation system typically includes:

    1. Task orchestration: use a container platform to spin up isolated execution environments per problem in parallel, keeping results reproducible.
    2. Archiving data and artifacts: store problems, prompts, model outputs, and verification logs together in object storage so runs can be reviewed later.
    3. Observability: use logging and monitoring/alerting to track long-tail issues such as timeouts, output-format parse failures, and verifier exceptions.
    4. Regression runs: after every model or prompt change, rerun the full suite so you build trend curves rather than isolated scores.

    At the infrastructure level, generic cloud product categories such as container platforms, object storage, logging services, and monitoring and alerting — offered by platforms including Baidu AI Cloud — can support this kind of evaluation pipeline. For specific product capabilities and pricing rules, refer to the official documentation.

    5.4 Design scoring functions that resist score-gaming

    1. def score(samples, verifier):
    2. # Multi-sample: separate stable capability from accidental correctness
    3. passed = [verifier(s) for s in samples]
    4. rate = sum(passed) / len(passed)
    5. # Penalty: format violations, timeouts, citing undefined results
    6. penalty = mean(s.penalties for s in samples)
    7. return {"pass_rate": rate, "stability": rate * (1 - penalty)}

    With pass@1 alone, a model can score by brute-force luck. Only after you add multi-sampling and a penalty term does the score start to reflect the stability of reasoning.

    6. Limitations and Outlook

    • Limited coverage: 100 problems, a single discipline, and machine-verifiability — these three facts bound the applicability of the conclusions.
    • Grading itself can be wrong: when a verifier is flawed, “passed” does not equal “correct,” so human spot checks are needed as a backstop.
    • Open problems have no lower bound: saying a model “can’t solve it” is easy; saying “how far off is it” is hard. Future evaluations need to report the quality of the intermediate results models produce on open problems.
    • From grading to co-research: when verification cost is far below solving cost, AI’s sensible role is a high-throughput candidate generator, while human researchers raise good questions, filter, and make the final call.

    7. Conclusion

    The greatest contribution of this exam is not the scores it assigned to models, but a scalable evaluation paradigm for research-level work: problems must be verifiable, answers must be decidable, and scores must distinguish “can do exercises” from “can do research.”

    For enterprises, rather than watching leaderboard rankings, it is better to build your own verifiable evaluation set — turn the hardest problems in your business into problems, so every model iteration has something concrete to measure against. As for whether AI can independently do mathematical research, this exam’s answer is measured: not yet, but it is on the way. And knowing exactly how far along it is matters more than any leaderboard.