In
computational complexity theory
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 ...
, and more specifically in the
analysis of algorithms with
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
data, the transdichotomous model is a variation of the
random access machine in which the machine
word size
In computing, a word is the natural unit of data used by a particular processor design. A word is a fixed-sized datum handled as a unit by the instruction set or the hardware of the processor. The number of bits or digits in a word (the ''word s ...
is assumed to match the problem size. The model was proposed by
Michael Fredman
Michael Lawrence Fredman is an emeritus professor at the Computer Science Department at Rutgers University, United States. He earned his Ph.D. degree from Stanford University in 1972 under the supervision of Donald Knuth. He was a member of the ...
and
Dan Willard
Dan Edward Willard is an American computer scientist and logician, and is a professor of computer science at the University at Albany.
Education and career
Willard did his undergraduate studies in mathematics at Stony Brook University, graduati ...
, 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 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 numb ...
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 In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length (polynomial space) and if every other problem that can be solved in polynomial space can b ...
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 algorithm
The following is a list of well-known algorithms along with one-line descriptions for each.
Automated planning
Combinatorial algorithms
General combinatorial algorithms
* Brent's algorithm: finds a cycle in function value iterations using on ...
s.
[.]
See also
*
Word RAM In theoretical computer science, the word RAM (word random-access machine) model is a model of computation in which a random-access machine does bitwise operations on a word of bits. Michael Fredman and Dan Willard created it in 1990 to simulate p ...
*
Cell-probe model
References
Computational complexity theory
Models of computation
{{comp-sci-theory-stub