What's up in

# computational complexity

## Latest Articles

### Landmark Computer Science Proof Cascades Through Physics and Math

Computer scientists established a new boundary on computationally verifiable knowledge. In doing so, they solved major open problems in quantum mechanics and pure mathematics.

### Computer Scientists Expand the Frontier of Verifiable Knowledge

The universe of problems that a computer can check has grown. The researchers’ secret ingredient? Quantum entanglement.

### Mathematicians Discover the Perfect Way to Multiply

By chopping up large numbers into smaller ones, researchers have rewritten a fundamental mathematical speed limit.

### In Quantum Games, There’s No Way to Play the Odds

These games combine quantum entanglement, infinity and impossible-to-calculate winning probabilities. But if researchers can crack them, they’ll reveal deep mathematical secrets.

### Major Quantum Computing Advance Made Obsolete by Teenager

18-year-old Ewin Tang has proven that classical computers can solve the “recommendation problem” nearly as fast as quantum computers. The result eliminates one of the best examples of quantum speedup.

### A Short Guide to Hard Problems

What’s easy for a computer to do, and what’s almost impossible? Those questions form the core of computational complexity. We present a map of the landscape.

### Finally, a Problem That Only Quantum Computers Will Ever Be Able to Solve

Computer scientists have been searching for years for a type of problem that a quantum computer can solve but that any possible future classical computer cannot. Now they’ve found one.

### First Big Steps Toward Proving the Unique Games Conjecture

The latest in a new series of proofs brings theoretical computer scientists within striking distance of one of the great conjectures of their discipline.

### One-Way Salesman Finds Fast Path Home

The real-world version of the famous “traveling salesman problem” finally gets a good-enough solution.