https://complexityzoo.net/index.php?title=Complexity_Zoo:Symbols&feed=atom&action=history
Complexity Zoo:Symbols - Revision history
2024-03-29T11:18:45Z
Revision history for this page on the wiki
MediaWiki 1.35.0
https://complexityzoo.net/index.php?title=Complexity_Zoo:Symbols&diff=6767&oldid=prev
Jgrochow: /* #L: Sharp-L */ Added link to GapL and the GapL-completeness of det
2022-06-15T17:29:58Z
<p><span dir="auto"><span class="autocomment">#L: Sharp-L: </span> Added link to GapL and the GapL-completeness of det</span></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 17:29, 15 June 2022</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l49" >Line 49:</td>
<td colspan="2" class="diff-lineno">Line 49:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Has the same relation to [[Complexity Zoo:L#l|L]] as [[#sharpp|#P]] does to [[Complexity Zoo:P#p|P]].</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Has the same relation to [[Complexity Zoo:L#l|L]] as [[#sharpp|#P]] does to [[Complexity Zoo:P#p|P]].</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>&#35;L is contained in [[Complexity Zoo:D#det|DET]] [[zooref#aj93|[AJ93]]].</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>&#35;L is contained in <ins class="diffchange diffchange-inline">the function class version of </ins>[[Complexity Zoo:D#det|DET]] [[zooref#aj93|[AJ93]]]<ins class="diffchange diffchange-inline">. In fact, the determinant is [[Complexity Zoo:G#gapl|GapL]]-complete (see refs at [[Complexity Zoo:G#gapl|GapL]]), where [[Complexity Zoo:G#gapl|GapL]] consists of functions that are the difference of two &#35;L functions</ins>. </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>===== <span id="sharplpoly" style="color:red">#L/poly</span>: Nonuniform [[#sharpl|#L]] =====</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>===== <span id="sharplpoly" style="color:red">#L/poly</span>: Nonuniform [[#sharpl|#L]] =====</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Has the same relation to [[#sharpl|#L]] as [[Complexity Zoo:P#ppoly|P/poly]] does to [[Complexity Zoo:P#p|P]].</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Has the same relation to [[#sharpl|#L]] as [[Complexity Zoo:P#ppoly|P/poly]] does to [[Complexity Zoo:P#p|P]].</div></td></tr>
</table>
Jgrochow
https://complexityzoo.net/index.php?title=Complexity_Zoo:Symbols&diff=6500&oldid=prev
Watson: /* ⊕Pcc: Communication Complexity ⊕P */
2016-06-10T01:35:43Z
<p><span dir="auto"><span class="autocomment">⊕Pcc: Communication Complexity ⊕P</span></span></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 01:35, 10 June 2016</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l121" >Line 121:</td>
<td colspan="2" class="diff-lineno">Line 121:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>===== <span id="paritypcc" style="color:red">&#8853;P<sup>cc</sup></span>: Communication Complexity [[#parityp|&#8853;P]] =====</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>===== <span id="paritypcc" style="color:red">&#8853;P<sup>cc</sup></span>: Communication Complexity [[#parityp|&#8853;P]] =====</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">Is not contained in [[Complexity Zoo:U#uppcc|UPP<sup>cc</sup>]] [[zooref#for02|[For02]]].</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">Does not contain [[Complexity Zoo:Z#zppcc|ZPP<sup>cc</sup>]] if partial functions are allowed [[zooref#gpw16b|[GPW16b]]].</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">The complexity measure associated with &#8853;P<sup>cc</sup> is equivalent to the log of the rank of the communication matrix over GF(2).</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td></tr>
</table>
Watson
https://complexityzoo.net/index.php?title=Complexity_Zoo:Symbols&diff=6422&oldid=prev
Watson: /* ⊕Pcc: Communication Complexity ⊕P */
2016-06-09T16:11:11Z
<p><span dir="auto"><span class="autocomment">⊕Pcc: Communication Complexity ⊕P</span></span></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 16:11, 9 June 2016</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l120" >Line 120:</td>
<td colspan="2" class="diff-lineno">Line 120:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>===== <span id="paritypcc" style="color:red">&#8853;P<sup>cc</sup></span>: Communication Complexity [[<del class="diffchange diffchange-inline">Complexity Zoo:P</del>#parityp|&#8853;P]] =====</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>===== <span id="paritypcc" style="color:red">&#8853;P<sup>cc</sup></span>: Communication Complexity [[#parityp|&#8853;P]] =====</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td></tr>
</table>
Watson
https://complexityzoo.net/index.php?title=Complexity_Zoo:Symbols&diff=6419&oldid=prev
Watson at 16:08, 9 June 2016
2016-06-09T16:08:47Z
<p></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 16:08, 9 June 2016</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l117" >Line 117:</td>
<td colspan="2" class="diff-lineno">Line 117:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Equals [[Complexity Zoo:M#modkp|Mod<sub>2^m</sub>P]] for every positive integer m.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Equals [[Complexity Zoo:M#modkp|Mod<sub>2^m</sub>P]] for every positive integer m.</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">----</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">===== <span id="paritypcc" style="color:red">&#8853;P<sup>cc</sup></span>: Communication Complexity [[Complexity Zoo:P#parityp|&#8853;P]] =====</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>----</div></td></tr>
</table>
Watson
https://complexityzoo.net/index.php?title=Complexity_Zoo:Symbols&diff=6319&oldid=prev
Fgrosshans: /* ⊕L: Parity L */ Add link with stabilizer circuits, as per [AG04].
2015-03-03T13:37:51Z
<p><span dir="auto"><span class="autocomment">⊕L: Parity L: </span> Add link with stabilizer circuits, as per <a href="/Zooref#ag04" class="mw-redirect" title="Zooref">[AG04</a>].</span></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 13:37, 3 March 2015</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l88" >Line 88:</td>
<td colspan="2" class="diff-lineno">Line 88:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Solving a linear system over Z<sub>2</sub> is complete for &#8853;L [[zooref#dam90|[Dam90]]].</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Solving a linear system over Z<sub>2</sub> is complete for &#8853;L [[zooref#dam90|[Dam90]]].</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">The problem of simulating stabilizer circuits is complete for ⊕L [[zooref#ag04|[AG04]]].</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&#8853;L<sup>&#8853;L</sup> = &#8853;L [[zooref#bdh92|[BDH+92]]], [[zooref#hrv00|[HRV00]]].</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>&#8853;L<sup>&#8853;L</sup> = &#8853;L [[zooref#bdh92|[BDH+92]]], [[zooref#hrv00|[HRV00]]].</div></td></tr>
</table>
Fgrosshans
https://complexityzoo.net/index.php?title=Complexity_Zoo:Symbols&diff=75&oldid=prev
Admin: 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|Symbols}}<br />
<br />
<br />
<br />
===== <span id="01npc" style="color:red">0-1-NP<sub>C</sub></span>: Binary Restriction of [[Complexity Zoo:N#np|NP]] Over The Complex Numbers =====<br />
The intersection of [[Complexity Zoo:N#npc2|NP<sub>C</sub>]] with {0,1}<sup>*</sup> (i.e. the set of binary strings).<br />
<br />
Contains [[Complexity Zoo:N#np|NP]].<br />
<br />
Is contained in [[Complexity Zoo:P#pspace|PSPACE]], and in [[Complexity Zoo:A#am|AM]] assuming the Extended Riemann Hypothesis [[zooref#koi96|[Koi96]]].<br />
<br />
----<br />
===== <span id="1nauxpdap" style="color:red">1NAuxPDA<sup>p</sup></span>: One-Way [[Complexity Zoo:N#nauxpdap|NAuxPDA<sup>p</sup>]] =====<br />
Defined in [[zooref#bra77|[Bra77]]], where it was also shown that 1NAuxPDA<sup>p</sup> strictly contains [[Complexity Zoo:C#cfl|CFL]] and is strictly contained in [[Complexity Zoo:L#logcfl|LOGCFL]]. The class corresponds to the closure of [[Complexity Zoo:C#cfl|CFL]] under one-way log-space reductions.<br />
<br />
----<br />
===== <span id="2exp" style="color:red">2-EXP</span>: Double-Exponential Time =====<br />
See [[Complexity Zoo:E#eexp|EEXP]].<br />
<br />
----<br />
===== <span id="3sumhard" style="color:red">3SUM-hard</span>: Problems hard for [[Complexity Garden#3sum|3SUM]] =====<br />
Defined in {{zcite|GO95}}, '''3SUM-hard''' is the set of problems <math>P</math> for which [[Complexity Garden#3sum|3SUM]] is reducible to a constant number of instances of <math>P</math> with additional time <math>o(n^2)</math>, using a real RAM model of computation as opposed to a Turing machine. That is, a problem is 3SUM-hard if 3SUM is reducible to it in sub-quadratic time.<br />
<br />
Known to contain many problems from computational geometry, including:<br />
* '''3SUM'''': do there exist <math>a,b,c</math> such that <math>a+b=c</math>?<br />
* '''3-Points-On-Line''': given a set of points on the plane, does a line exist connecting three of them?<br />
<br />
In {{zcite|GO95}}, the authors list many more computational geometry problems in 3SUM-hard.<br />
<br />
Using a model of computation strictly weaker than the real RAM machine model, a lower bound of <math>\Omega(n^2)</math> has been shown, but this model is weak enough that not all problems in 3SUM-hard are even decidable under the model.<br />
<br />
----<br />
<br />
===== <span id="sharpac0" style="color:red">#AC<sup>0</sup></span>: Sharp-[[Complexity Zoo:A#ac0|AC<sup>0</sup>]] =====<br />
The class of functions from {0,1}<sup>n</sup> to nonnegative integers computed by polynomial-size constant-depth arithmetic circuits, using addition and multiplication gates and the constants 0 and 1.<br />
<br />
Contained in [[Complexity Zoo:G#gapac0|GapAC<sup>0</sup>]].<br />
<br />
----<br />
===== <span id="sharpga" style="color:red">#GA</span>: Graph Automorphism =====<br />
The class of problems (Karp-)reducible to counting the number of automorphisms of a graph.<br />
<br />
Counterpart of [[Complexity Zoo:G#ga|GA]].<br />
<br />
----<br />
<br />
===== <span id="sharpl" style="color:red">#L</span>: Sharp-L =====<br />
Has the same relation to [[Complexity Zoo:L#l|L]] as [[#sharpp|#P]] does to [[Complexity Zoo:P#p|P]].<br />
<br />
&#35;L is contained in [[Complexity Zoo:D#det|DET]] [[zooref#aj93|[AJ93]]].<br />
<br />
----<br />
===== <span id="sharplpoly" style="color:red">#L/poly</span>: Nonuniform [[#sharpl|#L]] =====<br />
Has the same relation to [[#sharpl|#L]] as [[Complexity Zoo:P#ppoly|P/poly]] does to [[Complexity Zoo:P#p|P]].<br />
<br />
----<br />
===== <span id="sharpp" style="color:red">#P</span>: Sharp-P or Number-P =====<br />
The class of function problems of the form "compute f(x)," where f is the number of accepting paths of an [[#np|NP]] machine.<br />
<br />
The canonical #P-complete problem is [[Complexity_Garden#sharpsat|#SAT]].<br />
<br />
Defined in [[zooref#val79|[Val79]]], where it was also shown that [[Complexity_Garden#sharpperfect_matching|#Perfect Matching]] (or equivalently, [[Complexity_Garden#permanent|Permanent]]) is #P-complete. What makes that interesting is that the associated decision problem [[Complexity_Garden#perfect_matching|Perfect Matching]] is in [[Complexity Zoo:P#p|P]].<br />
<br />
[[Complexity Zoo:P#ph|PH]] is in [[Complexity Zoo:P#psharpp|P<sup>#P</sup>]] [[zooref#tod89|[Tod89]]].<br />
<br />
Any function in #P can be approximated to within a polynomial factor in [[Complexity Zoo:B#bpp|BPP]] with [[Complexity Zoo:N#np|NP]] oracle [[zooref#sto85|[Sto85]]]. Likewise, any problem in #P can be approximated to within a constant factor <math>\epsilon</math> by a machine in [[Complexity Zoo:F#fp|FP]]<sup>||NP</sup> running in <math>\mathrm{poly}(n,\epsilon^{-1})</math> time [[zooref#su05|[SU05]]].<br />
<br />
----<br />
<br />
===== <span id="sharpwt" style="color:red">#W[t]</span>: Sharp-[[Complexity Zoo:W#wt|W[t]]] =====<br />
Roughly, the analogue of [[#sharpp|#P]] for parameterized complexity. I.e. the class of parameterized counting problems that are fixed-parameter parsimonious reducible to [[Complexity_Garden#sharpwsat|#WSAT]].<br />
Defined in [[zooref#fg02|[FG02]]], which should be consulted for the full definition. [[zooref#fg02|[FG02]]] also showed that there exist #W[1]-complete problems whose corresponding decision problems are fixed-parameter tractable (i.e. in [[Complexity Zoo:F#fpt|FPT]]).<br />
<br />
Complete problems for #W[1] include counting the paths or cycles of a given length in a graph and counting the chordless paths of a given length (the latter both under parsimonious and Turing reductions). Complete problems for #W[2] include the maximal chordless path problem. [[zooref#cf07|[CF07]]]<br />
----<br />
<br />
===== <span id="parityexp" style="color:red">&#8853;EXP</span>: Parity [[Complexity Zoo:E#exp|EXP]] =====<br />
The exponential-time analogue of [[#parityp|&#8853;P]].<br />
<br />
There exists an oracle relative to which &#8853;EXP = [[Complexity Zoo:Z#zpp|ZPP]] [[zooref#bbf98|[BBF98]]].<br />
<br />
----<br />
===== <span id="parityl" style="color:red">&#8853;L</span>: Parity [[Complexity Zoo:L#l|L]] =====<br />
Has the same relation to [[Complexity Zoo:L#l|L]] as [[#parityp|&#8853;P]] does to [[Complexity Zoo:P#p|P]].<br />
<br />
Contains [[Complexity Zoo:S#sl|SL]] [[zooref#kw93|[KW93]]].<br />
<br />
Solving a linear system over Z<sub>2</sub> is complete for &#8853;L [[zooref#dam90|[Dam90]]].<br />
<br />
&#8853;L<sup>&#8853;L</sup> = &#8853;L [[zooref#bdh92|[BDH+92]]], [[zooref#hrv00|[HRV00]]].<br />
<br />
----<br />
<br />
===== <span id="paritylpoly" style="color:red">&#8853;L/poly</span>: Nonuniform [[#parityl|&#8853;L]] =====<br />
Has the same relation to [[#parityl|&#8853;L]] as [[Complexity Zoo:P#ppoly|P/poly]] does to [[Complexity Zoo:P#p|P]].<br />
<br />
Contains [[Complexity Zoo:N#nlpoly|NL/poly]] [[zooref#gw96|[GW96]]].<br />
<br />
----<br />
<br />
===== <span id="parityp" style="color:red">&#8853;P</span>: Parity [[Complexity Zoo:P#p|P]] =====<br />
The class of decision problems solvable by an [[Complexity Zoo:N#np|NP]] machine such that<br />
<ol><br />
<li>If the answer is 'yes,' then the number of accepting paths is odd.</li><br />
<li>If the answer is 'no,' then the number of accepting paths is even.</li><br />
</ol><br />
Defined in [[zooref#pz83|[PZ83]]].<br />
<br />
Contains [[Complexity_Garden#graph_isomorphism|Graph Isomorphism]]; indeed, [[Complexity_Garden#graph_isomorphism|Graph Isomorphism]] is low for &#8853;P [[zooref#ak02|[AK02]]].<br />
<br />
Contains [[Complexity Zoo:F#fewp|FewP]] [[zooref#ch89|[CH89]]].<br />
<br />
There exists an oracle relative to which [[Complexity Zoo:P#p|P]] = &#8853;P but [[Complexity Zoo:P#p|P]] is not equal to [[Complexity Zoo:N#np|NP]] (and indeed [[Complexity Zoo:N#np|NP]] = [[Complexity Zoo:E#exp|EXP]]) [[zooref#bbf98|[BBF98]]].<br />
<br />
Equals [[Complexity Zoo:M#modkp|Mod<sub>2^m</sub>P]] for every positive integer m.<br />
<br />
----<br />
<br />
===== <span id="paritysac0" style="color:red">&#8853;SAC<sup>0</sup></span>: [[Complexity Zoo:A#ac0|AC<sup>0</sup>]] With Unbounded Parity Gates =====<br />
<br />
----<br />
===== <span id="paritysac1" style="color:red">&#8853;SAC<sup>1</sup></span>: [[Complexity Zoo:A#ac1|AC<sup>1</sup>]] With Unbounded Parity Gates =====<br />
The class of problems solvable by a nonuniform family of polynomial-size, polylog-depth circuits with unbounded-fanin [[Complexity_Garden#parity|XOR]] and bounded-fanin AND gates.<br />
<br />
Defined in [[zooref#gw96|[GW96]]], where it was also shown that &#8853;SAC<sup>1</sup> contains [[Complexity Zoo:S#sac1|SAC<sup>1</sup>]].</div>
Admin