| dbo:abstract
|
- In computational complexity theory, the 3SUM problem asks if a given set of real numbers contains three elements that sum to zero. A generalized version, k-SUM, asks the same question on k numbers. 3SUM can be easily solved in time, and matching lower bounds are known in some specialized models of computation. It was conjectured that any deterministic algorithm for the 3SUM requires time.In 2014, the original 3SUM conjecture was refuted by Allan Grønlund and Seth Pettie who gave a deterministic algorithm that solves 3SUM in time.Additionally, Grønlund and Pettie showed that the 4-linear decision tree complexity of 3SUM is .These bounds were subsequently improved.The current best known algorithm for 3SUM runs in time.Kane, Lovett, and Moran showed that the 6-linear decision tree complexity of 3SUM is . The latter bound is tight (up to a logarithmic factor). It is still conjectured that 3SUM is unsolvable in expected time. When the elements are integers 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 . (en)
- 在计算复杂度理论中, 3SUM问题是指如下的问题：给定一个包含n个实数的集合，判断其中是否包含3个和为0的元素。问题也可以推广到一个更一般化的版本，rSUM，是要求判断集合中是否存在r个数的和为0。3SUM问题可以很容易地在的时间复杂度内解决。对于某些特化的计算模型，这已经达到了它们的复杂度下界。 人们曾经猜想任何3SUM问题的确定性算法都至少需要的时间复杂度。然而在2014年，最初的3SUM被Allan Grønlund和Seth Pettie否决了。他们给出了一个能在能在的时间复杂度内求解3SUM问题的确定性算法。目前仍然有人猜想3SUM是不可能在的时间复杂度内解决的。 (zh)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 16922 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- 在计算复杂度理论中, 3SUM问题是指如下的问题：给定一个包含n个实数的集合，判断其中是否包含3个和为0的元素。问题也可以推广到一个更一般化的版本，rSUM，是要求判断集合中是否存在r个数的和为0。3SUM问题可以很容易地在的时间复杂度内解决。对于某些特化的计算模型，这已经达到了它们的复杂度下界。 人们曾经猜想任何3SUM问题的确定性算法都至少需要的时间复杂度。然而在2014年，最初的3SUM被Allan Grønlund和Seth Pettie否决了。他们给出了一个能在能在的时间复杂度内求解3SUM问题的确定性算法。目前仍然有人猜想3SUM是不可能在的时间复杂度内解决的。 (zh)
- In computational complexity theory, the 3SUM problem asks if a given set of real numbers contains three elements that sum to zero. A generalized version, k-SUM, asks the same question on k numbers. 3SUM can be easily solved in time, and matching lower bounds are known in some specialized models of computation. When the elements are integers 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 . (en)
|
| rdfs:label
| |
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
