| dbo:abstract |
In computational complexity theory, and more specifically in the analysis of algorithms with integer data, the transdichotomous model is a variation of the random access machine in which the machine word size is assumed to match the problem size. The model was proposed by Michael Fredman and Dan Willard, who chose its name "because the dichotomy between the machine model and the problem size is crossed in a reasonable manner." In a problem such as integer sorting in which there are n integers to be sorted, the transdichotomous model assumes that each integer may be stored in a single word of computer memory, that operations on single words take constant time per operation, and that the number of bits that can be stored in a single word is at least log2n. The goal of complexity analysis in this model is to find time bounds that depend only on n and not on the actual size of the input values or the machine words. In modeling integer computation, it is necessary to assume that machine words are limited in size, because models with unlimited precision are unreasonably powerful (able to solve PSPACE-complete problems in polynomial time). The transdichotomous model makes a minimal assumption of this type: that there is some limit, and that the limit is large enough to allow random access indexing into the input data. As well as its application to integer sorting, the transdichotomous model has also been applied to the design of priority queues and to problems in computational geometry and graph algorithms. (en) |
| dbo:wikiPageID |
30767413 (xsd:integer) |
| dbo:wikiPageLength |
4555 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID |
1032122927 (xsd:integer) |
| dbo:wikiPageWikiLink |
dbr:PSPACE-complete dbr:Analysis_of_algorithms dbr:Dan_Willard dbr:Computational_complexity_theory dbr:Computational_geometry dbr:Priority_queue dbr:Michael_Fredman dbr:Cell-probe_model dbc:Computational_complexity_theory dbc:Models_of_computation dbr:Graph_algorithm dbr:Integer dbr:Integer_sorting dbr:Word_RAM dbr:Word_size dbr:Random_access_machine |
| dbp:wikiPageUsesTemplate |
dbt:Math dbt:Mvar dbt:Reflist dbt:Comp-sci-theory-stub |
| dcterms:subject |
dbc:Computational_complexity_theory dbc:Models_of_computation |
| gold:hypernym |
dbr:Variation |
| rdf:type |
dbo:Food |
| rdfs:comment |
In computational complexity theory, and more specifically in the analysis of algorithms with integer data, the transdichotomous model is a variation of the random access machine in which the machine word size is assumed to match the problem size. The model was proposed by Michael Fredman and Dan Willard, who chose its name "because the dichotomy between the machine model and the problem size is crossed in a reasonable manner." (en) |
| rdfs:label |
Transdichotomous model (en) |
| owl:sameAs |
freebase:Transdichotomous model wikidata:Transdichotomous model https://global.dbpedia.org/id/4x1km |
| prov:wasDerivedFrom |
wikipedia-en:Transdichotomous_model?oldid=1032122927&ns=0 |
| foaf:isPrimaryTopicOf |
wikipedia-en:Transdichotomous_model |
| is dbo:wikiPageRedirects of |
dbr:Transdichotomous_RAM dbr:Transdichotomous_machine_model |
| is dbo:wikiPageWikiLink of |
dbr:Quicksort dbr:Block_sort dbr:Dan_Willard dbr:Transdichotomous_RAM dbr:Transdichotomous_machine_model dbr:Michael_Fredman dbr:Predecessor_problem dbr:AF-heap dbr:Integer_sorting dbr:Random-access_machine dbr:Word_RAM |
| is foaf:primaryTopic of |
wikipedia-en:Transdichotomous_model |