Class Description

3SUM-hard: Problems hard for 3SUM

Defined in [GO95], 3SUM-hard is the set of problems for which 3SUM is reducible to a constant number of instances of with additional time , 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:

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 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.