<p>Let <span class="math-container">$L^t=DSPACE[O(\log n)^t]$</span>, <span class="math-container">$NL^t=NSPACE[O(\log n)^t]$</span> and <span class="math-container">$UL^t=USPACE[O(\log n)^t$</span>.</p>
<p>Savitch provides <span class="math-container">$NL\subseteq L^{2}$</span>.</p>
<blockquote>
<p>If <span class="math-container">$CH=UL$</span> we clearly got rid of <a href="http://cs.brown.edu/research/pubs/pdfs/1993/Kao-1993-TOT.pdf" rel="nofollow noreferrer">the transitive closure bottleneck problem</a> as matrix powering is in <span class="math-container">$UL$</span> and therefore if <span class="math-container">$CH=UL$</span> would <span class="math-container">$L=UL$</span> or <span class="math-container">$NC^1=UL$</span> (if <span class="math-container">$CH=UL=RL$</span> the belief would be <span class="math-container">$CH=L$</span>) be still difficult to demonstrate given <span class="math-container">$UL=CH$</span> implies <span class="math-container">$L\subseteq RL\subseteq BPL\subseteq NL=UL=CH$</span> which is a <span class="math-container">$LOGSPACE$</span> strengthening of Sipser-Gacs' <span class="math-container">$BPP\in\Sigma_2^P\cap\Pi_2^P$</span> (would there be any barriers?)?</p>
</blockquote>
<p><span class="math-container">$PL$</span> counts if majority of paths in undirected graph is accepting and <span class="math-container">$\oplus L$</span> counts if parity of accepting paths in undirected graph is odd.</p>
<blockquote>
<p>Perhaps if <span class="math-container">$PL=\oplus L=UL$</span> there is a reduction from counting paths in undirected graphs to identifying if there is a path in an undirected graph having <span class="math-container">$0/1$</span> paths which would provide <span class="math-container">$L=CH$</span> if <span class="math-container">$UL=CH$</span>?</p>
</blockquote>

CC BY-SA 4.0
2021-02-26T14:22:09.640Z
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
CC BY-SA 4.0
2021-02-26T16:15:28.677Z
It seems a little awkward $DTIME[2^{O(m)}]\subseteq DSPACE[O(m^2)]$.
Turbo
<cc.complexity-theory><counting-complexity><big-picture><space-complexity><logspace>
$CH=UL$ and partial breaking of transitive closure bottleneck problem and Savitch's theorem?
Turbo
# $CH=UL$ and partial breaking of transitive closure bottleneck problem and Savitch's theorem?

(Asked by: username_0 on 2021-02-26)

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](http://cs.brown.edu/research/pubs/pdfs/1993/Kao-1993-TOT.pdf) 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$?

**Tags:** cc.complexity-theory, counting-complexity, big-picture, space-complexity, logspace

> **Comments:**
> **username_1**: 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.  
> **username_0**: It seems a little awkward $DTIME[2^{O(m)}]\subseteq DSPACE[O(m^2)]$.  

---

## 0 answers

