0
$\begingroup$

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$?

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ 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. $\endgroup$
    – Ryan Williams
    Feb 26, 2021 at 14:22
  • $\begingroup$ It seems a little awkward $DTIME[2^{O(m)}]\subseteq DSPACE[O(m^2)]$. $\endgroup$
    – Turbo
    Feb 26, 2021 at 16:15

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy