Class Description

VNPk: Valiant NP Over Field k

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.

Linked From

NPC: 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 PC = NPC, nor are implications known among this question, PR versus NPR, and P versus NP.

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

[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 {nk} of positive integers, t(nk k!) grows faster than polylogarithmically in k, then PC does not equal NPC.

See also VNPk.

More about...


NPR: NP Over The Reals

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

Defined in [BCS+97].

It is unknown whether PR = NPR, nor are implications known among this question, PC versus NPC, and P versus NP.

Also, in contrast to the case of NPC, it is an open problem to show that P/poly distinct from NP/poly implies PR distinct from NPR. 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 VNPk.

More about...


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