> most of the probabilistic methods (specifically those that use a logarithmic amount of space)

These are by far not most, nor most of the practically useful ones. Directed graph reachability, given an adjacency list as input, is NL-hard.