20
$\begingroup$

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 (doi:10.1145/1391289.1391291). The proof constructs a constant-degree expander 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) that USTCONN is SL-complete, which with Reingold's result implies that SL=L. Savitch showed (doi: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), 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, $\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) 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 (preprint)). 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\}$.

$\endgroup$
6
  • $\begingroup$ Your ", so at least ... space is needed for UStCONN" conclusion does not follow from the rest of its sentence, since there are functions in $o(\log(\log(n)))$ for which such a $\delta$ does not exist. $\;$ $\endgroup$
    – user6973
    Jun 23, 2015 at 20:18
  • 5
    $\begingroup$ 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? $\endgroup$
    – Thomas
    Jun 24, 2015 at 2:04
  • $\begingroup$ FO = LTH = DLogTime uniform AC^0 $\endgroup$
    – Kaveh
    Jun 24, 2015 at 11:56
  • $\begingroup$ 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 lower bounds & its interrelation to USTConn, ofc seems there would be very natural connections $\endgroup$
    – vzn
    Jun 24, 2015 at 18:08
  • $\begingroup$ 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$? $\endgroup$
    – Kaveh
    Jul 14, 2015 at 15:02

1 Answer 1

13
$\begingroup$

The paper Counting Quantifiers, Successor Relations and Logarithmic Space, 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.)

$\endgroup$
12
  • 1
    $\begingroup$ 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? $\endgroup$ Jun 25, 2015 at 22:00
  • 2
    $\begingroup$ @AndrasSalamon : $\:$ You're missing Thomas's question about input representation, even if that doesn't address the question you just asked. $\;\;\;\;$ $\endgroup$
    – user6973
    Jun 25, 2015 at 22:58
  • $\begingroup$ 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 (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. $\endgroup$ Jun 8, 2021 at 5:41
  • $\begingroup$ 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. $\endgroup$ Jun 8, 2021 at 8:56
  • $\begingroup$ @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. $\endgroup$
    – SamiD
    Jul 29, 2021 at 18:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.