# Tag Info

14

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

11

I don't know the answer to your specific question (it seems related to the question of whether W1=W[2]). But the algorithm you give in your question is subsumed by several other results. Using your definition of $N$, CNF-SAT is basically solvable in $O(1.1279^N)$ time, as in the paper by Wahlstrom (link goes to a google scholar page of papers that cite it)....

8

Claim: If there exists an $\epsilon > 0$ such that for every $k'$, $k'$-partite $k'$-SAT can be solved in $2^{n(1-\epsilon)}$ time, then SETH fails. Proof: Suppose such an algorithm exists. We give an algorithm that, for every $k$ solves $k$-SAT in time $2^{n(1-\epsilon/2)}$. Consider a $k$-SAT instance with $n$ variables, apply the sparsification lemma ...

7

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

7

The "inverse" is almost the same as SAT is solvable in $O(2^{(1-\epsilon)n})$ time implies the intersection problem is solvable in $O(n^{2-\epsilon})$ time. To show this, it seems that you would need to provide a reduction from an intersection problem instance of size $n$ to a SAT instance of size $2\cdot log_2(n)$. This kind of reduction would be ...

6

Assuming SETH, the problem is not solvable in time $O\bigl(2^{(1-\epsilon)n}\mathrm{poly}(l)\bigr)$ for any $\epsilon>0$. First, let me show that this is true for the more general problem where $\Phi$ and $\Psi$ may be arbitrary monotone formulas. In this case, there is a poly-time ctt reduction from TAUT to the problem that preserves the number of ...

4

It is $W[1]$-hard even when $G$ has maximum degree $3$, but $FPT$ if $G$ has constant treewidth (all the above examples have constant treewidth). See the paper Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask) by Marx and Pilipczuk. Indeed, it follows from an earlier paper of Marx: Can ...

3

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

2

As Ricky Demer said in his comment, many search problems can be sped up with sorting or building some other index structure Lowest common ancestor queries can be answered in constant time with linear preprocessing. Lots of text problems can be sped up with some preprocessing, e.g. building a suffix array

Only top voted, non community-wiki answers of a minimum length are eligible