Sign In

Communications of the ACM

ACM News

Complexity Theory's 50-Year Journey to the Limits of Knowledge

View as: Print Mobile App Share:
Despite decades of effort by researchers in the field of computational complexity theory, a resolution to the P versus NP question has remained elusive.

Complexity theorists are confronting their most puzzling problem yet: complexity theory itself.

Credit: Tommy Parker/Quanta Magazine

In the first week of the fall semester in 2007, Marco Carmosino dragged himself to a math class required for all computer science majors at the University of Massachusetts, Amherst. Carmosino, a sophomore, was considering dropping out of college to design video games. Then the professor posed a simple question that would change the course of his life: How do you know math actually works?

"That made me sit up and pay attention," recalled Carmosino, now a theoretical computer scientist at IBM. He signed up for an optional seminar on the work of Kurt Gödel, whose dizzying self-referential arguments first exposed the limits of mathematical reasoning and created the foundation for all future work on the fundamental limits of computation. It was a lot to take in.

"I 100% did not understand," Carmosino said. "But I knew that I wanted to."

Today, even seasoned researchers find understanding in short supply when they confront the central open question in theoretical computer science, known as the P versus NP problem. In essence, that question asks whether many computational problems long considered extremely difficult can actually be solved easily (via a secret shortcut we haven't discovered yet), or whether, as most researchers suspect, they truly are hard. At stake is nothing less than the nature of what's knowable.

From Quanta Magazine
View Full Article



No entries found