Transdichotomous model

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,[1] who chose its name "because the dichotomy between the machine model and the problem size is crossed in a reasonable matter."[2]

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.[3][4] 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).[5] 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.[3]

As well as its application to integer sorting, the transdichotomous model has also been applied to the design of priority queues[6] and to problems in computational geometry[3] and graph algorithms.[7]

References

  1. ↑ Fredman, Michael L.; Willard, Dan E. (1993), "Surpassing the information-theoretic bound with fusion trees", Journal of Computer and System Sciences, 47 (3): 424–436, doi:10.1016/0022-0000(93)90040-4, MR 1248864.
  2. ↑ Benoit, David; Demaine, Erik D.; Munro, J. Ian; Raman, Venkatesh, "Representing trees of higher degree", Algorithms and Data Structures: 6th International Workshop, WADS'99, p. 170.
  3. 1 2 3 Chan, Timothy M.; Pǎtraşcu, Mihai (2009), "Transdichotomous Results in Computational Geometry, I: Point Location in Sublogarithmic Time" (PDF), SIAM Journal on Computing, 39 (2): 703–729, doi:10.1137/07068669X.
  4. ↑ Chan, Timothy M.; Pǎtraşcu, Mihai (2010), Transdichotomous Results in Computational Geometry, II: Offline Search, arXiv:1010.1948Freely accessible.
  5. ↑ Bertoni, Alberto; Mauri, Giancarlo; Sabadini, Nicoletta (1981), "A characterization of the class of functions computable in polynomial time on Random Access Machines", Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing (STOC '81), pp. 168–176, doi:10.1145/800076.802470.
  6. ↑ Raman, Rajeev, "Priority Queues: Small, Monotone and Trans-dichotomous", Proceedings of the Fourth Annual European Symposium on Algorithms (ESA '96), Lecture Notes in Computer Science, 1136, Springer-Verlag, pp. 121–137, doi:10.1007/3-540-61680-2_51.
  7. ↑ Fredman, Michael L.; Willard, Dan E. (1994), "Trans-dichotomous algorithms for minimum spanning trees and shortest paths", Journal of Computer and System Sciences, 48 (3): 533–551, doi:10.1016/S0022-0000(05)80064-9.
This article is issued from Wikipedia - version of the 8/24/2013. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.