Transdichotomous model
Encyclopedia
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 E. 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 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 . The goal of complexity analysis in this model is to find time bounds that depend only on 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 queue
s and to problems in computational geometry
and graph algorithms.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, and more specifically in the analysis of algorithms
Analysis of algorithms
To analyze an algorithm is to determine the amount of resources necessary to execute it. Most algorithms are designed to work with inputs of arbitrary length...
with integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
data, the transdichotomous model is a variation of the random access machine
Random access machine
In computer science, random access machine is an abstract machine in the general class of register machines. The RAM is very similar to the counter machine but with the added capability of 'indirect addressing' of its registers...
in which the machine word size is assumed to match the problem size. The model was proposed by Michael Fredman
Michael Fredman
Michael Lawrence Fredman is a professor at the Computer Science Department at Rutgers University, United States. He got his Ph. D. degree from Stanford University in 1972 under the supervision of Donald Knuth. He was a member of the mathematics department at the Massachusetts Institute of...
and Dan E. 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
Integer sorting
In computer science, integer sorting is the algorithmic problem of sorting a collection of data values by numeric keys, each of which is an integer. Algorithms designed for integer sorting may also often be applied to sorting problems in which the keys are floating point numbers or text strings...
in which there are 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 . The goal of complexity analysis in this model is to find time bounds that depend only on 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
PSPACE-complete
In complexity theory, a decision problem is PSPACE-complete if it is in the complexity class PSPACE, and every problem in PSPACE can be reduced to it in polynomial time...
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 queue
Priority queue
A priority queue is an abstract data type in computer programming.It is exactly like a regular queue or stack data structure, but additionally, each element is associated with a "priority"....
s and to problems in computational geometry
Computational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...
and graph algorithms.