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
VCk: Verification Class With A Circuit of Depth K
- For k = 0, VC0 is the class of compressible languages.
- For k = 1, VC1 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, VCk 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.
VC0 ⊆ VCOR ⊆ VC1 ⊆ VC2 ⊆ VC3 …
Introduced in [HN06]; see there for formal definitions.
VCor: 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 VCk.
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].
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:
- p is computable in VPk; that is, by a polynomial-size straight-line program.
- The inputs to p are constants c1,...,cm,e1,...,eh and indeterminates X1,...,Xn over the base field k.
- When p is summed over all 2h possible assignments of {0,1} to each of e1,...,eh, 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 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:
- If k is finite, NC2/poly = P/poly = NP/poly = PH/poly.
- If k has characteristic 0, then assuming the Generalized Riemann Hypothesis (GRH), NC3/poly = P/poly = NP/poly = PH/poly, and #P/poly = FP/poly.
In both cases, PH collapses to Σ2P.
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.
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.
VQPk: Valiant QP Over Field k
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.