Computational complexity

A major advance in computational complexity reveals deep connections between the classes of problems that computers can — and can’t — possibly do.

Subhash Khot’s bold conjecture is helping mathematicians explore the precise limits of computation.

An infinitesimal advance in the traveling salesman problem breathes new life into the search for improved approximate solutions.