Algebraic P and NP
The most interesting open problem in computational complexity theory is the P vs. NP problem. Roughly, this problem is to determine whether an advice is really helpful, or whether we do not really need advice. In his seminal work Valiant suggested an algebraic analog of this problem, the VP vs. VNP problem.
The class VP is the algebraic analog of P; it is the class of polynomials f of polynomial degree that have polynomial size circuits. The class VNP is the analog of NP. VNP can be thought of as the class of polynomials f of polynomial degree such that given a monomial we can determine its coefficient in f efficiently, with a polynomial size circuit.
One of the basic notions in complexity theory is the notion of completeness. Given a class of polynomials (such as VP or VNP), a complete polynomial f for this class is a polynomial with two properties: (1) it is part of the class, and (2) any other polynomial g in the class is easier than f, in the sense that if f has a small circuit then so does g. Valiant showed that the permanent is complete for the class VNP. So in order to show that VP is not equal to VNP, one needs to show that the permanent does not have polynomial size circuits. This remains an outstanding open problem.
Read more about this topic: Arithmetic Circuit Complexity
Famous quotes containing the word algebraic:
“I have no scheme about it,—no designs on men at all; and, if I had, my mode would be to tempt them with the fruit, and not with the manure. To what end do I lead a simple life at all, pray? That I may teach others to simplify their lives?—and so all our lives be simplified merely, like an algebraic formula? Or not, rather, that I may make use of the ground I have cleared, to live more worthily and profitably?”
—Henry David Thoreau (1817–1862)