# Complexity Zoo:V

*Back to the Main Zoo* -
*Complexity Garden* -
*Zoo Glossary* -
*Zoo References*

*Complexity classes by letter:*
Symbols -
A -
B -
C -
D -
E -
F -
G -
H -
I -
J -
K -
L -
M -
N -
O -
P -
Q -
R -
S -
T -
U -
**V** -
W -
X -
Y -
Z

*Lists of related classes:*
Communication Complexity -
Hierarchies -
Nonuniform

VC_{k} -
VC_{OR} -
VNC_{k} -
VNP_{k} -
VP_{k} -
VPL -
VQP_{k}

##### VC_{k}: Verification Class With A Circuit of Depth K

- For k = 0, VC
_{0}is the class of compressible languages. - For k = 1, VC
_{1}is the class of languages that have local verification: they can be verified by testing only a small part of the instance. (Small means polynomial in the witness length and the log of the instance length.) - For k ≥ 2, VC
_{k}is the class of languages that can be verified by a circuit of depth k, with size polynomial in the witness length and instance length.

VC_{0} ⊆ VC_{OR} ⊆ VC_{1} ⊆ VC_{2} ⊆ VC_{3} …

Introduced in [HN06]; see there for formal definitions.

##### VC_{or}: Verification Class With OR

The class of languages that have verification presentable as the OR of m instances of SAT, each of size n. (m is the witness length of an instance and n is the instance length.)

Introduced in [HN06].

See also VC_{k}.

##### VNC_{k}: Valiant NC Over Field k

Has the same relation to VP_{k} as NC does to P.

More formally, the class of VP_{k} problems computable by a straight-line program of depth polylogarithmic in n.

Surprisingly, VNC_{k} = VP_{k} for any k [VSB+83].

##### 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
_{1},...,c_{m},e_{1},...,e_{h}and indeterminates X_{1},...,X_{n}over the base field k. - When p is summed over all 2
^{h}possible assignments of {0,1} to each of e_{1},...,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
^{2}/poly = P/poly = NP/poly = PH/poly. - If k has characteristic 0, then assuming the Generalized Riemann Hypothesis (GRH), NC
^{3}/poly = P/poly = NP/poly = PH/poly, and #P/poly = FP/poly.

In both cases, PH collapses to Σ_{2}P.

##### 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_{1},...,c_{m} and indeterminates X_{1},...,X_{n} over a base field k (for instance, the complex numbers or Z_{2}). 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}.

##### VPL: Visibly pushdown languages

The class of problems that can be decided by a visibly pushdown automaton. In a visibly pushdown automaton, all push and pop transitions have to be triggered by special alphabet symbols, and thus are visible in the input word. Nondeterminism does not add to the expressive power of this automaton model, and the complexity class is closed under all Boolean operations.

Originated in [AM04]. See also [AM09].

Properly contains REG. Properly contained in DCFL.

##### VQP_{k}: Valiant QP Over Field k

Has the same relation to VP_{k} as QP does to P.

Originated in [Val79b].

The determinant of an n-by-n matrix of indeterminates is VQP_{k}-complete under a type of reduction called qp-projections (see [Bur00] for example). It is an open problem whether the determinant is VP_{k}-complete.