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₀ is the class of compressible languages.
• For k = 1, VC₁ 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₀ ⊆ VC_OR ⊆ VC₁ ⊆ VC₂ ⊆ VC₃ …

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

---

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.

---

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.