Modelo transdicotómico

En la teoría de la complejidad computacional , y más específicamente en el análisis de algoritmos con datos enteros , el modelo transdicotómico es una variación de la máquina de acceso aleatorio en la que se supone que el tamaño de palabra de la máquina coincide con el tamaño del problema. El modelo fue propuesto por Michael Fredman y Dan Willard , ^{[ 1 ]} quienes eligieron su nombre "porque la dicotomía entre el modelo de la máquina y el tamaño del problema se cruza de manera razonable". ^{[ 2 ]}

En un problema como la ordenación de enteros, donde hay n enteros que ordenar, el modelo transdicotómico asume que cada entero puede almacenarse en una sola palabra de memoria de computadora, que las operaciones en palabras individuales toman un tiempo constante por operación, y que el número de bits que se pueden almacenar en una sola palabra es al menos log₂n _. El objetivo del análisis de complejidad en este modelo es encontrar límites de tiempo que dependan solo de n y no del tamaño real de los valores de entrada o las palabras de máquina. ^{[ 3 ] [ 4 ]} Al modelar el cálculo de enteros, es necesario asumir que las palabras de máquina tienen un tamaño limitado, porque los modelos con precisión ilimitada son irrazonablemente potentes (capaces de resolver problemas PSPACE-completos en tiempo polinomial). ^{[ 5 ]} El modelo transdicotómico hace una suposición mínima de este tipo: que hay algún límite, y que el límite es lo suficientemente grande como para permitir la indexación de acceso aleatorio en los datos de entrada. ^{[ 3 ]}

Además de su aplicación a la ordenación de enteros, el modelo transdicotómico también se ha aplicado al diseño de colas de prioridad ^{[ 6 ]} y a problemas en geometría computacional ^{[ 3 ]} y algoritmos de grafos . ^{[ 7 ]}

• Memoria RAM de palabras
• Modelo de sonda celular