Complexity Zoo:V

From Qwiki

Jump to: navigation, search

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 - VCOR - VNCk - VNPk - VPk - VQPk


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.

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.

Retrieved from "http://qwiki.stanford.edu/wiki/Complexity_Zoo:V"
Personal tools