Can Large Language Models Solve Open Problems in Theoretical Computer Science?
This article examines whether Large Language Models (LLMs) can solve open problems in theoretical computer science (TCS). It distinguishes between solving standardized problems and conducting actual research, highlights the core challenges in research-oriented evaluation, and proposes engineering workflows and evaluation design strategies to build reliable research-assistance systems.
What Does Theoretical Computer Science Study?
Theoretical Computer Science (TCS) studies the concept of “computation” itself. It concerns whether certain classes of problems can be solved by computers in principle, how much time and space are required, and the difficulty relationships between different problems. While engineers focus on system implementation, theoretical researchers focus on whether a specific path is destined to fail and the upper speed limits of optimal paths.
Conclusions in this field rely almost entirely on rigorous proofs. For a conclusion to be accepted, a complete logical derivation must be provided; experimental data and empirical judgments cannot replace proofs. Therefore, TCS is generally considered the intersection of mathematics and computer science.
Why Mathematics is a Pioneer Field for LLMs
The progress of Large Language Models (LLMs) in mathematics is notable for two main reasons. First, standard answers to math problems are definitive, allowing training and evaluation to yield clear accuracy rates. Second, the correctness of a proof can be machine-checked. Sudoku is an apt analogy: the process of filling in the grid may be difficult, but checking whether each cell complies with the rules is easy. Formal proof systems leverage this by writing derivation steps in a form that can be verified by a program.
These two points make mathematical capability one of the easiest achievements to gain public recognition. However, they imply a premise: the answers and judgment criteria for the problems already exist.
The Fundamental Difference Between Solving Problems and Research
Solving problems is similar to cooking with a recipe. The steps are given, and there is a recognized standard for the final taste. Research is more like developing a new dish without a recipe: it is uncertain which ingredient combinations work or which methods are feasible. The proposers of some problems do not even know the answers themselves.
Therefore, scores on standardized tests cannot directly infer research capabilities. A model capable of completing a large number of competition problems does not necessarily mean it can propose new proofs, discover new structures, or make progress on unsolved problems. Evaluating research capabilities requires designing separate questions and processes, rather than following the leaderboards for problem-solving.
Three Challenges in Research-Oriented Evaluation
First, open problems lack standard answers. If a conjecture remains unsolved, evaluators cannot provide a reference solution in advance; they must wait for subsequent researchers to verify the conclusion. Evaluation thus requires long-term participation from domain experts, resulting in long cycles and high costs.
Second, the cost of proof review is high. A model might output hundreds of pages of derivations. Even if each step appears reasonable, the whole might still harbor hidden logical flaws. Manual page-by-page checking is inefficient, and experts’ attention is limited.
Third, it is difficult to self-prove the credibility of a conclusion. If a model claims to have solved a long-standing problem, the correctness cannot be judged solely by the output text. “Claiming” and “verifying” must be separated, and the verification process must be placed in a reproducible workflow.
Engineering Approaches to Cope with Challenges
Faced with the above challenges, a research-assistance system can be broken down into several stages: generating candidate conclusions, automatically checking formalizable parts, grading non-automatable parts for manual review, and completely retaining process records. The code below is a simplified example illustrating the connection between these stages.
from dataclasses import dataclass, field@dataclassclass Claim:statement: strproof_steps: list[str]formalized: bool = Falseverified: bool = Falsenotes: list[str] = field(default_factory=list)def auto_check(claim: Claim) -> bool:# Placeholder logic: an actual system should call a formal proof checker# to verify each formalizable step, returning True only if all pass.return claim.formalizeddef review_pipeline(claims: list[Claim]) -> dict[str, list[Claim]]:result = {"accepted": [], "needs_expert": [], "rejected": []}for c in claims:if not c.proof_steps:c.notes.append("Missing proof steps")result["rejected"].append(c)elif auto_check(c):c.verified = Trueresult["accepted"].append(c)else:result["needs_expert"].append(c)return result
This code only demonstrates the structure. In a real system, auto_check needs to integrate specialized formal proof tools, and the needs_expert queue must be handled by reviewers with domain backgrounds.
Recommendations for Evaluation Design
- Tiered Questions. Divide questions into three categories: reproduction of known conclusions, application of known methods, and attempts at unsolved problems. Record scores separately to avoid masking differences with a single score.
- Process Logging. Require the model to provide reasoning steps and citations for its basis, making it easier to locate where errors occur.
- Blind Review. Reviewers should not know which system the conclusion comes from, reducing preconceived judgments.
- Negative Samples. Include intentionally designed incorrect proofs to test whether the review process can identify problems.
These designs can make evaluation results closer to true research capabilities, rather than just templated problem-solving skills.
Practical Implications for Users
For research and development teams, current LLMs are more suitable for auxiliary tasks such as literature review, counterexample searching, and preliminary organization of proof steps. When facing open problems, conclusions provided by the model should be treated as hypotheses awaiting verification. Once a conclusion enters the formal process, expert review and formal verification remain indispensable steps.
