How AI Is Affecting Theoretical Computer Science—and What It Can Prove

AI is changing theoretical computer science by helping researchers discover algorithms, search for mathematical proofs, and investigate the limits of computation. Its most reliable contributions come when a proposed result can be checked independently—by a proof assistant, a rigorous mathematical argument, or a program that evaluates a precisely defined problem. AI is a research tool, not a substitute for proof.

The impact goes both ways. Theoretical computer science also supplies the ideas needed to understand what AI systems can learn, how much computing they require, and why an impressive answer is not necessarily a correct one.

What does theoretical computer science study?

Theoretical computer science (TCS) asks what computers can do, how efficiently they can do it, and how to establish that an algorithm works. Its core areas include algorithms, computational complexity, logic, cryptography, automata, and learning theory.

Consider a delivery-routing problem. Software engineering might focus on building a useful route planner. A theoretician asks whether there is an algorithm that always finds the best route, how its running time grows with the number of stops, and what guarantees are possible if an approximate route is acceptable. These questions involve more than writing functional code.

1. AI is helping discover better algorithms

A traditional algorithm designer develops an idea, proves properties about it, and tests it. AI systems can now help explore a much larger space of candidate procedures. The productive pattern is generate, evaluate, and refine: a model proposes changes, an automated evaluator scores them, and promising candidates are improved further.

Google DeepMind's AlphaEvolve is a concrete example. In research announced in May 2025, the system combined language models with automated evaluation to search for algorithms. Its researchers reported a method for multiplying two 4-by-4 complex-valued matrices using 48 scalar multiplications, improving a longstanding result for that specific setting. The team's original AlphaEvolve research paper describes the discovery and its evaluation.

That result is meaningful, but it does not imply that all matrix multiplication suddenly became faster. A mathematical improvement for a particular operation or matrix size may require additional engineering—and analysis of larger cases—before it changes everyday software performance.

2. AI is becoming a partner in theorem proving

Theoretical results often depend on long chains of reasoning. Language models can suggest lemmas, identify promising proof strategies, and translate informal mathematical ideas into a formal language. Proof assistants such as Lean can then check whether a formally stated argument follows the allowed rules.

In 2024, Google DeepMind's AlphaProof and AlphaGeometry 2 solved four of six International Mathematical Olympiad problems, reaching a silver-medal-level score. AlphaProof used formal reasoning in Lean, with experts manually formalizing the relevant competition problems. The peer-reviewed AlphaProof study published in November 2025 documents the system and its limitations.

In 2025, a more advanced Gemini Deep Think system reached gold-medal-level performance on the Olympiad problems in natural language, according to results evaluated by the competition's coordinators. That is evidence of stronger mathematical problem-solving, not proof that AI can independently settle every open question in computer science. See DeepMind’s account of the 2025 evaluation.

One crucial distinction remains: a formal checker validates a proof of the statement encoded in its system. Researchers must still ensure that the formal statement faithfully represents the intended real-world or mathematical claim and that any imported assumptions are appropriate.

3. AI is contributing directly to complexity theory

Computational complexity asks why some problems are easy, others are expensive, and certain approximations may be impossible under standard assumptions. AI can help by discovering the small mathematical constructions that underpin much larger proofs.

In September 2025, Google researchers described using AlphaEvolve to identify computer-checkable combinatorial structures. Those structures strengthened results involving MAX-4-CUT approximation hardness and properties of random graphs. The important step was not simply finding a good example: researchers could insert the verified finite structure into an established proof framework to obtain a general theorem. Their research explanation of AI-assisted complexity theory explains this method.

A major 2026 claim still needs independent scrutiny

On October 26, 2026, OpenAI announced that an internal AI system had produced a purported refutation of the Exponential Time Hypothesis (ETH), a widely used conjecture about how rapidly the difficulty of certain satisfiability problems grows. OpenAI published a manuscript and a Lean formalization and said an external group of complexity theorists would lead an open examination of the result. As of October 30, 2026, that independent examination was not reported as complete in the announcement.

This is an important research claim under review, not a settled conclusion that ETH is false. Even if a subexponential algorithm is validated, it would not by itself establish that P equals NP or make hard optimization problems easy in practice. For the original announcement and its verification plan, see OpenAI’s October 26 research release.

4. Theoretical computer science is helping explain AI itself

While AI helps investigate theory, theoretical tools provide a more disciplined way to study AI. Learning theory examines when performance on training examples should extend to new data. Complexity theory studies the computational resources a learning method needs. Formal methods clarify which properties can be verified and which remain unproven.

For example, a model might correctly answer thousands of arithmetic questions yet fail when the number of digits exceeds the range it saw during training. Accuracy on familiar examples does not demonstrate an algorithm that works for every input length. Researchers therefore test changes in problem size, structure, and distribution rather than assuming a high benchmark score indicates general reasoning.

A 2025 IBM Research perspective explores how algebraic circuit complexity can help formalize tests of algorithmic generalization—whether models learn underlying procedures rather than only familiar patterns. See the original research perspective.

What changes for researchers and students?

AI is most useful as an assistant in a workflow that preserves mathematical accountability:

1. State the exact problem. Define the inputs, assumptions, and desired theorem or performance measure.
2. Use AI to generate candidates. Ask for algorithms, proof sketches, counterexamples, or finite constructions.
3. Run independent checks. Test candidate code, use formal verification where possible, and scrutinize every unproven assertion.
4. Establish the general result. Show why a finding applies beyond sampled inputs or a single benchmark.
5. Report the limitations. Distinguish a faster implementation from better asymptotic complexity and an independently checked proof from an unverified proposal.

Suppose an AI tool proposes a faster graph algorithm. Timing it on 100 generated graphs may be a useful first experiment, but it is not a proof of correctness, a worst-case running-time guarantee, or evidence that all graphs benefit. Those claims require separate reasoning. The same distinction applies to model-generated theorems: plausible text is a hypothesis until a sound proof or appropriate verification supports it.

Will AI replace theoretical computer scientists?

There is no evidence that the field no longer needs human researchers. AI can accelerate search, propose unfamiliar constructions, and reduce tedious parts of formal proof development. Humans remain essential for choosing meaningful questions, deciding which assumptions matter, interpreting results, detecting mismatches between formal models and intended claims, and evaluating broader consequences.

The central change is the research process. Theoretical computer science is moving toward closer collaboration between human mathematical judgment, machine-generated proposals, and independently checkable evidence. The exciting prospect is not that AI can make any theorem true; it is that researchers may be able to investigate more ideas rigorously than they could before.