Recientemente descubrí un límite inferior cuadrático en la complejidad de un problema en el modelo de árbol de decisión, y me pregunto si este resultado podría generalizarse parcialmente al modelo de máquina de acceso aleatorio. Por parcial , me refiero a una generalización de los programas de RAM con una cierta compensación tiempo / espacio. Por ejemplo, me gustaría mostrar que mi problema no puede resolverse con un programa RAM de espacio lineal y tiempo lineal.
AM Ben-Amram y Z. Galil demostraron en este documento que un programa RAM que se ejecuta en el tiempo y el espacio se puede simular en el tiempo en una máquina de puntero. ¿Conocemos resultados similares que podrían aplicarse a los árboles de decisión?s O ( t
Alternativamente, ¿es posible simular un programa RAM que se ejecute en el espacio con un árbol de decisión de grados ? (intuitivamente, el direccionamiento indirecto podría simularse utilizando nodos de grado )s ≤ s
Respuestas:
El modelo natural relacionado con los árboles de decisión que pueden simular RAM es el programa de ramificación. Básicamente, es un árbol de decisión con subárboles comunes unidos que producen un DAG. El tiempo T y el espacio S en una RAM se pueden simular en altura T y tamaño 2 ^ S en un programa de ramificación. (Es posible que deba utilizar la ramificación multidireccional).
Para problemas de decisión, está claro que cualquier árbol de decisión solo necesita altura = # entradas y espacio = total # de bits en la entrada. Tenga en cuenta que con la ramificación multidireccional uno podría tener los # bits en la entrada más grandes que la medida habitual del # de entradas (por ejemplo, n punteros que toman cada uno log n bits). Para tales problemas con nlog n total de bits de entrada, se puede demostrar que ciertos problemas no se pueden resolver en tiempo O (n) y espacio = O (n) bits. ¿Es esa la forma de tu problema?
Parece sugerir que está utilizando el número de salidas para tratar de obtener un límite inferior más grande. Es habitual que los problemas de múltiples salidas permitan muchas salidas a lo largo de un solo borde en lugar de en nodos de hoja (véase, por ejemplo, el documento de 1982 de Borodin-Cook sobre la clasificación de los límites inferiores). Sin embargo, incluso sin esta suposición, uno también puede calcular cualquier función con altura = # entradas y espacio = # bits de entrada. (Lea y recuerde la entrada y la salida de todos los valores en cada nodo hoja).
fuente
El modelo natural relacionado con los árboles de decisión que simula RAM sin pérdida es el programa de ramificación. Básicamente, es un árbol de decisión con subárboles comunes unidos que producen un DAG. El tiempo T y el espacio S en una RAM se pueden simular en altura T y tamaño 2 ^ S en un programa de ramificación. (Es posible que deba utilizar la ramificación multidireccional).
Para problemas de decisión, está claro que cualquier árbol de decisión solo necesita altura = # entradas y espacio = total # de bits en la entrada. Tenga en cuenta que con la ramificación multidireccional uno podría tener los # bits en la entrada más grandes que la medida habitual del # de entradas (por ejemplo, n punteros que toman cada uno log n bits). Para tales problemas con nlog n total de bits de entrada, se puede demostrar que ciertos problemas no pueden resolverse en tiempo O (n) y espacio = O (n) bits en una RAM.) ¿Esa es la forma de su problema?
Parece sugerir que está utilizando el número de salidas para tratar de obtener un límite inferior más grande. Sin embargo, incluso con esto, también puede calcular cualquier función con height = # input y space = # input bits. (Lea y recuerde la entrada y haga salir todos los valores requeridos en cada nodo hoja. Es habitual permitir múltiples salidas en un solo nodo).
fuente