Computational complexity

A theorem for coloring a large class of “perfect” mathematical networks could ease the way for a long-sought general coloring proof.

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.