For more than five decades, mathematicians and computer scientists have been chasing an answer to a problem that, to the uninitiated, looks suspiciously simple: Does P = NP?
Loosely translated, it asks whether NP problems – those with solutions that are hard to compute but easy to verify – are equivalent to P problems – those that can be solved quickly by a computer program. For a computer scientist, the question boils down to whether or not brute-force algorithms can be replaced by smarter, more efficient strategies.
NP problems show up in many fields, including science, business, mathematics, medicine, and engineering. If researchers can prove that P = NP, they can begin to pursue efficient algorithms to solve NP problems. But equivalency isn’t likely; most experts in the field expect that P and NP are not the same. The Clay Mathematics Institute, in Boston, has deemed this proof so important that it has offered a $1 million reward to its “prover.”
One research area focused on proving that P is not equal to NP is called Geometric Complexity Theory, or GCT. This approach recasts P versus NP as a geometric question, explains Josh Grochow, an Omidyar Fellow at SFI.
Imagine that all possible algorithmic problems take up some space; NP forms a blob within that space, and so does P. Given that setup, says Grochow, “we want to understand if one is contained in the other by understanding their geometry.”
Together with J. M. Landsberg from Texas A&M University and Jerzy Weyman from the University of Connecticut, Grochow has planned a December working group on GCT. His goal is to explore some of the stepping stones needed to understand the geometry of the big question.
“We have a good idea of the immediate questions we want to tackle,” he says. “We’re bringing in a lot of advanced math and techniques that haven’t been used much in computational complexity before.”
Read more about the working group "Geometric Complexity Theory."