# $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. – Ryan Williams Feb 26 at 14:22
• It seems a little awkward $DTIME[2^{O(m)}]\subseteq DSPACE[O(m^2)]$. – 1.. Feb 26 at 16:15