Transdichotomous model

Last updated

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 manner." [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 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. [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]

See also

Related Research Articles

The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved.

In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem.

In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm.

<span class="mw-page-title-main">Time complexity</span> Estimate of time taken for running an algorithm

In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor.

A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random determined by the random bits; thus either the running time, or the output are random variables.

In computer science, a selection algorithm is an algorithm for finding the th smallest value in a collection of ordered values, such as numbers. The value that it finds is called the th order statistic. Selection includes as special cases the problems of finding the minimum, median, and maximum element in the collection. Selection algorithms include quickselect, and the median of medians algorithm. When applied to a collection of values, these algorithms take linear time, as expressed using big O notation. For data that is already structured, faster algorithms may be possible; as an extreme case, selection in an already-sorted array takes time .

In computer science, a fusion tree is a type of tree data structure that implements an associative array on w-bit integers on a finite universe, where each of the input integers has size less than 2w and is non-negative. When operating on a collection of n key–value pairs, it uses O(n) space and performs searches in O(logwn) time, which is asymptotically faster than a traditional self-balancing binary search tree, and also better than the van Emde Boas tree for large values of w. It achieves this speed by using certain constant-time operations that can be done on a machine word. Fusion trees were invented in 1990 by Michael Fredman and Dan Willard.

Algorithmic topology, or computational topology, is a subfield of topology with an overlap with areas of computer science, in particular, computational geometry and computational complexity theory.

In computer science, the AF-heap is a type of priority queue for integer data, an extension of the fusion tree using an atomic heap proposed by M. L. Fredman and D. E. Willard.

<span class="mw-page-title-main">Range searching</span>

In computer science, the range searching problem consists of processing a set S of objects, in order to determine which objects from S intersect with a query object, called the range. For example, if S is a set of points corresponding to the coordinates of several cities, find the subset of cities within a given range of latitudes and longitudes.

In computational complexity theory, the average-case complexity of an algorithm is the amount of some computational resource used by the algorithm, averaged over all possible inputs. It is frequently contrasted with worst-case complexity which considers the maximal complexity of the algorithm over all possible inputs.

In computing, especially computational geometry, a real RAM is a mathematical model of a computer that can compute with exact real numbers instead of the binary fixed point or floating point numbers used by most actual computers. The real RAM was formulated by Michael Ian Shamos in his 1978 Ph.D. dissertation.

In computer science, integer sorting is the algorithmic problem of sorting a collection of data values by integer keys. Algorithms designed for integer sorting may also often be applied to sorting problems in which the keys are floating point numbers, rational numbers, or text strings. The ability to perform integer arithmetic on the keys allows integer sorting algorithms to be faster than comparison sorting algorithms in many cases, depending on the details of which operations are allowed in the model of computing and how large the integers to be sorted are.

<span class="mw-page-title-main">Mihai Pătrașcu (computer scientist)</span> Romanian-American computer scientist

Mihai Pătrașcu was a Romanian-American computer scientist at AT&T Labs in Florham Park, New Jersey, USA.

In computer science, the cell-probe model is a model of computation similar to the random-access machine, except that all operations are free except memory access. This model is useful for proving lower bounds of algorithms for data structure problems.

Dan Edward Willard was an American computer scientist and logician, and a professor of computer science at the University at Albany.

<i>X</i> + <i>Y</i> sorting Problem of sorting pairs of numbers by their sum

In computer science, sorting is the problem of sorting pairs of numbers by their sums. Applications of the problem include transit fare minimisation, VLSI design, and sparse polynomial multiplication. As with comparison sorting and integer sorting more generally, algorithms for this problem can be based only on comparisons of these sums, or on other operations that work only when the inputs are small integers.

In theoretical computer science, the word RAM model is a model of computation in which a random-access machine does bitwise operations on a word of w bits. Michael Fredman and Dan Willard created it in 1990 to simulate programming languages like C.

In computer science, the predecessor problem involves maintaining a set of items to, given an element, efficiently query which element precedes or succeeds that element in an order. Data structures used to solve the problem include balanced binary search trees, van Emde Boas trees, and fusion trees. In the static predecessor problem, the set of elements does not change, but in the dynamic predecessor problem, insertions into and deletions from the set are allowed.

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.1948 , Bibcode:2010arXiv1010.1948C .
  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, S2CID   12878381 .
  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, vol. 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 page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.