Encyclopedia  |   World Factbook  |   World Flags  |   Reference Tables  |   List of Lists     
   Academic Disciplines  |   Historical Timeline  |   Themed Timelines  |   Biographies  |   How-Tos     
Sponsor by The Tattoo Collection
Main Page | See live article | Alphabetical index


In computational geometry a problem is called 3sum-hard if solving it in subquadratic time implies a subquadratic-time algorithm for the following problem:
Given a set S of n integers, are there elements a, b, c in S such that a + b + c = 0?
There is a simple algorithm to solve 3sum in O(n2) time. This is the fastest algorithm known, but matching lower bounds are only known in very specialized models of computation. The concept of 3sum-hardness was introduced by Gajentaan and Overmars [GO95]. By now there is a multitude of problems that falls into this category. (Add REFS)