• Facets (new session)
• Description
• Metadata
• Settings
  • Rule: ActivityStreamsMapasEquivalentb3sb3sifpdbprdf-labelfacetshttp://dbpedia.org/resource/inference/rules/dbpedia#http://dbpedia.org/resource/inference/rules/opencyc#http://dbpedia.org/resource/inference/rules/umbel#http://dbpedia.org/resource/inference/rules/yago#http://dbpedia.org/schema/property_rules#http://www.ontologyportal.org/inference/rules/SUMO#http://www.ontologyportal.org/inference/rules/WordNet#http://www.w3.org/2002/07/owl#ldpoplwebskos-transurn:det:rdf:labelvirtrdf-labelvirtrdf-urlNone
    
  • Inverse Functional Properties: Disabled (fastest) Apply to subjects only Apply to objects only Apply to both subjects and objects
  • "Same As": Disabled (fastest) Apply to subjects only Apply to objects only Apply to both subjects and objects (recommended) Apply to subjects, objects and predicates (not recommended on big datasets) Apply to predicates only (special use cases only)

About: 3SUM     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : yago:WikicatPolynomial-timeProblems, within Data Space : dbpedia.demo.openlinksw.com associated with source document(s)

Type: yago:WikicatUnsolvedProblemsInComputerScienceyago:Abstraction100002137yago:Attribute100024264yago:Condition113920835yago:Difficulty114408086yago:Problem114410605yago:State100024720yago:WikicatPolynomial-timeProblems New Facet based on Instances of this Class

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 .