# Tag Info

Here is a definition of $O$ for one variable from Cormen, Introduction to Algorithms: $f(n) = O(g(n))$ means there exist positive constants $c$ and $n_0$ such that $0 \leq f(n) \leq cg(n)$ for all $n \geq n_0$. The extension to multiple variables is obvious: $f(m,n) = O(g(m,n))$ means there exist positive constants $c$ and $n_0$ such that $0 \leq f(m,n) \leq ... 7 The problem is L-complete. It’s easier to think about it when the edges are written backwards. That is, I will consider the problem formulated as follows: given a directed acyclic graph such that every node has out-degree at most$1$, and vertices$s$and$t$, determine if$t$is reachable from$s$. To see that it is in L, just follow the unique path ... 8 I don't know any publication where this is stated, but it is an$NLOGSPACE$-complete. For the lower bound one can give a reduction from the reachability problem, which is the problem of determining whether there is a path between two vertices$s$and$t$in a given (directed) graph$G= (V,E)$. Indeed, the following formula$\$p_s \land \bigwedge_{(v,u) \in E} ...