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).
* Uniform AC0=PH has not yet been ruled out, but AC0 is arguably not a natural complexity class.
* PRP = NEXP
* PNP = ⊕P = PEXP (though this prevents PNP from being 'feasible')
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.