1
$\begingroup$

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

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ 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. $\endgroup$
    – Tassle
    Oct 26 at 16:07
  • $\begingroup$ 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? $\endgroup$
    – Nicola Gigante
    Oct 26 at 17:40
  • 2
    $\begingroup$ 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. $\endgroup$
    – Tassle
    Oct 26 at 18:01
  • 2
    $\begingroup$ 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) $\endgroup$
    – Alex Golovnev
    Oct 31 at 18:12

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.