TransWikia.com

Implication of solving 3SUM problem of a certain size on the Exponential Time Hypothesis

Theoretical Computer Science Asked on October 30, 2021

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.

2 Answers

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.

Answered by Avi Tal on October 30, 2021

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

Answered by Laakeri on October 30, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP