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 la 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 el ordenamiento de números enteros en el que hay n números enteros para ordenar, el modelo transdicotómico supone que cada número entero puede almacenarse en una sola palabra de la memoria de la computadora, que las operaciones sobre palabras individuales toman un tiempo constante por operación y que la cantidad 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 números 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 PSPACE-completos 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 números enteros, el modelo transdicotómico también se ha aplicado al diseño de colas de prioridad [6] y a problemas de geometría computacional [3] y algoritmos de grafos . [7]