Class Description

VNCk: Valiant NC Over Field k

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

Linked From

VPk: Valiant P Over Field k

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.

More about...