Matches in DBpedia 2014 for { <http://dbpedia.org/resource/3SUM> ?p ?o. }
Showing items 1 to 19 of
19
with 100 items per page.
- 3SUM abstract "In computational complexity theory, the 3SUM problem asks if a given set of integers, each with absolute value bounded by some polynomial in , contains three elements that sum to zero. The generalized version, rSUM, asks the same question of r elements. 3SUM can be easily solved in time, and matching lower bounds are known in some specialized models of computation (Erickson 1999). Slightly faster randomized algorithms are known that exploit computational-model parallelism on a RAM and in the external-memory and cache-oblivious models (Baran, Demaine & Pǎtraşcu 2008). When the integers are in the range , 3SUM can be solved in time by representing the input set as a bit vector, computing the set of all pairwise sums as a discrete convolution using the Fast Fourier transform, and finally comparing this set to .".
- 3SUM wikiPageExternalLink contents.html.
- 3SUM wikiPageExternalLink P11.html.
- 3SUM wikiPageExternalLink 3SUM_Algorithmica.
- 3SUM wikiPageExternalLink Welcome.html.
- 3SUM wikiPageExternalLink 3sumhard.pdf.
- 3SUM wikiPageID "506330".
- 3SUM wikiPageRevisionID "603742599".
- 3SUM hasPhotoCollection 3SUM.
- 3SUM subject Category:Computational_geometry.
- 3SUM subject Category:Polynomial-time_problems.
- 3SUM subject Category:Unsolved_problems_in_computer_science.
- 3SUM comment "In computational complexity theory, the 3SUM problem asks if a given set of integers, each with absolute value bounded by some polynomial in , contains three elements that sum to zero. The generalized version, rSUM, asks the same question of r elements. 3SUM can be easily solved in time, and matching lower bounds are known in some specialized models of computation (Erickson 1999).".
- 3SUM label "3SUM".
- 3SUM sameAs m.02jl6y.
- 3SUM sameAs Q4636407.
- 3SUM sameAs Q4636407.
- 3SUM wasDerivedFrom 3SUM?oldid=603742599.
- 3SUM isPrimaryTopicOf 3SUM.