# Conditional lower bounds for reachability

Are there conditional lower bounds for the deterministic time complexity of directed reachability algorithms? Maybe something linked to the Strong Exponential Time Hypothesis (SETH)?

I mean some result like, if SETH is true then reachability cannot be solved in less than $$\mathcal{O}(something)$$.

• What exactly do you mean by "directed reachability algorithms"? If you mean: "given a graph on $n$ vertices, compute its transitive closure", then that is equivalent to Boolean Matrix Multiplication, so it takes $\Theta(n^\omega)$ time, where $\omega$ is the matrix multiplication exponent. Oct 26, 2023 at 16:07
• Yes, I mean exactly that. Ok so as you said we can link it to the matrix multiplication lower bound. Is this in any way related to SAT and SETH? Oct 26, 2023 at 17:40
• I don't know of any direct relation between Matrix Multiplication and SETH. There is another relevant conjecture here: that any "combinatorial" algorithm for boolean matrix multiplication requires essentially cubic time (up to subpolynomial factors). This would imply that any combinatorial algorithm for reachability requires essentially cubic time. Note however that "combinatorial" in this context isn't well defined, so it's a kind of informal conjecture. Oct 26, 2023 at 18:01
• We don't know any non-trivial lower bounds on Matrix Multiplication under SETH, and there are some barriers to proving such lower bounds (see Theorem 4.4 in arxiv.org/pdf/2309.16176.pdf) Oct 31, 2023 at 18:12