Some math problems submit quickly to efficient algorithms; others remain stubbornly unsolved. Understanding what makes a problem hard to solve is at the core of a field called algebraic complexity theory.
In recent work, a team of researchers including SFI Omidyar Fellow Joshua Grochow used the tools of algebraic complexity theory to chip away at an unsolved problem that's been bugging mathematicians since the 1950s.
The problem asks whether problems with solutions that can be quickly verified (“NP” problems) can also be quickly found by a computer algorithm (“P” problems). P versus NP is widely considered to be the most difficult open problem in mathematics and computer science — it's solution would profoundly improve our understanding of computation.
Mathematicians aren't likely close to resolving the P versus NP question. However, they're making inroads using a spectrum of tools, like algebraic complexity theory.
An example problem: Can one follow a path through a graph that touches each node once and only once, ending where it began? Such a circuit is called a Hamiltonian cycle. Although it's straightforward to use an algorithm to verify which paths are Hamiltonian cycles, it's nearly impossible to find the most efficient cycle for a given graph of any size.
The algebraic version of the NP problem above would ask, for example, how many cycles does the graph have? Researchers call this class of algebraic problems VNP. (The “V” honors computer scientist Leslie Valiant at Harvard University.)
“It's sort of the counting analog of NP,” says Grochow. Solving the "counting" version won't solve P versus NP, but it is “an important milestone on the way,” says Grochow. (The algebraic analog of the class of P problems, similarly, is called VP.)
His collaborators include Mrinal Kumar, Michael Saks, and Shubhangi Saraf, all from Rutgers University. In their work, published on the arXiv, they showed that certain techniques from algebraic complexity theory probably won't work against VP versus VNP. They're not the only ones using this approach: A separate, independent team of researchers (Michael Forbes from the Simons Institute for the Theory of Computing, and Amir Shpilka and Ben Lee Volk of Tel-Aviv University) recently came to the same conclusion independently and pushed these ideas even further. Their paper has been recently accepted at STOC '17, one of the top conferences for computer science theory.
Such findings may seem negative, but they're not. They help narrow the search for solutions. The work by Grochow and his collaborators is the algebraic analog of work published In the 1990s when computer scientists Alexander Razborov and Steven Rudich demonstrated that certain proofs can't crack P versus NP. Their results led to new insights about complexity classes that weren't obvious.
Often in math, figuring out what won't work is a step toward solving a stubborn problem.
Read the paper on the arXiv.