<p>Are there conditional lower bounds for the deterministic time complexity of directed reachability algorithms? Maybe something linked to the <em>Strong Exponential Time Hypothesis</em> (SETH)?</p>
<p>I mean some result like, if SETH is true then reachability cannot be solved in less than <span class="math-container">$\mathcal{O}(something)$</span>.</p>

CC BY-SA 4.0
2023-10-26T16:07:15.750Z
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.
Tassle
CC BY-SA 4.0
2023-10-26T17:40:32.523Z
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?
Nicola Gigante
CC BY-SA 4.0
2023-10-26T18:01:28.650Z
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.
Tassle
CC BY-SA 4.0
2023-10-31T18:12:12.780Z
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 https://arxiv.org/pdf/2309.16176.pdf)
Alex Golovnev
<cc.complexity-theory><lower-bounds>
Conditional lower bounds for reachability
Nicola Gigante
# Conditional lower bounds for reachability

(Asked by: username_0 on 2023-10-26)

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)$.

**Tags:** cc.complexity-theory, lower-bounds
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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?  
> **username_1**: 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.  
> **username_2**: 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 https://arxiv.org/pdf/2309.16176.pdf)  

---

## 0 answers

