Class Description

3SUM-hard: Problems hard for 3SUM

Defined in [GO95], 3SUM-hard is the set of problems ${\displaystyle P}$ for which 3SUM is reducible to a constant number of instances of ${\displaystyle P}$ with additional time ${\displaystyle o(n^{2})}$, using a real RAM model of computation as opposed to a Turing machine. That is, a problem is 3SUM-hard if 3SUM is reducible to it in sub-quadratic time.

Known to contain many problems from computational geometry, including:

• 3SUM': do there exist ${\displaystyle a,b,c}$ such that ${\displaystyle a+b=c}$?
• 3-Points-On-Line: given a set of points on the plane, does a line exist connecting three of them?

In [GO95], the authors list many more computational geometry problems in 3SUM-hard.

Using a model of computation strictly weaker than the real RAM machine model, a lower bound of ${\displaystyle \Omega (n^{2})}$ has been shown, but this model is weak enough that not all problems in 3SUM-hard are even decidable under the model.

Linked From

No class.