Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Transdichotomous_model> ?p ?o }
Showing triples 1 to 38 of
38
with 100 triples per page.
- Transdichotomous_model 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 matter."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 trans-dichotomous 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.".
- Transdichotomous_model wikiPageID "30767413".
- Transdichotomous_model wikiPageLength "4367".
- Transdichotomous_model wikiPageOutDegree "13".
- Transdichotomous_model wikiPageRevisionID "569961893".
- Transdichotomous_model wikiPageWikiLink Analysis_of_algorithms.
- Transdichotomous_model wikiPageWikiLink Category:Computational_complexity_theory.
- Transdichotomous_model wikiPageWikiLink Computational_complexity_theory.
- Transdichotomous_model wikiPageWikiLink Computational_geometry.
- Transdichotomous_model wikiPageWikiLink Dan_Willard.
- Transdichotomous_model wikiPageWikiLink Graph_algorithm.
- Transdichotomous_model wikiPageWikiLink Integer.
- Transdichotomous_model wikiPageWikiLink Integer_sorting.
- Transdichotomous_model wikiPageWikiLink List_of_algorithms.
- Transdichotomous_model wikiPageWikiLink Michael_Fredman.
- Transdichotomous_model wikiPageWikiLink PSPACE-complete.
- Transdichotomous_model wikiPageWikiLink Priority_queue.
- Transdichotomous_model wikiPageWikiLink Random-access_machine.
- Transdichotomous_model wikiPageWikiLink Random_access_machine.
- Transdichotomous_model wikiPageWikiLink Word_(computer_architecture).
- Transdichotomous_model wikiPageWikiLink Word_size.
- Transdichotomous_model wikiPageWikiLinkText "Transdichotomous model".
- Transdichotomous_model wikiPageWikiLinkText "transdichotomous machine model".
- Transdichotomous_model wikiPageWikiLinkText "transdichotomous model".
- Transdichotomous_model hasPhotoCollection Transdichotomous_model.
- Transdichotomous_model wikiPageUsesTemplate Template:Math.
- Transdichotomous_model wikiPageUsesTemplate Template:Mvar.
- Transdichotomous_model wikiPageUsesTemplate Template:Reflist.
- Transdichotomous_model subject Category:Computational_complexity_theory.
- Transdichotomous_model hypernym Variation.
- Transdichotomous_model type Food.
- Transdichotomous_model 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.".
- Transdichotomous_model label "Transdichotomous model".
- Transdichotomous_model sameAs m.0gfd533.
- Transdichotomous_model sameAs Q7833959.
- Transdichotomous_model sameAs Q7833959.
- Transdichotomous_model wasDerivedFrom Transdichotomous_model?oldid=569961893.
- Transdichotomous_model isPrimaryTopicOf Transdichotomous_model.