I ask because John Baez notes that with reachability it is "known that no algorithm can solve it in polynomial time."

So I wondered if reachability is equivalent to satisfiability since satisfiability is well known to be NP-complete.