Start here · 5-minute guide

How AI is changing theoretical computer science

AI is becoming a useful research tool in some clearly defined tasks. It is not a magic machine that automatically discovers and proves every truth. This guide explains the difference in plain language.

The short answer: AI is best supported today as a helper for searching, generating candidates, writing formal proofs and checking parts of a larger argument. Humans still decide what to ask, what the result means, and whether the wider claim is justified.

See verified examples Learn the four areas

First, four words

You do not need a PhD to follow the discussion.

Theoretical computer science asks what computers can do, how much time and memory a task needs, and how we can prove those answers.

Algorithm: A recipe: a step-by-step way to solve a problem. A faster recipe can matter even when both recipes eventually give the right answer.
Proof: A step-by-step argument that shows why a statement must be true. In formal mathematics, a computer can check the steps.
Complexity: The study of how the cost of a task grows when the input gets larger. A task can be solvable in principle but still be too expensive in practice.
Formal proof: A proof written in a precise language that software such as Lean can check, rather than relying only on a convincing-looking explanation.

What has actually changed

Four areas, four different levels of evidence.

The important question is not simply “can AI do this?” It is “which part can it do, in what setting, and who checked the result?”

Peer-reviewed

Finding algorithms

What it can do: search for candidate constructions inside a defined mathematical problem.

What must happen next: a person or checker must verify that the construction is correct and compare it with the right baseline.

What it does not prove: that every algorithm problem is now easy to solve.

Peer-reviewed

Searching for proofs

What it can do: search for a formal proof in a proof assistant, with the assistant checking each step.

What must happen next: researchers still choose the problem, the formal setting and the meaning of success.

What it does not prove: that solving narrow examples means AI can solve open research questions.

Demonstrated

Supplying proof pieces

What it can do: find a finite object that fits inside a larger proof framework designed by humans.

What must happen next: check the object, then show that the existing framework really produces the claimed conclusion.

What it does not prove: that the whole complexity-theory problem has been solved.

Contested

Changing research work

What is visible: tools can help with searching, coding, formalisation and checking parts of a project.

What is uncertain: how these task-level changes affect the total number of jobs, career paths and the quality of research.

What we will not do: turn a few examples into an unsupported forecast about replacing researchers.

The hard boundary

A useful result inside a box is still inside a box.

Most misleading headlines come from removing one of these limits:

A construction is not a universal theorem. Finding one valid object does not explain how to find every object.
A benchmark is not a proof. A high score can show that a system is good at a test, but it does not show that every answer is true.
A solved example is not a research programme. A system can succeed on a well-scoped problem while failing on the next question.
A checker checks the proof, not the story. The formal statement must match the claim being made in the headline.

Keep going

Now choose what you want to inspect.

Verified breakthroughsSee what has evidence and what the evidence stops short of proving. Career outlookSeparate changing work tasks from unsupported job forecasts. Claim checkUse five questions before believing a viral AI discovery headline.