Communications of the ACM
Complexity Theory's 50-Year Journey to the Limits of Knowledge
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