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.
