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)
* ZPP = EXP = ⊕EXP

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.
* 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.
* 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.

  • 3
    $\begingroup$ 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. $\endgroup$ Sep 8, 2017 at 16:59
  • 1
    $\begingroup$ blog.computationalcomplexity.org/2005/08/extreme-oracles.html may give you some ideas. $\endgroup$ Sep 8, 2017 at 17:05
  • $\begingroup$ @EmilJeřábek Thanks. I strengthened the first two entries accordingly, and added two entries from the link. $\endgroup$ Sep 8, 2017 at 18:08
  • $\begingroup$ P-uniform NC$^1$ ​ = ​ PSPACE ​ ​ ​ is more extreme than ​ P = PSPACE . ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$
    – user6973
    Sep 8, 2017 at 20:30
  • 1
    $\begingroup$ @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. $\endgroup$ Sep 9, 2017 at 2:15


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.