The class of efficiently-solvable problems in Valiant's algebraic complexity theory.
More formally, the input consists of constants c1,...,cm and indeterminates X1,...,Xn over a base field k (for instance, the complex numbers or Z2). The desired output is a collection of polynomials over the Xi's. The complexity is the minimum number of pairwise additions, subtractions, and multiplications needed by a straight-line program to produce these polynomials. VPk is the class of problems whose complexity is polynomial in n. (Hence, VPk is a nonuniform class, in contrast to PC and PR.)
Originated in [Val79b]; see [Bur00] for more information.
Contained in VNPk and VQPk, and contains VNCk.
An analog of P for Turing machines over a complex number field.
Defined in [BCS+97].
An analog of P for Turing machines over a real number field.
Defined in [BCS+97].
Has the same relation to VPk as NC does to P.
More formally, the class of VPk problems computable by a straight-line program of depth polylogarithmic in n.
Surprisingly, VNCk = VPk for any k [VSB+83].
A superclass of VPk in Valiant's algebraic complexity theory, but not quite the analogue of NP.
A problem is in VNPk if there exists a polynomial p with the following properties:
Originated in [Val79b].
If the field k has characteristic greater than 2, then the permanent of an n-by-n matrix of indeterminates is VNPk-complete under a type of reduction called p-projections ([Val79b]; see also [Bur00]).
A central conjecture is that for all k, VPk is not equal to VNPk. Bürgisser [Bur00] shows that if this were false then:
In both cases, PH collapses to Σ2P.
Has the same relation to VPk as QP does to P.
Originated in [Val79b].
The determinant of an n-by-n matrix of indeterminates is VQPk-complete under a type of reduction called qp-projections (see [Bur00] for example). It is an open problem whether the determinant is VPk-complete.