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.


1 Answer 1


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.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.