Hard Questions, Hard Answers: Exploring the Nature of Hard Problems in Computer Science

Sunday - December 24 2023, 20:49 UTC - 11 months ago

This article explores advances made in the field of computer science in 2023. In particular, it focuses on the P versus NP problem and the emergence of large language models. These models are impressing us with their seemingly original pieces of text, but AI researchers are still grappling with the 'black box' problem of understanding their inner workings.

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.

Hard Questions, Hard Answers .

For 50 years, computer scientists have tried to solve the biggest open question in their field, known as "P versus NP." It asks, roughly, how hard certain hard problems are. And for 50 years, their attempts have ended in failure. Many times, just as they began to make progress with a new approach, they hit a barrier proving that the tactic would never work. Eventually, they began to wonder why it’s so hard to prove that some problems are hard. Their efforts to answer such inward-looking questions have blossomed into a subfield, called meta-complexity, which has provided the greatest insights into the question yet.

In an August article and a short documentary video, Quanta explained exactly what we know, how we know it and what we’re just starting to figure out when it comes to meta-complexity. At stake is not just the curiosity of the researchers involved: Resolving P versus NP could solve countless logistical problems, render all cryptography moot, and even speak to the ultimate nature of what’s knowable and what’s forever beyond our grasp.

The Powers of Large Language Models .

Get enough stuff together, and you might be surprised by what can happen. Water molecules create waves, flocks of birds swoop and soar as one, and unconscious atoms combine into life. Scientists call these "emergent beheviors" and, in June, a Quanta article explored how they show up, too, in the largest and most complex ever language models.

Fuelled by data and computation more than any single individual's experience, these sprawling language models absorb text, identify patterns, and spit out ideas and seemingly original pieces of text — a process that plays out something like the emergence of an unknown voice from an amalgamation of many.

The results can be impressive, thought-provoking, if not unsettling. But much of their inner workings still remain opaque. AI researchers still struggle with the "black box" problem: How to open up the machine learning "box" and make sense of what’s inside.