In 2023, artificial intelligence dominated popular culture — showing up in everything from internet memes to Senate hearings. Large language models such as those behind ChatGPT fueled a lot of this excitement, even as researchers still struggled to pry open the “black box” that describes their inner workings. Image generation systems also routinely impressed and unsettled us with their artistic abilities, yet these were explicitly founded on concepts borrowed from physics.

The year brought many other advances in computer science. Researchers made subtle but important progress on one of the oldest problems in the field, a question about the nature of hard problems referred to as “P versus NP.” In August, my colleague Ben Brubaker explored this seminal problem and the attempts of computational complexity theorists to answer the question: Why is it hard (in a precise, quantitative sense) to understand what makes hard problems hard? “It hasn’t been an easy journey — the path is littered with false turns and roadblocks, and it loops back on itself again and again,” Brubaker wrote. “Yet for meta-complexity researchers, that journey into an uncharted landscape is its own reward.”

The year was also full of more discrete but still important pieces of individual progress. Shor’s algorithm, the long-promised killer app of quantum computing, got its first significant upgrade after nearly 30 years. Researchers finally learned how to find the shortest route through a general type of network nearly as fast as theoretically possible. And cryptographers, forging an unexpected connection to AI, showed how machine learning models and machine-generated content must also contend with hidden vulnerabilities and messages.

Some problems, it seems, are still beyond our ability to solve — for now.