Class Description

VNP_k: Valiant NP Over Field k

A superclass of VP_k in Valiant's algebraic complexity theory, but not quite the analogue of NP.

A problem is in VNP_k if there exists a polynomial p with the following properties:

• p is computable in VP_k; that is, by a polynomial-size straight-line program.
• The inputs to p are constants c₁,...,c_m,e₁,...,e_h and indeterminates X₁,...,X_n over the base field k.
• When p is summed over all 2^h possible assignments of {0,1} to each of e₁,...,e_h, the result is some specified polynomial q.

Originated in [Val79b].

If the field k has characteristic greater than 2, then the permanent of an n-by-n matrix of indeterminates is VNP_k-complete under a type of reduction called p-projections ([Val79b]; see also [Bur00]).

A central conjecture is that for all k, VP_k is not equal to VNP_k. Bürgisser [Bur00] shows that if this were false then:

• If k is finite, NC²/poly = P/poly = NP/poly = PH/poly.
• If k has characteristic 0, then assuming the Generalized Riemann Hypothesis (GRH), NC³/poly = P/poly = NP/poly = PH/poly, and #P/poly = FP/poly.

In both cases, PH collapses to Σ₂P.

Linked From

NP_C: NP Over The Complex Numbers

An analog of NP for Turing machines over a complex number field.

Defined in [BCS+97].

It is unknown whether P_C = NP_C, nor are implications known among this question, P_R versus NP_R, and P versus NP.

However, [CKK+95] show that if P/poly does not equal NP/poly then P_C does not equal NP_C.

[BCS+97] show the following striking result. For a positive integer n, let t(n) denote the minimum number of additions, subtractions, and multiplications needed to construct n, starting from 1. If for every sequence {n_k} of positive integers, t(n_k k!) grows faster than polylogarithmically in k, then P_C does not equal NP_C.

See also VNP_k.

More about...

NP_R: NP Over The Reals

An analog of NP for Turing machines over a real number field.

Defined in [BCS+97].

It is unknown whether P_R = NP_R, nor are implications known among this question, P_C versus NP_C, and P versus NP.

Also, in contrast to the case of NP_C, it is an open problem to show that P/poly distinct from NP/poly implies P_R distinct from NP_R. The difference is that in the real case, a comparison (or greater-than) operator is available, and it is not known how much power this yields in comparison to the complex case.

See also VNP_k.

More about...

VP_k: Valiant P Over Field k

The class of efficiently-solvable problems in Valiant's algebraic complexity theory.

More formally, the input consists of constants c₁,...,c_m and indeterminates X₁,...,X_n over a base field k (for instance, the complex numbers or Z₂). The desired output is a collection of polynomials over the X_i's. The complexity is the minimum number of pairwise additions, subtractions, and multiplications needed by a straight-line program to produce these polynomials. VP_k is the class of problems whose complexity is polynomial in n. (Hence, VP_k is a nonuniform class, in contrast to P_C and P_R.)

Originated in [Val79b]; see [Bur00] for more information.

Contained in VNP_k and VQP_k, and contains VNC_k.

More about...