<p>What are some of the most extreme potential equalities between computational complexity classes (especially if there is a barrier to refuting them)?  These may give us an opportunity to prove better bounds, or provide a clearer understanding of the fundamental obstacles in complexity theory.</p>

<p>Here is my list (at most one and probably zero equalities actually hold):<br/>
* uniform TC<sup>0</sup> = NP<br/>
* NC<sup>1</sup> = CH (defined using logtime uniformity; implies NC<sup>1</sup> = LOGSPACE = PP)<br/>
* P = PSPACE<br/>
* ZPP = EXP = ⊕EXP<br/>
* BPP = NEXP = EXP<sup>NP</sup></p>

<p>It remains open whether P=PSPACE can be combined with P having non-uniform TC<sup>0</sup>-circuits, which would allow P-uniform TC<sup>0</sup>-circuits for PSPACE, and analogously for ZPP/EXP and BPP/NEXP.  It is also open whether (logtime) uniform TC<sup>0</sup> with an additional random input can simulate EXP (with zero error and unlikely failure) or NEXP (with bounded error).  TC<sub>0</sub> &lt; PP was only proved for (logtime) uniform TC<sup>0</sup> without randomness.  Also, if TC<sup>0</sup> is ruled out, we can fallback to NC<sup>1</sup> (with the same uniformity conditions).</p>

<p>More items:<br/>
* Uniform AC<sup>0</sup>[6]=PH has not yet been ruled out, but AC<sup>0</sup>[6] is arguably not a natural complexity class.<br/>
* P<sup>RP</sup> = NEXP<br/>
* P<sup>NP</sup> = ⊕P = PEXP (though this prevents P<sup>NP</sup> from being 'feasible')</p>

<p><i>Quasilinear Time</i></p>

<p>In the above, polynomial transformations of input size are immaterial, but the sharpened versions below care about the exact (up to a constant factor) size.</p>

<p>Sharpened version of P=PSPACE: Every function in nondeterministic linear space with linear output size can be computed in O(n*log n) time and O(n) space using a Turing machine with a single tape and a stack.  We can also ask for the machine to be reversible, and also oblivious with LOGSPACE computable movement.</p>

<p>Sharpened version of BPP=NEXP:  Every function (with linear output size) in E<sup>NP</sup> can be computed with linear size logarithmic depth bounded fan-in bounded fan-out uniform circuits, if O(n) random bits are appended to the input string, allowing 2<sup>-O(n)</sup> error probability.<br/>
<i>Notes:</i><br/>
* This is arguably the most extreme equality that we cannot yet rule out.<br/>
* There are different notions of (essentially logtime) uniformity that allow quasilinear-time circuit construction, with one reasonable choice being a Time(O(log n * (log log n)<sup>O(1)</sup>)) algorithm that given gate number (perhaps with gate ordering consistent with causality) gives the type of gate and the numbers where to send the output.<br/>
* One can also ask about zero error, 2<sup>-O(n)</sup> failure probability, and functions in E (but not simultaneously with BPP=NEXP).<br/>
* If linear size logarithmic depth circuits are finally ruled out, we can backtrack to logarithmic time on uniform linear size O(1)-depth recurrent circuits (even with reversibility, and bounded fan-in and fan-out).<br/>
* Also, uniform TC<sup>0</sup> of size O(n<sup>1+ε</sup>) (with randomness as above; depth depends on ε) has not been ruled out.</p>

CC BY-SA 3.0
2017-09-08T16:59:00.557Z
The first entry on your list can be made more extreme in several ways, such as $\mathrm{AC}^0[6]=\mathrm{PH}$ or $\mathrm{NC}^1=\mathrm{CH}$. The latter is also more extreme than your second line.
Emil Jeřábek
CC BY-SA 3.0
2017-09-08T17:05:23.297Z
http://blog.computationalcomplexity.org/2005/08/extreme-oracles.html may give you some ideas.
Emil Jeřábek
CC BY-SA 3.0
2017-09-08T18:08:13.210Z
@EmilJeřábek Thanks.  I strengthened the first two entries accordingly, and added two entries from the link.
Dmytro Taranovsky
CC BY-SA 3.0
2017-09-08T22:59:44.103Z
@RickyDemer Thanks.  I added it to the list (and also added possible ZPP-uniform NC$^1$ = EXP).
Dmytro Taranovsky
CC BY-SA 3.0
2017-09-09T00:25:33.087Z
AFAIK, we cannot rule out uniform-$TC^0=NEXP$. i.e. poly-time-constructable constant-depth threshold circuits compute all of nodeterministic exponential time.
Thomas Steinke
CC BY-SA 3.0
2017-09-09T02:02:43.787Z
@RickyDemer Regardless of whether the circuit can depend on randomness, existence of ZPP-uniform  $\mathrm{NC}^1$ circuits for EXP is equivalent to ZPP=EXP plus existence of non-uniform $\mathrm{NC}^1$ circuits for EXP, and similarly for BPP=NEXP.  I revised the wording accordingly.  Incidentally, were P-uniform TC$^0$ circuits for PSPACE ruled out? The proof for uniform TC$^0$ < PP used logtime uniformity.
Dmytro Taranovsky
CC BY-SA 3.0
2017-09-09T02:15:54.893Z
@Thomas P-uniform TC$^0$ is in P and so is not NEXP complete.  I am not sure whether that applies to uniform TC$^0$ circuits with randomness and bounded error.
Dmytro Taranovsky
CC BY-SA 3.0
2017-09-13T04:11:01.143Z
You are too cool!  I'm digging this.  I added you on LinkedIn btw.  Hope that you have a lovely day!  :)
Michael Wehar
<cc.complexity-theory><complexity-classes><circuit-complexity>
Complexity Class Equalities on the Edge of Inconsistency
Dmytro Taranovsky
# Complexity Class Equalities on the Edge of Inconsistency

