6
$\begingroup$

In the recent question 3SUM Complexity—A special(?) Case I asked about why the set size $O(n^3)$ was an interesting value for the 3SUM Problem and got a nice answer. My reference was the paper “Consequences of Faster Alignment of Sequences” by Abboud, Vassilevska Williams, and Weimann available [here][1]. The term of a certain size in the title of this question refers to the support set being $\{-n^3,\ldots,n^3\}$:

Conjecture 1 (3-SUM Conjecture) In the Word RAM model with words of $O(\log n)$ bits, any algorithm requires $n^{2−o(1)}$ time in expectation to determine whether three sets $A,B,C \subset \{−n^3,\ldots,n^3\}$ with $|A| = |B| = |C| = n$ integers contain three elements $a∈A,b∈B,c∈C$ with $a+b+c=0.$

If there was an algorithm solving this exact version of 3SUM with complexity $O(n^{2-\varepsilon})$ for $\varepsilon>0,$ what would be the impact on the Exponential Time Hypothesis?

Again, not being an expert, I am wondering would the ETH be refuted? Or the strong ETH only? Please feel free to include details that may be "obvious" in your comments and answers.

$\endgroup$
  • 2
    $\begingroup$ The answers are great, I just want to add one more comment. If you were able to solve k-SUM in (for example) n^(k/log log log log k + O(1)} time (for k as some slow-growing function of n) then ETH would indeed be false. This result appears in M. Patrascu and R. Williams, SODA 2010. $\endgroup$ – Ryan Williams Jul 12 at 6:32
9
$\begingroup$

I think currently it is not even known if strong ETH and 3SUM are related, see e.g. [1]. For the relation of ETH and 3SUM, note that ETH really cannot be refuted by improving polynomial time algorithms (at least via Karp reductions) because it would only improve constants in the exponent of the runtime. In particular, if we reduce 3-SAT to a 3SUM instance of size $2^{O(n)}$, it will not refute ETH, and if we reduce 3-SAT to a 3SUM instance of size $2^{o(n)}$, it will refute ETH regardless of the complexity of 3SUM.

[1] Virginia V. Williams. Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk). IPEC 2015. https://drops.dagstuhl.de/opus/volltexte/2015/5568/pdf/5.pdf

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

The following excellent video:

https://www.youtube.com/watch?v=YRiyqc99kd0&t=2661s

and this one:

https://www.youtube.com/watch?v=x-HskkxUuVI&t=1965s

Deals with this issue and Fine Grained Approach to Complexity in general.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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