# $CH=UL$ and partial breaking of transitive closure bottleneck problem and Savitch's theorem?

Let $$L^t=DSPACE[O(\log n)^t]$$, $$NL^t=NSPACE[O(\log n)^t]$$ and $$UL^t=USPACE[O(\log n)^t$$.

Savitch provides $$NL\subseteq L^{2}$$.

If $$CH=UL$$ we clearly got rid of the transitive closure bottleneck problem as matrix powering is in $$UL$$ and therefore if $$CH=UL$$ would $$L=UL$$ or $$NC^1=UL$$ (if $$CH=UL=RL$$ the belief would be $$CH=L$$) be still difficult to demonstrate given $$UL=CH$$ implies $$L\subseteq RL\subseteq BPL\subseteq NL=UL=CH$$ which is a $$LOGSPACE$$ strengthening of Sipser-Gacs' $$BPP\in\Sigma_2^P\cap\Pi_2^P$$ (would there be any barriers?)?

$$PL$$ counts if majority of paths in undirected graph is accepting and $$\oplus L$$ counts if parity of accepting paths in undirected graph is odd.

Perhaps if $$PL=\oplus L=UL$$ there is a reduction from counting paths in undirected graphs to identifying if there is a path in an undirected graph having $$0/1$$ paths which would provide $$L=CH$$ if $$UL=CH$$?

• Intuitively if e.g. CH is in NL then NL is much more powerful than expected, so it seems unlikely that NL could be simulated more efficiently under that hypothesis. Feb 26, 2021 at 14:22
• It seems a little awkward $DTIME[2^{O(m)}]\subseteq DSPACE[O(m^2)]$. Feb 26, 2021 at 16:15