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 máquina y el tamaño del problema se cruza de manera razonable”. [2]
En un problema como la clasificación de enteros en la que hay n enteros para clasificar, el modelo transdicotómico asume que cada entero puede almacenarse en una sola palabra de la memoria de la computadora, que las operaciones en palabras únicas 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 2 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 suponer que las palabras de máquina tienen un tamaño limitado, porque los modelos con precisión ilimitada son irrazonablemente poderosos (capaces de resolver problemas completos de PSPACE en tiempo polinomial). [5] El modelo transdicotómico hace una suposición mínima de este tipo: que existe 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] ya problemas de geometría computacional [3] y algoritmos de grafos . [7]