“The Ultimate Limits of Computation”

Marco Carmosino says a lot of people are surprised to hear that he transferred to Hampshire to do what is, basically, math. He contends that the freedom to self-direct is just as beneficial for studying complexity theory as it is for photography, anthropology, biology, playwriting, or anything else.

"It gives you a lot of freedom to specialize as much as you want and get some real work done," he says. This independence is especially important for Carmosino's work in such a specific field.

Carmosino's Division III project deals with "P versus NP," the unanswered question of whether or not the solution to any problem can be verified by a computer as efficiently as a computer can find the solution itself. "This question has ramifications for all of mathematics," he says. "It's incredibly fascinating and it demonstrates just how much we don't know about what comes out of our systems of mathematical rules."

"I don't write software," Carmosino explains. "Theoretical computer science, and especially complexity theory, is sort of like theoretical physics of the computing world. We seek underlying principles that govern the ultimate limits of computation."

The project itself is a mathematical proof that separates a section of P (the class of problems that we already know a computer can efficiently solve) from the rest. Breaking P into smaller parts to figure out if P equals NP was proposed four decades ago by Michael Sipser, whose doctoral advisee David Mix Barrington is a computer science professor at the University of Massachusetts Amherst and the faculty committee chair for Carmosino's Div III. Barrington would propose the next section to separate.

After that, no one was able to separate another natural section of P from NP. Carmosino's proof, and a proof published in 1993, both come close to separating a small part of that section - the same one, although Carmosino notes that the two proofs have different flaws.

Carmosino plans to spend the summer expanding his proof—"because sometimes unexpected things happen, and I like that about math," he says—before publishing it. This fall he begins graduate school at the University of Massachusetts Amherst with a full-ride Bay State Fellowship. After that, Carmosino wants to go to Germany, because "this sort of stuff is very popular there. Well, in the sense that there are thirty or forty people doing it instead of fifteen on the East Coast here," he says.

Div III faculty committee: Barrington (chair), computer science professor Lee Spector; computer science visiting assistant professor Paul Dickson