(Asked by: username_0 on 2017-09-08)

What are some of the most extreme potential equalities between computational complexity classes (especially if there is a barrier to refuting them)? These may give us an opportunity to prove better bounds, or provide a clearer understanding of the fundamental obstacles in complexity theory.

Here is my list (at most one and probably zero equalities actually hold):  
\* uniform TC0 = NP  
\* NC1 = CH (defined using logtime uniformity; implies NC1 = LOGSPACE = PP)  
\* P = PSPACE  
\* ZPP = EXP = ⊕EXP  
\* BPP = NEXP = EXPNP

It remains open whether P=PSPACE can be combined with P having non-uniform TC0-circuits, which would allow P-uniform TC0-circuits for PSPACE, and analogously for ZPP/EXP and BPP/NEXP. It is also open whether (logtime) uniform TC0 with an additional random input can simulate EXP (with zero error and unlikely failure) or NEXP (with bounded error). TC0 < PP was only proved for (logtime) uniform TC0 without randomness. Also, if TC0 is ruled out, we can fallback to NC1 (with the same uniformity conditions).

More items:  
\* Uniform AC0[6]=PH has not yet been ruled out, but AC0[6] is arguably not a natural complexity class.  
\* PRP = NEXP  
\* PNP = ⊕P = PEXP (though this prevents PNP from being 'feasible')

*Quasilinear Time*

In the above, polynomial transformations of input size are immaterial, but the sharpened versions below care about the exact (up to a constant factor) size.

Sharpened version of P=PSPACE: Every function in nondeterministic linear space with linear output size can be computed in O(n\*log n) time and O(n) space using a Turing machine with a single tape and a stack. We can also ask for the machine to be reversible, and also oblivious with LOGSPACE computable movement.

Sharpened version of BPP=NEXP: Every function (with linear output size) in ENP can be computed with linear size logarithmic depth bounded fan-in bounded fan-out uniform circuits, if O(n) random bits are appended to the input string, allowing 2-O(n) error probability.  
*Notes:*  
\* This is arguably the most extreme equality that we cannot yet rule out.  
\* There are different notions of (essentially logtime) uniformity that allow quasilinear-time circuit construction, with one reasonable choice being a Time(O(log n \* (log log n)O(1))) algorithm that given gate number (perhaps with gate ordering consistent with causality) gives the type of gate and the numbers where to send the output.  
\* One can also ask about zero error, 2-O(n) failure probability, and functions in E (but not simultaneously with BPP=NEXP).  
\* If linear size logarithmic depth circuits are finally ruled out, we can backtrack to logarithmic time on uniform linear size O(1)-depth recurrent circuits (even with reversibility, and bounded fan-in and fan-out).  
\* Also, uniform TC0 of size O(n1+ε) (with randomness as above; depth depends on ε) has not been ruled out.

**Tags:** cc.complexity-theory, complexity-classes, circuit-complexity
> **Comments:**
> **username_1**: The first entry on your list can be made more extreme in several ways, such as $\mathrm{AC}^0[6]=\mathrm{PH}$ or $\mathrm{NC}^1=\mathrm{CH}$. The latter is also more extreme than your second line.  
> **username_1**: http://blog.computationalcomplexity.org/2005/08/extreme-oracles.html may give you some ideas.  
> **username_0**: @EmilJeřábek Thanks.  I strengthened the first two entries accordingly, and added two entries from the link.  
> **username_0**: @RickyDemer Thanks.  I added it to the list (and also added possible ZPP-uniform NC$^1$ = EXP).  
> **username_2**: AFAIK, we cannot rule out uniform-$TC^0=NEXP$. i.e. poly-time-constructable constant-depth threshold circuits compute all of nodeterministic exponential time.  
> **username_0**: @RickyDemer Regardless of whether the circuit can depend on randomness, existence of ZPP-uniform  $\mathrm{NC}^1$ circuits for EXP is equivalent to ZPP=EXP plus existence of non-uniform $\mathrm{NC}^1$ circuits for EXP, and similarly for BPP=NEXP.  I revised the wording accordingly.  Incidentally, were P-uniform TC$^0$ circuits for PSPACE ruled out? The proof for uniform TC$^0$ < PP used logtime uniformity.  
> **username_0**: @Thomas P-uniform TC$^0$ is in P and so is not NEXP complete.  I am not sure whether that applies to uniform TC$^0$ circuits with randomness and bounded error.  
> **username_3**: You are too cool!  I'm digging this.  I added you on LinkedIn btw.  Hope that you have a lovely day!  :)  

---

## 0 answers

