Complexity of Unique s-t-Connectivity I would like to know whether the following problem can be decided in $\mathsf{NL}$ (nondeterministic logspace):

Given a directed graph $G$ with two distinguished vertices $s$ and $t$, is there a unique path from $s$ to $t$ in $G$?

I feel that it is likely to be in $\mathsf{NL}$ since we can decide both if there is a $s$-$t$-path and if there is no such path. Yet, counting the number of such paths is $\mathsf{\sharp P}$-hard (Valiant, 1979).

So my questions: Do you have references about this? Is it obvious that it is in $\mathsf{NL}$? Or that it is not in $\mathsf{NL}$?
It seems your problem is in $NL$. Here is an algorithm.
First, nondeterministically guess a path from $s$ to $t$. If you guess incorrectly, reject. Call this algorithm $A$.
Consider the following nondeterministic algorithm $B$, which determines if there are at least two paths. Given a graph and $s,t$, for all pairs of distinct edges $e,f$, guess a path from $s$ to $t$ that includes $e$ but not $f$, then guess a path from $s$ to $t$ that includes $f$ but not $e$. If the guesses are correct, accept. If no acceptance occurs for all choices of $e$ and $f$, reject. Note $B$ is implementable in nondeterministic logspace.
Now, the set $L(B)$ is the set of $s$-$t$ graphs with at least two paths from $s$ to $t$. Because $NL = coNL$, the complement of $B$ is also in $NL$, i.e., we can determine if $s$ and $t$ have less than two paths, in nondeterministic logspace.
The final algorithm is: &quot;Run $A$. If $A$ accepts, then run the complement of $B$ and output its answer.&quot;
I don't know of a reference.
UPDATE: If you really want a reference, check out the first paragraph of Section 3 of this paper. But this is probably only one of many references that cite this consequence. It would be more reasonable to call the result &quot;folklore&quot; rather than citing a paper that happens to mention it.
UPDATE 2: Let's suppose you want to determine if there is a unique simple path. In that case, algorithm $A$ doesn't have to change: if there is a path at all then there is a simple path. I believe the following modification will work for algorithm $B$.
We want to rewrite algorithm $B$ so that it accepts iff there are at least two simple paths.
First consider the following polynomial-time algorithm for the problem. Find a shortest path $P$ from $s$ to $t$. For every edge $e$ in $P$, check if there is another $s$-$t$ path that does not go through $e$. If you find such a path then accept. If you never find another path then reject. Because $P$ is shortest, it does not have a cycle, and if there is another path that doesn't use some edge of $P$, then there is another path which is simple and doesn't use some edge of $P$. (This algorithm is used for the &quot;second shortest paths&quot; problem.)
We will implement this algorithm in $NL$. If we had an $NL$ algorithm for querying the edges $e$ in a fixed path $P$, we could implement the above in nondeterministic logspace: iterating through all edges $e$ in $P$, guess an $s$-$t$ path and check that for every edge visited along the way, none of them are equal to $e$.
So what we need is a &quot;path oracle&quot;, an $NL$ algorithm with the property: given $i=1,\ldots,n$, in every computation path the algorithm either reports the $i$th edge on a particular fixed $s$-$t$ path, or reject. We can get a path oracle by using $NL=coNL$ to isolate the lexicographically first path.
Here is a sketch of the path oracle.

Find $k$, the length of the shortest path from $s$ to $t$, by trying all $k=1,\ldots,n$ and using $NL=coNL$.
Set variables $u:=s$, $x:=1$, $j:=k$.
For all neighbors $v$ of $u$ in lexicographical order,
Determine whether or not there is a path from $v$ to $t$ of length $j-1$ (using the result $NL=coNL$).
More precisely, run the nondeterministic algorithm for $s$-$t$ connectivity (of length $j-1$) and the algorithm for its complement, simultaneously. When one of them accepts, go with its answer (it must be correct; both cannot accept). If both reject then reject.
If there is no path, proceed to the next neighbor. If you've exhausted all neighbors then reject.
If there is a path, then if $x=i$, output $(u,v)$ as the $i$th edge on the path from $s$ to $t$. Otherwise increment $x$, decrement $j$, set $u := v$, and start the for-loop again if $v \neq t$.
If $x &lt; i$ after reaching $t$ output bad $i$ (the given $i$ was too big).

Given $i$, this algorithm either outputs the $i$th edge on the lexicographically shortest path $P$ from $s$ to $t$, or rejects.