https://complexityzoo.net/index.php?title=Complexity_Zoo:A&feed=atom&action=history
Complexity Zoo:A - Revision history
2024-03-28T08:57:39Z
Revision history for this page on the wiki
MediaWiki 1.35.0
https://complexityzoo.net/index.php?title=Complexity_Zoo:A&diff=6886&oldid=prev
ZTKing: /* Ack: Ackermann Time */
2023-10-25T04:16:32Z
<p><span dir="auto"><span class="autocomment">Ack: Ackermann Time</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 04:16, 25 October 2023</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l87" >Line 87:</td>
<td colspan="2" class="diff-lineno">Line 87:</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="ackermann" style="color:red">Ack</span>: Ackermann Time =====</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="ackermann" style="color:red">Ack</span>: Ackermann Time =====</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>Defined in [[zooref#sch16|[Sch16]]]. Let <math>F_0(x) = x+1</math> and <math>F_k(x) = F_{k-1}^x(x)</math> where <math>F_{k-1}^x(x)</math> is <math>F_{k-1}(x)</math> applied to itself <math>x</math> times. For example <math>F_1(x) = 2x + 1</math>, <del class="diffchange diffchange-inline">and </del><math>F_2(x) = 2^{x+1}(x + 1) - 1</math>. Then define, <math>F_\omega(x) = F_x(x)</math>, note that has <del class="diffchange diffchange-inline">about </del>the same growth rate as <math>A(x,x)</math> where A is the Ackermann function. This class is equal to [[Complexity Zoo:D#dtime|DTIME]](F<sub>ω</sub>(p(n))) over all primitive-recursive functions p(n). The class remains unchanged if we replace [[Complexity Zoo:D#dtime|DTIME]] with [[Complexity Zoo:D#ntime|NTIME]] or [[Complexity Zoo:D#dspace|DSPACE]].</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>Defined in [[zooref#sch16|[Sch16]]]. Let <math>F_0(x) = x+1</math> and <math>F_k(x) = F_{k-1}^x(x)</math> where <math>F_{k-1}^x(x)</math> is <math>F_{k-1}(x)</math> applied to itself <math>x</math> times. For example <math>F_1(x) = 2x + 1</math>, <math>F_2(x) = 2^{x+1}(x + 1) - 1</math><ins class="diffchange diffchange-inline">, etc</ins>. Then define, <math>F_\omega(x) = F_x(x)</math>, note that <ins class="diffchange diffchange-inline">this </ins>has the same growth rate as <math>A(x,x)</math> where A is the Ackermann function. This class is equal to [[Complexity Zoo:D#dtime|DTIME]](F<sub>ω</sub>(p(n))) over all primitive-recursive functions p(n). The class remains unchanged if we replace [[Complexity Zoo:D#dtime|DTIME]] with [[Complexity Zoo:D#ntime|NTIME]] or [[Complexity Zoo:D#dspace|DSPACE]].</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>Strictly contains [[Complexity Zoo:E#elementary|ELEMENTARY]], [[Complexity Zoo:T#tower|Tower]], and [[Complexity Zoo:P#pr|PR]]. Is strictly contained in [[Complexity Zoo:R#r|R]].</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>Strictly contains [[Complexity Zoo:E#elementary|ELEMENTARY]], [[Complexity Zoo:T#tower|Tower]], and [[Complexity Zoo:P#pr|PR]]. Is strictly contained in [[Complexity Zoo:R#r|R]].</div></td></tr>
</table>
ZTKing
https://complexityzoo.net/index.php?title=Complexity_Zoo:A&diff=6885&oldid=prev
ZTKing: Fixed alphabetization mistake
2023-10-25T00:25:10Z
<p>Fixed alphabetization mistake</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 00:25, 25 October 2023</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l82" >Line 82:</td>
<td colspan="2" class="diff-lineno">Line 82:</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>See also: [[Complexity Zoo:Q#qacc0|QACC<sup>0</sup>]] and [[Complexity Zoo:C#cc0|CC<sup>0</sup>]].</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>See also: [[Complexity Zoo:Q#qacc0|QACC<sup>0</sup>]] and [[Complexity Zoo:C#cc0|CC<sup>0</sup>]].</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="ackermann" style="color:red">Ack</span>: Ackermann Time =====</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;">Defined in [[zooref#sch16|[Sch16]]]. Let <math>F_0(x) = x+1</math> and <math>F_k(x) = F_{k-1}^x(x)</math> where <math>F_{k-1}^x(x)</math> is <math>F_{k-1}(x)</math> applied to itself <math>x</math> times. For example <math>F_1(x) = 2x + 1</math>, and <math>F_2(x) = 2^{x+1}(x + 1) - 1</math>. Then define, <math>F_\omega(x) = F_x(x)</math>, note that has about the same growth rate as <math>A(x,x)</math> where A is the Ackermann function. This class is equal to [[Complexity Zoo:D#dtime|DTIME]](F<sub>ω</sub>(p(n))) over all primitive-recursive functions p(n). The class remains unchanged if we replace [[Complexity Zoo:D#dtime|DTIME]] with [[Complexity Zoo:D#ntime|NTIME]] or [[Complexity Zoo:D#dspace|DSPACE]].</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;">Strictly contains [[Complexity Zoo:E#elementary|ELEMENTARY]], [[Complexity Zoo:T#tower|Tower]], and [[Complexity Zoo:P#pr|PR]]. Is strictly contained in [[Complexity Zoo:R#r|R]].</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 relationship between this class and [[Complexity Zoo:P#pr|PR]] is analogous to the relationship between [[Complexity Zoo:T#tower|Tower]] and [[Complexity Zoo:E#elementary|ELEMENTARY]]. That is, Ack contains problems "barely" outside of [[Complexity Zoo:P#pr|PR]] and, unlike [[Complexity Zoo:P#pr|PR]], has complete problems.</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 reachability problems for Petri nets [[zooref#ler22|[Ler22]]] and vector addition systems [[zooref#co22|[CO22]]] are complete for this class under primitive recursive reductions, as well as the problem of navigating robots through a maze of gadgets with spawner and destroyer nodes [[zooref#ani+23|[Ani+23]]].</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" class="diff-lineno" id="mw-diff-left-l99" >Line 99:</td>
<td colspan="2" class="diff-lineno">Line 111:</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>An equivalent definition is: <math>\Sigma_0=\Delta_0=\Pi_0</math> is the set of numbers decided by formula with one free variable and bounded quantifier, where the primitives are + and <math>\times</math>. A bounded quantifier is of the form <math> \phi=\forall i<j \psi </math> or <math>\phi=\exists i<j \psi</math> where <math>j</math> is considered to be free in <math>\phi</math>. Then <math>\Sigma_{i+1}</math> is the sets of number validating a formula of the form <math>\exists X_1\dots\exists X_n,\psi</math> with <math>\psi\in\Delta_i</math>. The set &#928;<sub>i</sub> is the set of formula who are negation of <math>\Sigma_i</math> formula. And &#916;<sub>i</sub> = &#931;<sub>i</sub> &#8745; &#928;<sub>i</sub>. </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>An equivalent definition is: <math>\Sigma_0=\Delta_0=\Pi_0</math> is the set of numbers decided by formula with one free variable and bounded quantifier, where the primitives are + and <math>\times</math>. A bounded quantifier is of the form <math> \phi=\forall i<j \psi </math> or <math>\phi=\exists i<j \psi</math> where <math>j</math> is considered to be free in <math>\phi</math>. Then <math>\Sigma_{i+1}</math> is the sets of number validating a formula of the form <math>\exists X_1\dots\exists X_n,\psi</math> with <math>\psi\in\Delta_i</math>. The set &#928;<sub>i</sub> is the set of formula who are negation of <math>\Sigma_i</math> formula. And &#916;<sub>i</sub> = &#931;<sub>i</sub> &#8745; &#928;<sub>i</sub>. </div></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><del style="font-weight: bold; text-decoration: none;">----</del></div></td><td colspan="2"> </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><del style="font-weight: bold; text-decoration: none;"></del></div></td><td colspan="2"> </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><del style="font-weight: bold; text-decoration: none;">===== <span id="ackermann" style="color:red">Ack</span>: Ackermann Time =====</del></div></td><td colspan="2"> </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><del style="font-weight: bold; text-decoration: none;"></del></div></td><td colspan="2"> </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><del style="font-weight: bold; text-decoration: none;">Defined in [[zooref#sch16|[Sch16]]]. Let <math>F_0(x) = x+1</math> and <math>F_k(x) = F_{k-1}^x(x)</math> where <math>F_{k-1}^x(x)</math> is <math>F_{k-1}(x)</math> applied to itself <math>x</math> times. For example <math>F_1(x) = 2x + 1</math>, and <math>F_2(x) = 2^{x+1}(x + 1) - 1</math>. Then define, <math>F_\omega(x) = F_x(x)</math>, note that has about the same growth rate as <math>A(x,x)</math> where A is the Ackermann function. This class is equal to [[Complexity Zoo:D#dtime|DTIME]](F<sub>ω</sub>(p(n))) over all primitive-recursive functions p(n). The class remains unchanged if we replace [[Complexity Zoo:D#dtime|DTIME]] with [[Complexity Zoo:D#ntime|NTIME]] or [[Complexity Zoo:D#dspace|DSPACE]].</del></div></td><td colspan="2"> </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><del style="font-weight: bold; text-decoration: none;"></del></div></td><td colspan="2"> </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><del style="font-weight: bold; text-decoration: none;">Strictly contains [[Complexity Zoo:E#elementary|ELEMENTARY]], [[Complexity Zoo:T#tower|Tower]], and [[Complexity Zoo:P#pr|PR]]. Is strictly contained in [[Complexity Zoo:R#r|R]].</del></div></td><td colspan="2"> </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><del style="font-weight: bold; text-decoration: none;"></del></div></td><td colspan="2"> </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><del style="font-weight: bold; text-decoration: none;">The relationship between this class and [[Complexity Zoo:P#pr|PR]] is analogous to the relationship between [[Complexity Zoo:T#tower|Tower]] and [[Complexity Zoo:E#elementary|ELEMENTARY]]. That is, Ack contains problems "barely" outside of [[Complexity Zoo:P#pr|PR]] and, unlike [[Complexity Zoo:P#pr|PR]], has complete problems.</del></div></td><td colspan="2"> </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><del style="font-weight: bold; text-decoration: none;"></del></div></td><td colspan="2"> </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><del style="font-weight: bold; text-decoration: none;">The reachability problems for Petri nets [[zooref#ler22|[Ler22]]] and vector addition systems [[zooref#co22|[CO22]]] are complete for this class under primitive recursive reductions, as well as the problem of navigating robots through a maze of gadgets with spawner and destroyer nodes [[zooref#ani+23|[Ani+23]]].</del></div></td><td colspan="2"> </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><del style="font-weight: bold; text-decoration: none;"></del></div></td><td colspan="2"> </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>
</table>
ZTKing
https://complexityzoo.net/index.php?title=Complexity_Zoo:A&diff=6884&oldid=prev
ZTKing: /* Ack: Ackermann Time */
2023-10-25T00:21:27Z
<p><span dir="auto"><span class="autocomment">Ack: Ackermann Time</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 00:21, 25 October 2023</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l109" >Line 109:</td>
<td colspan="2" class="diff-lineno">Line 109:</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>The relationship between this class and [[Complexity Zoo:P#pr|PR]] is analogous to the relationship between [[Complexity Zoo:T#tower|Tower]] and [[Complexity Zoo:E#elementary|ELEMENTARY]]. That is, Ack contains problems "barely" outside of [[Complexity Zoo:P#pr|PR]] and, unlike [[Complexity Zoo:P#pr|PR]], has complete problems.</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>The relationship between this class and [[Complexity Zoo:P#pr|PR]] is analogous to the relationship between [[Complexity Zoo:T#tower|Tower]] and [[Complexity Zoo:E#elementary|ELEMENTARY]]. That is, Ack contains problems "barely" outside of [[Complexity Zoo:P#pr|PR]] and, unlike [[Complexity Zoo:P#pr|PR]], has complete problems.</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>The reachability <del class="diffchange diffchange-inline">problem </del>for Petri nets [[zooref#ler22|[Ler22]]] and vector addition systems [[zooref#co22|[CO22]]] are complete for this class under primitive recursive reductions, as well as the problem of navigating robots through a maze of gadgets with spawner and destroyer nodes [[zooref#ani+23|[Ani+23]]].</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>The reachability <ins class="diffchange diffchange-inline">problems </ins>for Petri nets [[zooref#ler22|[Ler22]]] and vector addition systems [[zooref#co22|[CO22]]] are complete for this class under primitive recursive reductions, as well as the problem of navigating robots through a maze of gadgets with spawner and destroyer nodes [[zooref#ani+23|[Ani+23]]].</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>
ZTKing
https://complexityzoo.net/index.php?title=Complexity_Zoo:A&diff=6883&oldid=prev
ZTKing: /* Ack: Ackermann Time */
2023-10-25T00:18:05Z
<p><span dir="auto"><span class="autocomment">Ack: Ackermann Time</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 00:18, 25 October 2023</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l103" >Line 103:</td>
<td colspan="2" class="diff-lineno">Line 103:</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="ackermann" style="color:red">Ack</span>: Ackermann Time =====</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="ackermann" style="color:red">Ack</span>: Ackermann Time =====</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>Defined in [[zooref#sch16|[Sch16]]]. Let <math>F_0(x) = x+1</math> and <math>F_k(x) = F_{k-1}^x(x)</math> where <math>F_{k-1}^x(x)</math> is <math>F_{k-1}(x)</math> applied to itself <math>x</math> times. For example <math>F_1(x) = 2x + 1</math>, and <math>F_2(x) = 2^{x+1}(x + 1) - 1</math>. Then define, <math>F_\omega(x) = F_x(x)</math>, note that has the same growth rate as <math>A(x,x)</math> where A is the Ackermann function. This class is equal to [[Complexity Zoo:D#dtime|DTIME]](F<sub>ω</sub>(p(n))) over all primitive-recursive functions p(n). </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>Defined in [[zooref#sch16|[Sch16]]]. Let <math>F_0(x) = x+1</math> and <math>F_k(x) = F_{k-1}^x(x)</math> where <math>F_{k-1}^x(x)</math> is <math>F_{k-1}(x)</math> applied to itself <math>x</math> times. For example <math>F_1(x) = 2x + 1</math>, and <math>F_2(x) = 2^{x+1}(x + 1) - 1</math>. Then define, <math>F_\omega(x) = F_x(x)</math>, note that has <ins class="diffchange diffchange-inline">about </ins>the same growth rate as <math>A(x,x)</math> where A is the Ackermann function. This class is equal to [[Complexity Zoo:D#dtime|DTIME]](F<sub>ω</sub>(p(n))) over all primitive-recursive functions p(n)<ins class="diffchange diffchange-inline">. The class remains unchanged if we replace [[Complexity Zoo:D#dtime|DTIME]] with [[Complexity Zoo:D#ntime|NTIME]] or [[Complexity Zoo:D#dspace|DSPACE]]</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>Strictly contains [[Complexity Zoo:E#elementary|ELEMENTARY]], [[Complexity Zoo:T#tower|Tower]], and [[Complexity Zoo:P#pr|PR]]. Is strictly contained in [[Complexity Zoo:R#r|R]].</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>Strictly contains [[Complexity Zoo:E#elementary|ELEMENTARY]], [[Complexity Zoo:T#tower|Tower]], and [[Complexity Zoo:P#pr|PR]]. Is strictly contained in [[Complexity Zoo:R#r|R]].</div></td></tr>
</table>
ZTKing
https://complexityzoo.net/index.php?title=Complexity_Zoo:A&diff=6882&oldid=prev
ZTKing: /* Ack: Ackermann Time */
2023-10-25T00:13:56Z
<p><span dir="auto"><span class="autocomment">Ack: Ackermann Time</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 00:13, 25 October 2023</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l103" >Line 103:</td>
<td colspan="2" class="diff-lineno">Line 103:</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="ackermann" style="color:red">Ack</span>: Ackermann Time =====</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="ackermann" style="color:red">Ack</span>: Ackermann Time =====</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>Defined in [[zooref#sch16|[Sch16]]]. Let <math>F_0(x) = x+1</math> and <math>F_k(x) = F_{k-1}^x(x)</math> where <math>F_{k-1}^x(x)</math> is <math>F_{k-1}(x)</math> applied to itself <math>x</math> times. For example <math>F_1(x) = 2x + 1</math>, and <math>F_2(x) = 2^{x+1}(x + 1) - 1</math>. Then define, <math>F_\omega(x) = F_x(x)</math>, note that <del class="diffchange diffchange-inline">this is equivalent to </del><math>A(x,x)</math> where A is the Ackermann function. This class is equal to [[Complexity Zoo:D#dtime|DTIME]](F<sub>ω</sub>(p(n))) over all primitive-recursive functions p(n). </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>Defined in [[zooref#sch16|[Sch16]]]. Let <math>F_0(x) = x+1</math> and <math>F_k(x) = F_{k-1}^x(x)</math> where <math>F_{k-1}^x(x)</math> is <math>F_{k-1}(x)</math> applied to itself <math>x</math> times. For example <math>F_1(x) = 2x + 1</math>, and <math>F_2(x) = 2^{x+1}(x + 1) - 1</math>. Then define, <math>F_\omega(x) = F_x(x)</math>, note that <ins class="diffchange diffchange-inline">has the same growth rate as </ins><math>A(x,x)</math> where A is the Ackermann function. This class is equal to [[Complexity Zoo:D#dtime|DTIME]](F<sub>ω</sub>(p(n))) over all primitive-recursive functions p(n). </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>Strictly contains [[Complexity Zoo:E#elementary|ELEMENTARY]], [[Complexity Zoo:T#tower|Tower]], and [[Complexity Zoo:P#pr|PR]]. Is strictly contained in [[Complexity Zoo:R#r|R]].</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>Strictly contains [[Complexity Zoo:E#elementary|ELEMENTARY]], [[Complexity Zoo:T#tower|Tower]], and [[Complexity Zoo:P#pr|PR]]. Is strictly contained in [[Complexity Zoo:R#r|R]].</div></td></tr>
</table>
ZTKing
https://complexityzoo.net/index.php?title=Complexity_Zoo:A&diff=6878&oldid=prev
ZTKing: /* Ack: Ackermann Time */
2023-10-24T23:53:21Z
<p><span dir="auto"><span class="autocomment">Ack: Ackermann Time</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 23:53, 24 October 2023</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l103" >Line 103:</td>
<td colspan="2" class="diff-lineno">Line 103:</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="ackermann" style="color:red">Ack</span>: Ackermann Time =====</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="ackermann" style="color:red">Ack</span>: Ackermann Time =====</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>Defined in [[zooref#sch16|[Sch16]]]. Let <math>F_0(x) = x+1</math> and <math>F_k(<del class="diffchange diffchange-inline">n</del>) = F_{k-1}^<del class="diffchange diffchange-inline">n</del>(<del class="diffchange diffchange-inline">n</del>)</math> where <math>F_{k-1}^<del class="diffchange diffchange-inline">n</del>(<del class="diffchange diffchange-inline">n</del>)</math> is <math>F_{k-1}(<del class="diffchange diffchange-inline">n</del>)</math> applied to itself <math><del class="diffchange diffchange-inline">n</del></math> times. For example <math>F_1(x) = 2x + 1</math>, and <math>F_2(x) = 2^{x+1}(x + 1) - 1</math>. Then define, <math>F_\omega(x) = F_x(x)</math>, note that this equivalent to <math>A(x,x)</math> where A is the Ackermann function. This class is equal to [[Complexity Zoo:D#dtime|DTIME]](F<sub>ω</sub>(p(n))) over all primitive-recursive functions p(n). </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>Defined in [[zooref#sch16|[Sch16]]]. Let <math>F_0(x) = x+1</math> and <math>F_k(<ins class="diffchange diffchange-inline">x</ins>) = F_{k-1}^<ins class="diffchange diffchange-inline">x</ins>(<ins class="diffchange diffchange-inline">x</ins>)</math> where <math>F_{k-1}^<ins class="diffchange diffchange-inline">x</ins>(<ins class="diffchange diffchange-inline">x</ins>)</math> is <math>F_{k-1}(<ins class="diffchange diffchange-inline">x</ins>)</math> applied to itself <math><ins class="diffchange diffchange-inline">x</ins></math> times. For example <math>F_1(x) = 2x + 1</math>, and <math>F_2(x) = 2^{x+1}(x + 1) - 1</math>. Then define, <math>F_\omega(x) = F_x(x)</math>, note that this <ins class="diffchange diffchange-inline">is </ins>equivalent to <math>A(x,x)</math> where A is the Ackermann function. This class is equal to [[Complexity Zoo:D#dtime|DTIME]](F<sub>ω</sub>(p(n))) over all primitive-recursive functions p(n). </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>Strictly contains [[Complexity Zoo:E#elementary|ELEMENTARY]], [[Complexity Zoo:T#tower|Tower]], and [[Complexity Zoo:P#pr|PR]]. Is strictly contained in [[Complexity Zoo:R#r|R]].</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>Strictly contains [[Complexity Zoo:E#elementary|ELEMENTARY]], [[Complexity Zoo:T#tower|Tower]], and [[Complexity Zoo:P#pr|PR]]. Is strictly contained in [[Complexity Zoo:R#r|R]].</div></td></tr>
</table>
ZTKing
https://complexityzoo.net/index.php?title=Complexity_Zoo:A&diff=6877&oldid=prev
ZTKing: /* Ack: Ackermann Time */
2023-10-24T23:52:28Z
<p><span dir="auto"><span class="autocomment">Ack: Ackermann Time</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 23:52, 24 October 2023</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l109" >Line 109:</td>
<td colspan="2" class="diff-lineno">Line 109:</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>The relationship between this class and [[Complexity Zoo:P#pr|PR]] is analogous to the relationship between [[Complexity Zoo:T#tower|Tower]] and [[Complexity Zoo:E#elementary|ELEMENTARY]]. That is, Ack contains problems "barely" outside of [[Complexity Zoo:P#pr|PR]] and, unlike [[Complexity Zoo:P#pr|PR]], has complete problems.</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>The relationship between this class and [[Complexity Zoo:P#pr|PR]] is analogous to the relationship between [[Complexity Zoo:T#tower|Tower]] and [[Complexity Zoo:E#elementary|ELEMENTARY]]. That is, Ack contains problems "barely" outside of [[Complexity Zoo:P#pr|PR]] and, unlike [[Complexity Zoo:P#pr|PR]], has complete problems.</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>The reachability problem for Petri nets [[zooref#ler22|[Ler22]]] and vector addition systems [[zooref#co22|[CO22]]] are complete for this class under primitive recursive reductions<del class="diffchange diffchange-inline">. The </del>problem of navigating robots through a maze of gadgets with spawner and destroyer nodes <del class="diffchange diffchange-inline">is also Ackerman-complete </del>[[zooref#ani+23|[Ani+23]]].</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>The reachability problem for Petri nets [[zooref#ler22|[Ler22]]] and vector addition systems [[zooref#co22|[CO22]]] are complete for this class under primitive recursive reductions<ins class="diffchange diffchange-inline">, as well as the </ins>problem of navigating robots through a maze of gadgets with spawner and destroyer nodes [[zooref#ani+23|[Ani+23]]].</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>
ZTKing
https://complexityzoo.net/index.php?title=Complexity_Zoo:A&diff=6876&oldid=prev
ZTKing: Added "Ack" complexity class.
2023-10-24T23:50:53Z
<p>Added "Ack" complexity class.</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 23:50, 24 October 2023</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l99" >Line 99:</td>
<td colspan="2" class="diff-lineno">Line 99:</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>An equivalent definition is: <math>\Sigma_0=\Delta_0=\Pi_0</math> is the set of numbers decided by formula with one free variable and bounded quantifier, where the primitives are + and <math>\times</math>. A bounded quantifier is of the form <math> \phi=\forall i<j \psi </math> or <math>\phi=\exists i<j \psi</math> where <math>j</math> is considered to be free in <math>\phi</math>. Then <math>\Sigma_{i+1}</math> is the sets of number validating a formula of the form <math>\exists X_1\dots\exists X_n,\psi</math> with <math>\psi\in\Delta_i</math>. The set &#928;<sub>i</sub> is the set of formula who are negation of <math>\Sigma_i</math> formula. And &#916;<sub>i</sub> = &#931;<sub>i</sub> &#8745; &#928;<sub>i</sub>. </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>An equivalent definition is: <math>\Sigma_0=\Delta_0=\Pi_0</math> is the set of numbers decided by formula with one free variable and bounded quantifier, where the primitives are + and <math>\times</math>. A bounded quantifier is of the form <math> \phi=\forall i<j \psi </math> or <math>\phi=\exists i<j \psi</math> where <math>j</math> is considered to be free in <math>\phi</math>. Then <math>\Sigma_{i+1}</math> is the sets of number validating a formula of the form <math>\exists X_1\dots\exists X_n,\psi</math> with <math>\psi\in\Delta_i</math>. The set &#928;<sub>i</sub> is the set of formula who are negation of <math>\Sigma_i</math> formula. And &#916;<sub>i</sub> = &#931;<sub>i</sub> &#8745; &#928;<sub>i</sub>. </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="ackermann" style="color:red">Ack</span>: Ackermann Time =====</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;">Defined in [[zooref#sch16|[Sch16]]]. Let <math>F_0(x) = x+1</math> and <math>F_k(n) = F_{k-1}^n(n)</math> where <math>F_{k-1}^n(n)</math> is <math>F_{k-1}(n)</math> applied to itself <math>n</math> times. For example <math>F_1(x) = 2x + 1</math>, and <math>F_2(x) = 2^{x+1}(x + 1) - 1</math>. Then define, <math>F_\omega(x) = F_x(x)</math>, note that this equivalent to <math>A(x,x)</math> where A is the Ackermann function. This class is equal to [[Complexity Zoo:D#dtime|DTIME]](F<sub>ω</sub>(p(n))) over all primitive-recursive functions p(n). </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;">Strictly contains [[Complexity Zoo:E#elementary|ELEMENTARY]], [[Complexity Zoo:T#tower|Tower]], and [[Complexity Zoo:P#pr|PR]]. Is strictly contained in [[Complexity Zoo:R#r|R]].</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 relationship between this class and [[Complexity Zoo:P#pr|PR]] is analogous to the relationship between [[Complexity Zoo:T#tower|Tower]] and [[Complexity Zoo:E#elementary|ELEMENTARY]]. That is, Ack contains problems "barely" outside of [[Complexity Zoo:P#pr|PR]] and, unlike [[Complexity Zoo:P#pr|PR]], has complete problems.</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 reachability problem for Petri nets [[zooref#ler22|[Ler22]]] and vector addition systems [[zooref#co22|[CO22]]] are complete for this class under primitive recursive reductions. The problem of navigating robots through a maze of gadgets with spawner and destroyer nodes is also Ackerman-complete [[zooref#ani+23|[Ani+23]]].</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 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>
</table>
ZTKing
https://complexityzoo.net/index.php?title=Complexity_Zoo:A&diff=6870&oldid=prev
Emil Jeřábek: /* AmpMP: Amplifiable MP */
2023-06-22T11:35:10Z
<p><span dir="auto"><span class="autocomment">AmpMP: Amplifiable MP</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 11:35, 22 June 2023</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l237" >Line 237:</td>
<td colspan="2" class="diff-lineno">Line 237:</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>Defined in [[zooref#gkr95|[GKR+95]]].</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>Defined in [[zooref#gkr95|[GKR+95]]].</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>Contains [[Complexity Zoo:P#ph|PH]] and Contained in [[Complexity Zoo:M#mp2|MP]].</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>Contains [[Complexity Zoo:P#ph|PH]] and <ins class="diffchange diffchange-inline">[[Complexity Zoo:M#modph|ModPH]]. </ins>Contained in [[Complexity Zoo:M#mp2|MP]].</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="amppbqp" style="color:red">AmpP-BQP</span>: [[Complexity Zoo:B#bqp|BQP]] Restricted To [[Zoo_Exhibit#ampp|AmpP]] States =====</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="amppbqp" style="color:red">AmpP-BQP</span>: [[Complexity Zoo:B#bqp|BQP]] Restricted To [[Zoo_Exhibit#ampp|AmpP]] States =====</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>Similar to [[Complexity Zoo:T#treebqp|TreeBQP]] except that the quantum computer's state at each time step is restricted to being exponentially close to a state in [[Zoo_Exhibit#ampp|AmpP]] (that is, a state for which the amplitudes are computable by a classical polynomial-size circuit).</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>Similar to [[Complexity Zoo:T#treebqp|TreeBQP]] except that the quantum computer's state at each time step is restricted to being exponentially close to a state in [[Zoo_Exhibit#ampp|AmpP]] (that is, a state for which the amplitudes are computable by a classical polynomial-size circuit).</div></td></tr>
</table>
Emil Jeřábek
https://complexityzoo.net/index.php?title=Complexity_Zoo:A&diff=6791&oldid=prev
Quackack: /* ACC0: AC0 With Arbitrary MOD Gates */
2022-07-19T11:13:06Z
<p><span dir="auto"><span class="autocomment">ACC0: AC0 With Arbitrary MOD Gates</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 11:13, 19 July 2022</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l81" >Line 81:</td>
<td colspan="2" class="diff-lineno">Line 81:</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>Contains 4-[[Complexity Zoo:P#kpbp|PBP]] [[zooref#bt88|[BT88]]].</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>Contains 4-[[Complexity Zoo:P#kpbp|PBP]] [[zooref#bt88|[BT88]]].</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>See also: [[Complexity Zoo:Q#qacc0|QACC<sup>0</sup>]].</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>See also: [[Complexity Zoo:Q#qacc0|QACC<ins class="diffchange diffchange-inline"><sup>0</sup>]] and [[Complexity Zoo:C#cc0|CC</ins><sup>0</sup>]].</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>
Quackack