On the complexity of some reachability problems