https://complexityzoo.net/index.php?title=Complexity_Zoo:V&feed=atom&action=historyComplexity Zoo:V - Revision history2024-03-29T06:41:42ZRevision history for this page on the wikiMediaWiki 1.35.0https://complexityzoo.net/index.php?title=Complexity_Zoo:V&diff=81&oldid=prevAdmin: 1 revision: Complexity zoo import.2012-11-18T03:10:33Z<p>1 revision: Complexity zoo import.</p>
<p><b>New page</b></p><div>__NOTOC__<br />
{{CZ-Letter-Menu|V}}<br />
<br />
<br />
===== <span id="vck" style="color:red">VC<sub>k</sub></span>: Verification Class With A Circuit of Depth K =====<br />
<ul><br />
<li> For k = 0, VC<sub>0</sub> is the class of compressible languages.<br />
<li> For k = 1, VC<sub>1</sub> 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.)<br />
<li> For k &ge; 2, VC<sub>k</sub> 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.<br />
</ul><br />
VC<sub>0</sub> &sube; VC<sub>OR</sub> &sube; VC<sub>1</sub> &sube; VC<sub>2</sub> &sube; VC<sub>3</sub> &hellip;<br />
<br />
Introduced in [[zooref#hn06|[HN06]]]; see there for formal definitions.<br />
<br />
----<br />
<br />
===== <span id="vcor" style="color:red">VC<sub>or</sub></span>: Verification Class With OR =====<br />
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.)<br />
<br />
Introduced in [[zooref#hn06|[HN06]]].<br />
<br />
See also [[#vck|VC<sub>k</sub>]].<br />
<br />
----<br />
<br />
===== <span id="vnc" style="color:red">VNC<sub>k</sub></span>: Valiant [[Complexity Zoo:N#nc|NC]] Over Field k =====<br />
Has the same relation to [[#vp|VP<sub>k</sub>]] as [[Complexity Zoo:N#nc|NC]] does to [[Complexity Zoo:P#p|P]].<br />
<br />
More formally, the class of [[#vp|VP<sub>k</sub>]] problems computable by a straight-line program of depth polylogarithmic in n.<br />
<br />
Surprisingly, VNC<sub>k</sub> = [[#vp|VP<sub>k</sub>]] for any k [[zooref#vsb83|[VSB+83]]].<br />
<br />
----<br />
<br />
===== <span id="vnp" style="color:red">VNP<sub>k</sub></span>: Valiant [[Complexity Zoo:N#np|NP]] Over Field k =====<br />
A superclass of [[#vp|VP<sub>k</sub>]] in Valiant's algebraic complexity theory, but not <i>quite</i> the analogue of [[Complexity Zoo:N#np|NP]].<br />
<br />
A problem is in VNP<sub>k</sub> if there exists a polynomial p with the following properties:<br />
<ul><br />
<li>p is computable in [[#vp|VP<sub>k</sub>]]; that is, by a polynomial-size straight-line program.</li><br />
<li>The inputs to p are constants c<sub>1</sub>,...,c<sub>m</sub>,e<sub>1</sub>,...,e<sub>h</sub> and indeterminates X<sub>1</sub>,...,X<sub>n</sub> over the base field k.</li><br />
<li>When p is summed over all 2<sup>h</sup> possible assignments of {0,1} to each of e<sub>1</sub>,...,e<sub>h</sub>, the result is some specified polynomial q.</li><br />
</ul><br />
Originated in [[zooref#val79b|[Val79b]]].<br />
<br />
If the field k has characteristic greater than 2, then the permanent of an n-by-n matrix of indeterminates is VNP<sub>k</sub>-complete under a type of reduction called p-projections ([[zooref#val79b|[Val79b]]]; see also [[zooref#bur00|[Bur00]]]).<br />
<br />
A central conjecture is that for all k, [[#vp|VP<sub>k</sub>]] is not equal to VNP<sub>k</sub>. B&uuml;rgisser [[zooref#bur00|[Bur00]]] shows that if this were false then:<br />
<ul><br />
<li>If k is finite, [[Complexity Zoo:N#nc2|NC<sup>2</sup>]]/poly = [[Complexity Zoo:P#ppoly|P/poly]] = [[Complexity Zoo:N#nppoly|NP/poly]] = [[Complexity Zoo:P#ph|PH]]/poly.</li><br />
<li>If k has characteristic 0, then assuming the Generalized Riemann Hypothesis (GRH), [[Complexity Zoo:N#nc|NC]]<sup>3</sup>/poly = [[Complexity Zoo:P#ppoly|P/poly]] = [[Complexity Zoo:N#nppoly|NP/poly]] = [[Complexity Zoo:P#ph|PH]]/poly, and [[Complexity Zoo:Symbols#sharpp|#P]]/poly = [[Complexity Zoo:F#fp|FP]]/poly.</li><br />
</ul><br />
In both cases, [[Complexity Zoo:P#ph|PH]] collapses to [[Complexity Zoo:S#sigma2p|&#931;<sub>2</sub>P]].<br />
<br />
----<br />
===== <span id="vp" style="color:red">VP<sub>k</sub></span>: Valiant [[Complexity Zoo:P#p|P]] Over Field k =====<br />
The class of efficiently-solvable problems in Valiant's algebraic complexity theory.<br />
<br />
More formally, the input consists of constants c<sub>1</sub>,...,c<sub>m</sub> and indeterminates X<sub>1</sub>,...,X<sub>n</sub> over a base field k (for instance, the complex numbers or Z<sub>2</sub>). The desired output is a collection of polynomials over the X<sub>i</sub>'s. The complexity is the minimum number of pairwise additions, subtractions, and multiplications needed by a straight-line program to produce these polynomials. VP<sub>k</sub> is the class of problems whose complexity is polynomial in n. (Hence, VP<sub>k</sub> is a nonuniform class, in contrast to [[Complexity Zoo:P#pc|P<sub>C</sub>]] and [[Complexity Zoo:P#pr2|P<sub>R</sub>]].)<br />
<br />
Originated in [[zooref#val79b|[Val79b]]]; see [[zooref#bur00|[Bur00]]] for more information.<br />
<br />
Contained in [[#vnp|VNP<sub>k</sub>]] and [[#vqp|VQP<sub>k</sub>]], and contains [[#vnc|VNC<sub>k</sub>]].<br />
<br />
----<br />
===== <span id="vpl" style="color:red">VPL</span>: Visibly pushdown languages =====<br />
<br />
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. <br />
<br />
Originated in [[zooref#am04|[AM04]]]. See also [[zooref#am09|[AM09]]].<br />
<br />
Properly contains [[#reg|REG]]. Properly contained in [[#dcfl|DCFL]].<br />
<br />
----<br />
<br />
===== <span id="vqp" style="color:red">VQP<sub>k</sub></span>: Valiant [[Complexity Zoo:Q#qp|QP]] Over Field k =====<br />
Has the same relation to [[#vp|VP<sub>k</sub>]] as [[Complexity Zoo:Q#qp|QP]] does to [[Complexity Zoo:P#p|P]].<br />
<br />
Originated in [[zooref#val79b|[Val79b]]].<br />
<br />
The determinant of an n-by-n matrix of indeterminates is VQP<sub>k</sub>-complete under a type of reduction called qp-projections (see [[zooref#bur00|[Bur00]]] for example). It is an open problem whether the determinant is [[#vp|VP<sub>k</sub>]]-complete.</div>Admin