<p>The paper <a href="http://homepages.inf.ed.ac.uk/kousha/counting_suc_ls_sscj.ps">Counting Quantifiers, Successor Relations and Logarithmic Space</a>, by Kousha Etessami proves that the problem $\mathbf{ORD}$ (which is essentially checking if a vertex $s$ precedes a vertex $t$ in an outdegree one graph $G$, that is promised to be a path) is $\mathsf{L}$-hard under quantifier free projections.</p>

<p>The problem $\mathbf{ORD}$ can be seen to reduce to the problem $\mathbf{USTCONN}$, by $\mathsf{FO}$-reductions: Given an instance $\langle G,s,t\rangle$ of $\mathbf{ORD}$ just delete the edge out of $t$ and output the other edges $u \rightarrow v$ as undirected edges $\{u,v\}$ the $\mathbf{USTCONN}$ question being whether $s,t$ are connected in the resulting graph. (Note: The reduction can probably be made even finer.)</p>

CC BY-SA 3.0
2015-06-25T22:00:21.827Z
Thanks!  This seems to be an elaboration of my final comment about L-completeness of USTCONN.  However, it is not clear to me that the reduction from ORD can be done in sublogarithmic space, so this doesn't seem to answer the main question, of showing that USTCONN really does require at least logarithmic space.  What am I missing?
András Salamon
CC BY-SA 4.0
2021-06-08T05:41:49.350Z
It’s rather unclear to me what this answer is attempting to demonstrate. But for the record, sublogarithmic space (in the input tape representation as specified in the question) is *not* closed under FO reductions. For example, Buss (https://www.math.ucsd.edu/~sbuss/ResearchWeb/Boolean3/index.html) proves that every ALOGTIME (i.e., uniform NC1) problem has a DLOGTIME (hence FO) reduction to a problem computable in space $O(\log\log n)$, and yet, it is generally assumed that general NC1 problems are not computable in sublogarithmic space.
Emil Jeřábek
CC BY-SA 4.0
2021-06-08T08:56:10.107Z
Oh, even better, there exist *regular* (i.e., DSPACE(0)) languages NC1-complete under FO reductions, due to Barrington. I’m not entirely sure whether this also holds under DLOGTIME reductions.
Emil Jeřábek
CC BY-SA 4.0
2021-07-29T18:31:56.540Z
@EmilJeřábek I was just trying to show that USTCONN is Logspace hard under FO-reductions. Does that not rule out USTCONN being in sublogarithmic space? Also, FO-reduction is too strong a notion and we can even replace it by say DLogtime-projection.
SamiD
CC BY-SA 4.0
2021-07-29T18:39:51.183Z
No, that does not rule out USTCONN being in sublogarithmic space, as sublogarithmic space is not closed under FO or dlogtime reductions, as I already explained.
Emil Jeřábek
CC BY-SA 4.0
2021-07-29T19:22:26.583Z
@EmilJeřábek Is sublogarithmic space known to be closed under sort of reductions? I seem to remember a monograph by Sziepietowski that described everything that was worth knowing about sublogarithmic space (at least until the mid nineties) but I don’t have access to it.
SamiD
CC BY-SA 4.0
2021-07-29T19:31:13.037Z
I don’t know. The most obvious first choice would be sublogarithmic-space reductions, but as far as I can see, this does not actually work either (the usual argument for composition of low-space functions requires extra space to index the bits of the output of the inner function, which in this case is $O(\log n)$). I am unfortunately not familiar with literature on sublogarithmic space.
Emil Jeřábek
CC BY-SA 4.0
2021-07-29T19:40:41.483Z
This is the monograph: https://www.springer.com/gp/book/9783540583554
SamiD
CC BY-SA 4.0
2021-07-30T10:33:38.877Z
I can’t access it either.
Emil Jeřábek
CC BY-SA 4.0
2021-07-30T14:11:04.117Z
I found a pirated copy on the internets. Skimming through the book, the only mention of a reduction I found was a log-space transducer reduction in the context of NL-completeness of directed s-t-connectivity (“GAP”); nothing that would be useful for sublogarithmic space.
Emil Jeřábek
CC BY-SA 4.0
2021-07-30T14:15:56.003Z
I see. I don’t know where else to look.
SamiD
CC BY-SA 3.0
2015-06-24T17:02:37.973Z
2015-06-24T17:02:37.973Z
SamiD
<p>USTCONN is the problem that requires deciding whether there is a path from the source vertex $s$ to the target vertex $t$ in a graph $G$, where these are all given as part of the input.</p>

<p>Omer Reingold showed that USTCONN is in <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:L#l" rel="nofollow">L</a> (doi:<a href="http://dx.doi.org/10.1145/1391289.1391291" rel="nofollow">10.1145/1391289.1391291</a>).
The proof constructs a constant-degree <a href="https://en.wikipedia.org/wiki/Expander_graph" rel="nofollow">expander</a> by means of the zig-zag product.
A constant-degree expander has logarithmic diameter and one can then check all the possible paths using a constant number of logarithmic-size markers.</p>

<p>Reingold's result gives a logarithmic upper bound on the space complexity of USTCONN, resolving its space complexity "up to a constant factor" according to the paper.
I am curious about the corresponding lower bound, which is not mentioned anywhere else in the paper.</p>

<blockquote>
  <p>How does one prove that logarithmic space is required to decide USTCONN in the worst case?</p>
</blockquote>

<p><em>Edit:</em> Fix the input representation to be the $N \times N$ adjacency matrix of the underlying $N$-vertex symmetric simple directed graph, with the rows listed consecutively to form an $N^2$-bit string.</p>

<hr>

<p>Lewis and Papadimitriou showed (doi:<a href="http://dx.doi.org/10.1016/0304-3975(82)90058-5" rel="nofollow">10.1016/0304-3975(82)90058-5</a>) that USTCONN is SL-complete,
which with Reingold's result implies that SL=L.
Savitch showed (doi:<a href="http://dx.doi.org/10.1016/S0022-0000(70)80006-X" rel="nofollow">10.1016/S0022-0000(70)80006-X</a>) that $\text{NSPACE}(n) \subseteq \text{DSPACE}(n^2)$.
Further $\text{DSPACE}(f(n)) = \text{DSPACE}(1)$ for any computable function $f(n) = o(\log\log n)$ by Stearns, Hartmanis and Lewis (doi:<a href="http://dx.doi.org/10.1109/FOCS.1965.11" rel="nofollow">10.1109/FOCS.1965.11</a>), so at least $\Omega(\log\log n)$ space is needed for USTCONN.
Finally, the usual classes known to be below L (such as $\text{NC}^1$) are defined in terms of circuits and are not obviously comparable to any class defined in terms of a space bound.</p>

<p>As far as I can see, this leaves open the (admittedly unlikely) possibility that there is an even better deterministic algorithm that only uses $O((\log n)^\delta)$ but $\Omega(\log \log n)$ space, for some $\delta &lt; 1$, or even a nondeterministic algorithm for USTCONN that uses $o((\log n)^{1/2})$ space.</p>

<p>By the <a href="https://en.wikipedia.org/wiki/Space_hierarchy_theorem" rel="nofollow">space hierarchy theorem</a>, $\text{DSPACE}(o(f(n)) \subsetneq \text{DSPACE}(f(n))$ as long as $f(n)$ is space-constructible.
This might seem to suggest that USTCONN cannot be in $\text{DSPACE}(o(\log n))$.
However, USTCONN being complete for L under logspace reductions does not seem to imply this.
It seems still possible that USTCONN has enough structure to encode any problem in L by means of a logspace reduction, yet USTCONN itself only requires sublogarithmic space.</p>

<p>As long as there is some language in L that does require logarithmic space, then showing that USTCONN is complete for L under a strictly "weaker" than logspace reduction would yield the desired lower bound.</p>

<blockquote>
  <p>Is USTCONN complete for L under a reduction that requires $o(\log n)$ space?</p>
</blockquote>

<p>Immerman showed (doi:<a href="http://dx.doi.org/10.1137/0216051" rel="nofollow">10.1137/0216051</a>) that a version of directed reachability in which the desired path (but not the graph itself) is deterministic, is complete for L under first-order reductions, which are computable by AC$^0$ circuits.
This might then perhaps be adapted to show that USTCONN is complete for L under FO-reductions.
However, although AC$^0$ is strictly contained in L, AC$^0$ is again a circuit class and I am not aware of any way to perform FO-reductions in sublogarithmic space.</p>

<hr>

<p><em>Edit 2015-07-14:</em>
It is an interesting philosophical issue whether the space usage of a TM should include the size of an index into the input (thus allowing random access into the input, but needing an extra bit if the input doubles in size), or whether the space used by a TM is the number of worktape squares visited during a computation (which assumes that the input tape head is fixed and does not change when the input tape doubles in size).
The former RAM-style definition immediately gives a logspace lower bound for <em>any</em> computation, and models current computers that keep track of the current position in a file as an offset from the start of the file.
The latter classical definition assumes a paper-like tape with a fixed read head that doesn't know anything about the tape other than the current input symbol, which possibly is what Turing intended in his 1937 paper.</p>

<p>Heuristic arguments like the comment by Thomas, that it is not even possible to index the input with $o(\log n)$ bits of space, appear to assume a modern RAM-style definition.
Stearns/Hartmanis/Lewis use the TM-style definition, as does most classical work in space-bounded computation.</p>

<p>One can prove a logspace lower bound for USTCONN represented as an adjacency matrix by noting that the unary language of perfect squares requires logspace to recognise (see Rūsiņš Freivalds, <em>Models of Computation, Riemann Hypothesis, and Classical Mathematics</em>, SOFSEM 1998, LNCS 1521, 89–106. doi:<a href="http://dx.doi.org/10.1007/3-540-49477-4_6" rel="nofollow">10.1007/3-540-49477-4_6</a> (<a href="http://www.researchgate.net/profile/Rsis_Freivalds/publication/225811967_Models_of_Computation_Riemann_Hypothesis_and_Classical_Mathematics/links/0deec52a4b499606e0000000.pdf" rel="nofollow">preprint</a>)).
Then the same lower bound applies to USTCONN with the adjacency matrix representation.
This is perhaps too much of a cheat: usually enforcing the promise in a promise problem is meant to be easy compared to the actual problem, but here enforcing the promise that the input is a graph already gives the lower bound.
So it would be nice to see an argument for a logspace lower bound for the promise problem where the input is guaranteed to be from the language $\{\{0,1\}^{N \times N} \mid N=1,2,\dots\}$.</p>

CC BY-SA 3.0
2015-07-14T15:02:45.777Z
Maybe communication complexity technique for proving time space lower bound can help: if space is less than $\log n$ then time is less than $n^2$ so space time is less than $n^2 \log n$. Can we somehow get rid of the $\log n$ in space time and show if space is less than $\log n$ then time space is less than $n^2$?
Kaveh
CC BY-SA 3.0
2015-06-24T02:04:50.927Z
The input representation becomes important, as with $o(\log n)$ space we cannot specify or access an arbitrary location in the input. What input representation are you using? Can we even show that USTCONN is in non-deterministic sub-logarithmic space?
Thomas Steinke
CC BY-SA 3.0
2015-06-24T11:56:59.960Z
FO = LTH = DLogTime uniform AC^0
Kaveh
CC BY-SA 3.0
2015-06-24T18:08:06.430Z
this is very detailed & thats great but seems it would help to relate this to "officially known/ acknowledged open problems" and also known complete problems (see some of latter but maybe more around?)... of which it is apparently quite close... and note se is not a good format for that if so... btw the U in USTConn seems to stand for Undirected right? fyi SJ on this site has studied "low level" [STConn](http://cstheory.stackexchange.com/questions/12841/monotone-complexity-of-s-t-connectivity) lower bounds & its interrelation to USTConn, ofc seems there would be very natural connections
vzn
CC BY-SA 4.0
2021-03-18T03:16:35.880Z
@Kaveh what is the relation between $N$ and $n$?
Turbo
<cc.complexity-theory><lower-bounds><reductions><space-bounded>
How to prove that USTCONN requires logarithmic space?
András Salamon
# How to prove that USTCONN requires logarithmic space?

(Asked by: username_0 on 2015-06-23)

USTCONN is the problem that requires deciding whether there is a path from the source vertex $s$ to the target vertex $t$ in a graph $G$, where these are all given as part of the input.

Omer Reingold showed that USTCONN is in [L](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:L#l) (doi:[10.1145/1391289.1391291](http://dx.doi.org/10.1145/1391289.1391291)).
The proof constructs a constant-degree [expander](https://en.wikipedia.org/wiki/Expander_graph) by means of the zig-zag product.
A constant-degree expander has logarithmic diameter and one can then check all the possible paths using a constant number of logarithmic-size markers.

Reingold's result gives a logarithmic upper bound on the space complexity of USTCONN, resolving its space complexity "up to a constant factor" according to the paper.
I am curious about the corresponding lower bound, which is not mentioned anywhere else in the paper.

> How does one prove that logarithmic space is required to decide USTCONN in the worst case?

*Edit:* Fix the input representation to be the $N \times N$ adjacency matrix of the underlying $N$-vertex symmetric simple directed graph, with the rows listed consecutively to form an $N^2$-bit string.

---

Lewis and Papadimitriou showed (doi:[10.1016/0304-3975(82)90058-5](http://dx.doi.org/10.1016/0304-3975(82)90058-5)) that USTCONN is SL-complete,
which with Reingold's result implies that SL=L.
Savitch showed (doi:[10.1016/S0022-0000(70)80006-X](http://dx.doi.org/10.1016/S0022-0000(70)80006-X)) that $\text{NSPACE}(n) \subseteq \text{DSPACE}(n^2)$.
Further $\text{DSPACE}(f(n)) = \text{DSPACE}(1)$ for any computable function $f(n) = o(\log\log n)$ by Stearns, Hartmanis and Lewis (doi:[10.1109/FOCS.1965.11](http://dx.doi.org/10.1109/FOCS.1965.11)), so at least $\Omega(\log\log n)$ space is needed for USTCONN.
Finally, the usual classes known to be below L (such as $\text{NC}^1$) are defined in terms of circuits and are not obviously comparable to any class defined in terms of a space bound.

As far as I can see, this leaves open the (admittedly unlikely) possibility that there is an even better deterministic algorithm that only uses $O((\log n)^\delta)$ but $\Omega(\log \log n)$ space, for some $\delta < 1$, or even a nondeterministic algorithm for USTCONN that uses $o((\log n)^{1/2})$ space.

By the [space hierarchy theorem](https://en.wikipedia.org/wiki/Space_hierarchy_theorem), $\text{DSPACE}(o(f(n)) \subsetneq \text{DSPACE}(f(n))$ as long as $f(n)$ is space-constructible.
This might seem to suggest that USTCONN cannot be in $\text{DSPACE}(o(\log n))$.
However, USTCONN being complete for L under logspace reductions does not seem to imply this.
It seems still possible that USTCONN has enough structure to encode any problem in L by means of a logspace reduction, yet USTCONN itself only requires sublogarithmic space.

As long as there is some language in L that does require logarithmic space, then showing that USTCONN is complete for L under a strictly "weaker" than logspace reduction would yield the desired lower bound.

> Is USTCONN complete for L under a reduction that requires $o(\log n)$ space?

Immerman showed (doi:[10.1137/0216051](http://dx.doi.org/10.1137/0216051)) that a version of directed reachability in which the desired path (but not the graph itself) is deterministic, is complete for L under first-order reductions, which are computable by AC$^0$ circuits.
This might then perhaps be adapted to show that USTCONN is complete for L under FO-reductions.
However, although AC$^0$ is strictly contained in L, AC$^0$ is again a circuit class and I am not aware of any way to perform FO-reductions in sublogarithmic space.

---

*Edit 2015-07-14:*
It is an interesting philosophical issue whether the space usage of a TM should include the size of an index into the input (thus allowing random access into the input, but needing an extra bit if the input doubles in size), or whether the space used by a TM is the number of worktape squares visited during a computation (which assumes that the input tape head is fixed and does not change when the input tape doubles in size).
The former RAM-style definition immediately gives a logspace lower bound for *any* computation, and models current computers that keep track of the current position in a file as an offset from the start of the file.
The latter classical definition assumes a paper-like tape with a fixed read head that doesn't know anything about the tape other than the current input symbol, which possibly is what Turing intended in his 1937 paper.

Heuristic arguments like the comment by Thomas, that it is not even possible to index the input with $o(\log n)$ bits of space, appear to assume a modern RAM-style definition.
Stearns/Hartmanis/Lewis use the TM-style definition, as does most classical work in space-bounded computation.

One can prove a logspace lower bound for USTCONN represented as an adjacency matrix by noting that the unary language of perfect squares requires logspace to recognise (see Rūsiņš Freivalds, *Models of Computation, Riemann Hypothesis, and Classical Mathematics*, SOFSEM 1998, LNCS 1521, 89–106. doi:[10.1007/3-540-49477-4\_6](http://dx.doi.org/10.1007/3-540-49477-4_6) ([preprint](http://www.researchgate.net/profile/Rsis_Freivalds/publication/225811967_Models_of_Computation_Riemann_Hypothesis_and_Classical_Mathematics/links/0deec52a4b499606e0000000.pdf))).
Then the same lower bound applies to USTCONN with the adjacency matrix representation.
This is perhaps too much of a cheat: usually enforcing the promise in a promise problem is meant to be easy compared to the actual problem, but here enforcing the promise that the input is a graph already gives the lower bound.
So it would be nice to see an argument for a logspace lower bound for the promise problem where the input is guaranteed to be from the language $\{\{0,1\}^{N \times N} \mid N=1,2,\dots\}$.

**Tags:** cc.complexity-theory, lower-bounds, reductions, space-bounded

> **Comments:**
> **username_2**: The input representation becomes important, as with $o(\log n)$ space we cannot specify or access an arbitrary location in the input. What input representation are you using? Can we even show that USTCONN is in non-deterministic sub-logarithmic space?  
> **username_1**: FO = LTH = DLogTime uniform AC^0  
> **username_3**: this is very detailed & thats great but seems it would help to relate this to "officially known/ acknowledged open problems" and also known complete problems (see some of latter but maybe more around?)... of which it is apparently quite close... and note se is not a good format for that if so... btw the U in USTConn seems to stand for Undirected right? fyi SJ on this site has studied "low level" [STConn](http://cstheory.stackexchange.com/questions/12841/monotone-complexity-of-s-t-connectivity) lower bounds & its interrelation to USTConn, ofc seems there would be very natural connections  
> **username_1**: Maybe communication complexity technique for proving time space lower bound can help: if space is less than $\log n$ then time is less than $n^2$ so space time is less than $n^2 \log n$. Can we somehow get rid of the $\log n$ in space time and show if space is less than $\log n$ then time space is less than $n^2$?  
> **username_4**: @username_1 what is the relation between $N$ and $n$?  

---

## 1 answers

### Answer by username_5 on 2015-06-24. Score: 13

The paper [Counting Quantifiers, Successor Relations and Logarithmic Space](http://homepages.inf.ed.ac.uk/kousha/counting_suc_ls_sscj.ps), by Kousha Etessami proves that the problem $\mathbf{ORD}$ (which is essentially checking if a vertex $s$ precedes a vertex $t$ in an outdegree one graph $G$, that is promised to be a path) is $\mathsf{L}$-hard under quantifier free projections.

The problem $\mathbf{ORD}$ can be seen to reduce to the problem $\mathbf{USTCONN}$, by $\mathsf{FO}$-reductions: Given an instance $\langle G,s,t\rangle$ of $\mathbf{ORD}$ just delete the edge out of $t$ and output the other edges $u \rightarrow v$ as undirected edges $\{u,v\}$ the $\mathbf{USTCONN}$ question being whether $s,t$ are connected in the resulting graph. (Note: The reduction can probably be made even finer.)

> **Comments:**
> **username_0**: Thanks!  This seems to be an elaboration of my final comment about L-completeness of USTCONN.  However, it is not clear to me that the reduction from ORD can be done in sublogarithmic space, so this doesn't seem to answer the main question, of showing that USTCONN really does require at least logarithmic space.  What am I missing?  
> **username_6**: It’s rather unclear to me what this answer is attempting to demonstrate. But for the record, sublogarithmic space (in the input tape representation as specified in the question) is *not* closed under FO reductions. For example, Buss (https://www.math.ucsd.edu/~sbuss/ResearchWeb/Boolean3/index.html) proves that every ALOGTIME (i.e., uniform NC1) problem has a DLOGTIME (hence FO) reduction to a problem computable in space $O(\log\log n)$, and yet, it is generally assumed that general NC1 problems are not computable in sublogarithmic space.  
> **username_6**: Oh, even better, there exist *regular* (i.e., DSPACE(0)) languages NC1-complete under FO reductions, due to Barrington. I’m not entirely sure whether this also holds under DLOGTIME reductions.  
> **username_5**: @EmilJeřábek I was just trying to show that USTCONN is Logspace hard under FO-reductions. Does that not rule out USTCONN being in sublogarithmic space? Also, FO-reduction is too strong a notion and we can even replace it by say DLogtime-projection.  
> **username_6**: No, that does not rule out USTCONN being in sublogarithmic space, as sublogarithmic space is not closed under FO or dlogtime reductions, as I already explained.  
> **username_5**: @EmilJeřábek Is sublogarithmic space known to be closed under sort of reductions? I seem to remember a monograph by Sziepietowski that described everything that was worth knowing about sublogarithmic space (at least until the mid nineties) but I don’t have access to it.  
> **username_6**: I don’t know. The most obvious first choice would be sublogarithmic-space reductions, but as far as I can see, this does not actually work either (the usual argument for composition of low-space functions requires extra space to index the bits of the output of the inner function, which in this case is $O(\log n)$). I am unfortunately not familiar with literature on sublogarithmic space.  
> **username_5**: This is the monograph: https://www.springer.com/gp/book/9783540583554  
> **username_6**: I can’t access it either.  
> **username_6**: I found a pirated copy on the internets. Skimming through the book, the only mention of a reduction I found was a log-space transducer reduction in the context of NL-completeness of directed s-t-connectivity (“GAP”); nothing that would be useful for sublogarithmic space.  
> **username_5**: I see. I don’t know where else to look.  

---

