25
$\begingroup$

Complexity theory, through such concepts as NP-completeness, distinguishes between computational problems that have relatively efficient solutions and those that are intractable. "Fine-grained" complexity aims to refine this qualitative distinction into a quantitative guide as to the exact time required to solve problems. More details can be found here: http://simons.berkeley.edu/programs/complexity2015

Here are some important hypotheses:

ETH: $3$-$SAT$ requires $2^{\delta n}$ time for some $ \delta > 0$.

SETH: for every $\varepsilon > 0$, there is a $k$ such that $k$-$SAT$ on $n$ variables, $m$ clauses cannot be solved in $2^{(1-\varepsilon)n}~poly~m$ time.

It is known that SETH is stronger than ETH and they both are stronger than $P \neq NP$,and both stronger than $FTP\neq W[1]$.

Four other important conjectures:

  1. 3SUM Conjecture: 3SUM on $n$ integers in $\{-n^3,…,n^3\}$ requires $n^{2-o(1)}$ time

  2. OV Conjecture: Orthogonal vectors on $n$ vectors requires $n^{2-o(1)}$ time.

  3. APSP Conjecture: All Pairs Shortest Path on $n$ nodes and $O(\log n)$ bit weights requires $n^{3-o(1)}$ time.

  4. BMM Conjecture: Any "combinatorial" algorithm for Boolean matrix multiplication requires $n^{3-o(1)}$ time.

It is known that SETH implies the OV Conjecture (Ryan Willams, 2004). Besides Ryan’s proof that SETH $\implies$ OV Conjecture, there are no other reductions relating the conjectures known.

My question: Do you know other related hypotheses or conjectures in this area? What are the relationships between them?

Acknowledgement: results listed are from the slides of Virginia Vassilevska Williams, she also gave me partial answers to this question.

Link to slides: http://theory.stanford.edu/~virgi/overview.pdf

$\endgroup$
3
  • $\begingroup$ Hi Rupei, I've been working on various graph reachability and constraint problems that are related to the very nice list of fine grained complexity problems that you mentioned. If you're at all interested, shoot me an email and we could chat sometime. I'm glad to see others who are interested in fine grained complexity on stackexchange. :) $\endgroup$ Sep 21, 2015 at 3:23
  • 3
    $\begingroup$ A trivial reduction: "combinatorial" subcubic APSP implies "combinatorial" subcubic BMM. For 3SUM, see relation among related problems in Page 14 of this slide cs.uwaterloo.ca/~tmchan/talks/bsg_stoc_talk.pdf. For BMM, see Section G of this paper theory.stanford.edu/~virgi/tria-mmult-conf.pdf. For APSP, there are many papers by Virginia showing subcubic equivalence. $\endgroup$ Sep 21, 2015 at 8:09
  • 1
    $\begingroup$ @Thatchaphol, Thank you for the kind sharing! $\endgroup$
    – user17918
    Sep 21, 2015 at 10:56

3 Answers 3

14
$\begingroup$

This is a recent paper introducing Nondeterministic Strong Exponential Time Hypothesis (NSETH), which is an extension of SETH.

NSETH: For every $\epsilon >0$, there is a $k$ such that $k$-DNF-TAUT cannot be solved in nondeterministic time $2^{(1-\epsilon)n}$.

NSETH implies SETH. If NSETH is true, then some problems do not have SETH lower bounds (because they have nondeterministic algorithms faster than deterministic algorithms).

This paper also introduced Non-uniform Nondeterministic Strong Exponential Time Hypothesis (NUNSETH), a hypothesis stronger than NSETH and SETH.

NUNSETH: For every $\epsilon >0$, there is a $k$ such that $k$-DNF-TAUT cannot be recognized by nondeterministic circuit families of size $2^{(1-\epsilon)n}$.

$\endgroup$
2
  • 1
    $\begingroup$ Thank you for the pioneering work! Ryan Williams believes SETH is false. Do you think NSETH is true? $\endgroup$
    – user17918
    Sep 21, 2015 at 8:42
  • 2
    $\begingroup$ This paper notes that Ryan has actually shown that the MA version of SETH is false, which seems to suggest that NSETH is unlikely to be true. Nevertheless, in some sense, the point is, in order to show connections between some of these other conjectures, you'd first have to make progress on refuting NSETH. $\endgroup$
    – palindrome
    Sep 22, 2015 at 4:37
7
$\begingroup$

Another interesting conjecture is hardness of $k$-Clique for fixed $k$ (see here).

This isn't exactly the sort of relationship you're looking for, but there was an interesting FOCS paper showing that a natural problem called "Matching Triangles" is hard under any of the SETH, 3SUM, or APSP conjectures (see here). It is not currently known whether or not any of these three conjectures imply each other in any interesting way -- this is one of the major open questions of Fine-Grained Complexity.

$\endgroup$
2
  • 1
    $\begingroup$ Thank you Greg! My original motivation to post this question here is to collect all the existing results in this area, like the good collections in The Parameterized Complexity Newsletter fpt.wikidot.com/… $\endgroup$
    – user17918
    Sep 20, 2015 at 23:00
  • $\begingroup$ The $k$-clique link seems to be broken. Just thought I'd let you know. :) $\endgroup$ Nov 5, 2015 at 16:43
3
$\begingroup$

relatively recent results by Backurs, Indyk accepted to STOC 2015 that computing edit distance in $O(n^{2-\epsilon})$ time → SETH false tie in neatly/ strong to the new emerging "fine grained complexity" research program/ paradigm. they are closely related to/ built on Williams result that SETH → Orthogonal Vectors conjecture. (even covered by the mainstream media, Boston Globe).

a seemingly very similar result due to Wehar considers the "2 DFA intersection emptiness" problem and finds that $O(n^{2-\epsilon})$ time → SETH false.

Wehar has other results that seem to also fit into general "fine grained complexity" connections, that the same $k$ DFA intersection emptiness in $n^{o(k)}$ time → $NL \subsetneq P$

along these lines it is also worth mentioning there is a known significant connection between DFA constructions and Levenshtein distance calculations eg in this paper

$\endgroup$
1
  • 1
    $\begingroup$ Added some small corrections to your post VZN. That was nice of you to mention me. I'm very passionate about the DFA intersection problem and will hopefully have more things to share in the future. :) $\endgroup$ Nov 5, 2015 at 16:53

Your Answer

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