<p>Most problems need at least linear time, so <span class="math-container">$O(n \log n)$</span> may be a little too close to optimal for a SETH based lower bound, generally we want running times where one can improve on the exponent by some constant.</p>
<p>However you can define problems solvable in <span class="math-container">$n^{1.0001}$</span> time such that improvements in the exponent would still refute SETH. Here is a simple example: consider Orthogonal Vectors with <span class="math-container">$n$</span> &quot;red&quot; vectors in <span class="math-container">$O(\log n)$</span> dimensions and <span class="math-container">$n^{0.0001}$</span> &quot;blue&quot; vectors in the same dimensions, and you want to find a red-blue pair that is orthogonal. It is not hard to see that improving over the obvious running time of this vector pair problem (in the exponent) would also refute SETH.</p>

CC BY-SA 4.0
2022-06-07T00:38:10.397Z
2022-06-07T12:52:37.103Z
2022-06-07T12:52:37.103Z
Ryan Williams
<p>After reading a bit about SETH (the strong exponential time hypothesis), I see that a lot of lower bounds for problems in P can be proven if we assume SETH. But I notice that most of the ones that are proven are solved in quadratic time (or slower). I wonder if any linear or <span class="math-container">$O(n\ log(n))$</span> time problem can have a similar property?</p>
<p>Is this something we can ask/show? What do you think?</p>
<p>Thanks for any answers.</p>

<cc.complexity-theory><time-complexity><fine-grained>
Lower-bounds under SETH
Jova
# Lower-bounds under SETH

(Asked by: username_0 on 2022-06-06)

After reading a bit about SETH (the strong exponential time hypothesis), I see that a lot of lower bounds for problems in P can be proven if we assume SETH. But I notice that most of the ones that are proven are solved in quadratic time (or slower). I wonder if any linear or $O(n\ log(n))$ time problem can have a similar property?

Is this something we can ask/show? What do you think?

Thanks for any answers.

**Tags:** cc.complexity-theory, time-complexity, fine-grained


---

## 1 answers

### Answer by username_1 on 2022-06-07. Score: 11

Most problems need at least linear time, so $O(n \log n)$ may be a little too close to optimal for a SETH based lower bound, generally we want running times where one can improve on the exponent by some constant.

However you can define problems solvable in $n^{1.0001}$ time such that improvements in the exponent would still refute SETH. Here is a simple example: consider Orthogonal Vectors with $n$ "red" vectors in $O(\log n)$ dimensions and $n^{0.0001}$ "blue" vectors in the same dimensions, and you want to find a red-blue pair that is orthogonal. It is not hard to see that improving over the obvious running time of this vector pair problem (in the exponent) would also refute SETH.


---

