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.
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.