Modelo de árbol de decisión

Modelo de complejidad computacional.

Modelo de árbol de decisión

En complejidad computacional, el modelo de árbol de decisión es el modelo de computación en el que un algoritmo se considera básicamente un árbol de decisión , es decir, una secuencia de consultas o pruebas que se realizan de forma adaptativa, por lo que el resultado de las pruebas anteriores puede influir en las pruebas realizadas a continuación. .

Normalmente, estas pruebas tienen una pequeña cantidad de resultados (como una pregunta de sí o no ) y se pueden realizar rápidamente (digamos, con un costo computacional unitario), por lo que la complejidad temporal del peor de los casos de un algoritmo en el modelo de árbol de decisión corresponde a la profundidad del árbol de decisión correspondiente. Esta noción de complejidad computacional de un problema o un algoritmo en el modelo de árbol de decisión se denomina complejidad del árbol de decisión o complejidad de la consulta .

Los modelos de árboles de decisión son fundamentales para establecer límites inferiores para la teoría de la complejidad para ciertas clases de problemas y algoritmos computacionales. Se han introducido varias variantes de modelos de árbol de decisión, según el modelo computacional y el tipo de algoritmos de consulta que se permite realizar.

Por ejemplo, se utiliza un argumento de árbol de decisión para mostrar que un tipo de elementos de comparación deben admitir comparaciones. Para los tipos de comparación, una consulta es una comparación de dos elementos , con dos resultados (suponiendo que ningún elemento sea igual): o o . Las clasificaciones de comparación se pueden expresar como un árbol de decisión en este modelo, ya que dichos algoritmos de clasificación solo realizan este tipo de consultas. ${\displaystyle n}$ ${\displaystyle n\log(n)}$ ${\displaystyle a,\,b}$ ${\displaystyle a<b}$ ${\displaystyle a>b}$

Árboles de comparación y límites inferiores para ordenar

Los árboles de decisión se emplean a menudo para comprender algoritmos de clasificación y otros problemas similares; Esto lo hicieron por primera vez Ford y Johnson. ^[1]

Por ejemplo, muchos algoritmos de clasificación son clasificaciones por comparación , lo que significa que solo obtienen información sobre una secuencia de entrada a través de comparaciones locales: probando si , o . Suponiendo que los elementos que se van a clasificar son todos distintos y comparables, esto se puede reformular como una pregunta de sí o no: ¿es ? ${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$ ${\displaystyle x_{i}<x_{j}}$ ${\displaystyle x_{i}=x_{j}}$ ${\displaystyle x_{i}>x_{j}}$ ${\displaystyle x_{i}>x_{j}}$

Estos algoritmos se pueden modelar como árboles de decisión binarios, donde las consultas son comparaciones: un nodo interno corresponde a una consulta y los hijos del nodo corresponden a la siguiente consulta cuando la respuesta a la pregunta es sí o no. Para los nodos hoja, la salida corresponde a una permutación que describe cómo se codificó la secuencia de entrada a partir de la lista de elementos completamente ordenada. (El inverso de esta permutación, reordena la secuencia de entrada). ${\displaystyle \pi }$ ${\displaystyle \pi ^{-1}}$

Se puede demostrar que los tipos de comparación deben utilizar comparaciones mediante un argumento simple: para que un algoritmo sea correcto, debe poder generar todas las permutaciones posibles de elementos; de lo contrario, el algoritmo fallaría para esa permutación particular como entrada. Entonces, su árbol de decisión correspondiente debe tener al menos tantas hojas como permutaciones: hojas. Cualquier árbol binario con al menos hojas tiene una profundidad de al menos , por lo que este es un límite inferior en el tiempo de ejecución de un algoritmo de clasificación por comparación. En este caso, la existencia de numerosos algoritmos de clasificación y comparación que tienen esta complejidad temporal, como mergesort y heapsort , demuestra que el límite es estrecho. ^{[2] : 91} ${\displaystyle \Omega (n\log(n))}$ ${\displaystyle n}$ ${\displaystyle n!}$ ${\displaystyle n!}$ ${\displaystyle \log _{2}(n!)=\Omega (n\log _{2}(n))}$

Este argumento no utiliza nada sobre el tipo de consulta, por lo que de hecho demuestra un límite inferior para cualquier algoritmo de clasificación que pueda modelarse como un árbol de decisión binario. En esencia, se trata de una reformulación del argumento de la teoría de la información de que un algoritmo de clasificación correcto debe aprender al menos bits de información sobre la secuencia de entrada. Como resultado, esto también funciona para árboles de decisión aleatorios. ${\displaystyle \log _{2}(n!)}$

Otros límites inferiores del árbol de decisión utilizan que la consulta es una comparación. Por ejemplo, considere la tarea de usar únicamente comparaciones para encontrar el número más pequeño entre los números. Antes de que se pueda determinar el número más pequeño, todos los números excepto el más pequeño deben "perder" (comparar con los mayores) en al menos una comparación. Por lo tanto, se necesitan al menos comparaciones para encontrar el mínimo. (El argumento de la teoría de la información aquí solo da un límite inferior de ). Un argumento similar funciona para límites inferiores generales para calcular estadísticas de orden . ^{[2] : 214} ${\displaystyle n}$ ${\displaystyle n-1}$ ${\displaystyle \log(n)}$

Árboles de decisión lineales y algebraicos.

Los árboles de decisión lineal generalizan los árboles de decisión de comparación anteriores a funciones informáticas que toman vectores reales como entrada. Las pruebas en árboles de decisión lineal son funciones lineales: para una elección particular de números reales , genera el signo de . (Los algoritmos en este modelo solo pueden depender del signo de la salida). Los árboles de comparación son árboles de decisión lineales, porque la comparación entre y corresponde a la función lineal . Según su definición, los árboles de decisión lineal sólo pueden especificar funciones cuyas fibras pueden construirse tomando uniones e intersecciones de semiespacios. ${\displaystyle x\in \mathbb {R} ^{n}}$ ${\displaystyle a_{0},\dots ,a_{n}}$ ${\displaystyle a_{0}+\textstyle \sum _{i=1}^{n}a_{i}x_{i}}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{j}}$ ${\displaystyle x_{i}-x_{j}}$ ${\displaystyle f}$

Los árboles de decisión algebraicos son una generalización de los árboles de decisión lineales que permiten que las funciones de prueba sean polinomios de grado . Geométricamente, el espacio se divide en conjuntos semialgebraicos (una generalización del hiperplano). ${\displaystyle d}$

Estos modelos de árboles de decisión, definidos por Rabin ^[3] y Reingold, ^[4] se utilizan a menudo para demostrar límites inferiores en geometría computacional . ^[5] Por ejemplo, Ben-Or demostró que la unicidad del elemento (la tarea de calcular , donde es 0 si y sólo si existen coordenadas distintas tales que ) requiere un árbol de decisión algebraico de profundidad . ^[6] Esto fue demostrado por primera vez para modelos de decisión lineal por Dobkin y Lipton. ^[7] También muestran un límite inferior para los árboles de decisión lineales en el problema de la mochila, generalizado a árboles de decisión algebraicos por Steele y Yao. ^[8] ${\displaystyle f:\mathbb {R} ^{n}\to \{0,1\}}$ ${\displaystyle f(x)}$ ${\displaystyle i,j}$ ${\displaystyle x_{i}=x_{j}}$ ${\displaystyle \Omega (n\log(n))}$ ${\displaystyle n^{2}}$

Complejidades del árbol de decisión booleano

Para los árboles de decisión booleanos, la tarea es calcular el valor de una función booleana de n bits para una entrada . Las consultas corresponden a leer un bit de la entrada, y la salida es . Cada consulta puede depender de consultas anteriores. Hay muchos tipos de modelos computacionales que utilizan árboles de decisión que podrían considerarse, admitiendo múltiples nociones de complejidad, llamadas medidas de complejidad . ${\displaystyle f:\{0,1\}^{n}\to \{0,1\}}$ ${\displaystyle x\in \{0,1\}^{n}}$ ${\displaystyle x_{i}}$ ${\displaystyle f(x)}$

Árbol de decisión determinista

Si la salida de un árbol de decisión es , para todos , se dice que el árbol de decisión "calcula" . La profundidad de un árbol es el número máximo de consultas que pueden ocurrir antes de llegar a una hoja y obtener un resultado. , la complejidad del árbol de decisión determinista es la profundidad más pequeña entre todos los árboles de decisión deterministas que calculan . ${\displaystyle f(x)}$ ${\displaystyle x\in \{0,1\}^{n}}$ ${\displaystyle f}$ ${\displaystyle D(f)}$ ${\displaystyle f}$ ${\displaystyle f}$

Árbol de decisión aleatorio

Una forma de definir un árbol de decisión aleatorio es agregar nodos adicionales al árbol, cada uno controlado por una probabilidad . Otra definición equivalente es definirla como una distribución sobre árboles de decisión deterministas. Con base en esta segunda definición, la complejidad del árbol aleatorio se define como la mayor profundidad entre todos los árboles que sustentan la distribución subyacente. se define como la complejidad del árbol de decisión aleatorio de menor profundidad cuyo resultado tiene probabilidad al menos para todos (es decir, con error bilateral acotado). ${\displaystyle p_{i}}$ ${\displaystyle R_{2}(f)}$ ${\displaystyle f(x)}$ ${\displaystyle 2/3}$ ${\displaystyle x\in \{0,1\}^{n}}$

${\displaystyle R_{2}(f)}$Se conoce como complejidad del árbol de decisión aleatorio de Monte Carlo , porque se permite que el resultado sea incorrecto con un error bilateral acotado. La complejidad del árbol de decisiones de Las Vegas mide la profundidad esperada de un árbol de decisión que debe ser correcto (es decir, que tenga error cero). También hay una versión de error acotado unilateral que se indica con . ${\displaystyle R_{0}(f)}$ ${\displaystyle R_{1}(f)}$

Árbol de decisión no determinista

La complejidad del árbol de decisión no determinista de una función se conoce más comúnmente como complejidad del certificado de esa función. Mide el número de bits de entrada que un algoritmo no determinista necesitaría considerar para evaluar la función con certeza.

Formalmente, la complejidad del certificado de at es el tamaño del subconjunto más pequeño de índices tales que, para todos , si para todos , entonces . La complejidad del certificado es la complejidad máxima del certificado en general . Se denota la noción análoga en la que sólo se requiere que el verificador sea correcto con 2/3 de probabilidad . ${\displaystyle f}$ ${\displaystyle x}$ ${\displaystyle S\subset [n]}$ ${\displaystyle y\in \{0,1\}^{n}}$ ${\displaystyle y_{i}=x_{i}}$ ${\displaystyle i\in S}$ ${\displaystyle f(y)=f(x)}$ ${\displaystyle f}$ ${\displaystyle x}$ ${\displaystyle RC(f)}$

Árbol de decisión cuántica

La complejidad del árbol de decisión cuántica es la profundidad del árbol de decisión cuántico de menor profundidad que da el resultado con probabilidad al menos para todos . Otra cantidad, , se define como la profundidad del árbol de decisión cuántico de menor profundidad que da el resultado con probabilidad 1 en todos los casos (es decir, calcula exactamente). y se conocen más comúnmente como complejidades de consultas cuánticas , porque la definición directa de un árbol de decisión cuántica es más complicada que en el caso clásico. De manera similar al caso aleatorio, definimos y . ${\displaystyle Q_{2}(f)}$ ${\displaystyle f(x)}$ ${\displaystyle 2/3}$ ${\displaystyle x\in \{0,1\}^{n}}$ ${\displaystyle Q_{E}(f)}$ ${\displaystyle f(x)}$ ${\displaystyle f}$ ${\displaystyle Q_{2}(f)}$ ${\displaystyle Q_{E}(f)}$ ${\displaystyle Q_{0}(f)}$ ${\displaystyle Q_{1}(f)}$

Estas nociones suelen estar limitadas por las nociones de grado y grado aproximado. El grado de , denotado , es el grado más pequeño de cualquier polinomio que satisfaga a todos . El grado aproximado de , denotado , es el grado más pequeño de cualquier polinomio que satisfaga siempre y cuando sea . ${\displaystyle f}$ ${\displaystyle \deg(f)}$ ${\displaystyle p}$ ${\displaystyle f(x)=p(x)}$ ${\displaystyle x\in \{0,1\}^{n}}$ ${\displaystyle f}$ ${\displaystyle {\widetilde {\deg }}(f)}$ ${\displaystyle p}$ ${\displaystyle p(x)\in [0,1/3]}$ ${\displaystyle f(x)=0}$ ${\displaystyle p(x)\in [2/3,1]}$ ${\displaystyle f(x)=1}$

Beals et al. estableció que y . ^[9] ${\displaystyle Q_{0}(f)\geq \deg(f)/2}$ ${\displaystyle Q_{2}(f)\geq {\widetilde {\deg }}(f)/2}$

Relaciones entre medidas de complejidad de funciones booleanas

De las definiciones se deduce inmediatamente que para funciones booleanas de todos los bits , y . Encontrar los mejores límites superiores en la dirección inversa es un objetivo importante en el campo de la complejidad de las consultas. ${\displaystyle n}$ ${\displaystyle f}$ ${\displaystyle Q_{2}(f)\leq R_{2}(f)\leq R_{1}(f)\leq R_{0}(f)\leq D(f)\leq n}$ ${\displaystyle Q_{2}(f)\leq Q_{0}(f)\leq D(f)\leq n}$

Todos estos tipos de complejidad de consultas están relacionados polinómicamente. Blum e Impagliazzo, ^[10] Hartmanis y Hemachandra, ^[11] y Tardos ^[12] descubrieron de forma independiente que . Noam Nisan descubrió que la complejidad del árbol de decisión aleatorio de Monte Carlo también está polinomialmente relacionada con la complejidad del árbol de decisión determinista: . ^[13] (Nisan también demostró que .) Se conoce una relación más estrecha entre los modelos Monte Carlo y Las Vegas :. ^[14] Esta relación es óptima hasta factores polilogarítmicos. ^[15] En cuanto a las complejidades del árbol de decisión cuántica, este límite es estrecho. ^{[16] [15]} Midrijanis demostró que , ^{[17] [18]} mejoraba un límite cuártico debido a Beals et al. ^[9] ${\displaystyle D(f)\leq R_{0}(f)^{2}}$ ${\displaystyle D(f)=O(R_{2}(f)^{3})}$ ${\displaystyle D(f)=O(R_{1}(f)^{2})}$ ${\displaystyle R_{0}(f)=O(R_{2}(f)^{2}\log R_{2}(f))}$ ${\displaystyle D(f)=O(Q_{2}(f)^{4})}$ ${\displaystyle D(f)=O(Q_{0}(f)^{3})}$

Es importante señalar que estas relaciones polinómicas son válidas sólo para funciones booleanas totales . Para funciones booleanas parciales , que tienen un dominio como subconjunto de , es posible una separación exponencial entre y ; El primer ejemplo de tal problema fue descubierto por Deutsch y Jozsa . ${\displaystyle \{0,1\}^{n}}$ ${\displaystyle Q_{0}(f)}$ ${\displaystyle D(f)}$

Conjetura de sensibilidad

Para una función booleana , la sensibilidad de se define como la sensibilidad máxima de sobre todo , donde la sensibilidad de at es el número de cambios de un solo bit que cambian el valor de . La sensibilidad está relacionada con la noción de influencia total proveniente del análisis de funciones booleanas , que es igual a la sensibilidad promedio sobre todo . ${\displaystyle f:\{0,1\}^{n}\to \{0,1\}}$ ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle x}$ ${\displaystyle f}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle f(x)}$ ${\displaystyle x}$

La conjetura de sensibilidad es la conjetura de que la sensibilidad está relacionada polinomialmente con la complejidad de la consulta; es decir, existe un exponente tal que, para todos , y . Se puede demostrar mediante un argumento simple que , por lo que la conjetura se refiere específicamente a encontrar un límite inferior para la sensibilidad. Dado que todas las medidas de complejidad analizadas anteriormente están relacionadas polinómicamente, el tipo preciso de medida de complejidad no es relevante. Sin embargo, esto suele plantearse como una cuestión de relacionar la sensibilidad con la sensibilidad del bloque. ${\displaystyle c,c'}$ ${\displaystyle f}$ ${\displaystyle D(f)=O(s(f)^{c})}$ ${\displaystyle s(f)=O(D(f)^{c'})}$ ${\displaystyle s(f)\leq D(f)}$

La sensibilidad de bloque de , denotada , se define como la sensibilidad de bloque máxima de todo . La sensibilidad del bloque de at es el número máximo de subconjuntos disjuntos tales que, para cualquiera de los subconjuntos , al invertir los bits de correspondientes a cambia el valor de . ^[13] ${\displaystyle f}$ ${\displaystyle bs(f)}$ ${\displaystyle f}$ ${\displaystyle x}$ ${\displaystyle f}$ ${\displaystyle x}$ ${\displaystyle t}$ ${\displaystyle S_{1},\ldots ,S_{t}\subset [n]}$ ${\displaystyle S_{i}}$ ${\displaystyle x}$ ${\displaystyle S_{i}}$ ${\displaystyle f(x)}$

En 2019, Hao Huang demostró la conjetura de la sensibilidad y demostró que . ^{[19] [20]} ${\displaystyle bs(f)=O(s(f)^{4})}$

Ver también

• Ordenación por comparación
• Árbol de decisión
• Conjetura de Aanderaa-Karp-Rosenberg
• Árbol de expansión mínima § Árboles de decisión

Referencias

1. Ford, Lester R. Jr.; Johnson, Selmer M. (1 de mayo de 1959). "Un problema de torneo". El Mensual Matemático Estadounidense . 66 (5): 387–389. doi :10.1080/00029890.1959.11989306. ISSN  0002-9890.
2. Introducción a los algoritmos. Cormen, Thomas H. (Tercera ed.). Cambridge, Massachusetts: MIT Press. 2009.ISBN​ 978-0-262-27083-0. OCLC  676697295.{{cite book}}: CS1 maint: others (link)
3. Rabin, Michael O. (1 de diciembre de 1972). "Demostrar la positividad simultánea de formas lineales". Revista de Ciencias de la Computación y de Sistemas . 6 (6): 639–650. doi : 10.1016/S0022-0000(72)80034-5 . ISSN  0022-0000.
4. Reingold, Edward M. (1 de octubre de 1972). "Sobre la optimización de algunos algoritmos establecidos". Revista de la ACM . 19 (4): 649–659. doi : 10.1145/321724.321730 . ISSN  0004-5411. S2CID  18605212.
5. Preparata, Franco P. (1985). Geometría computacional: una introducción. Shamos, Michael Ian. Nueva York: Springer-Verlag. ISBN 0-387-96131-3. OCLC  11970840.
6. Ben-Or, Michael (1 de diciembre de 1983). "Límites inferiores de árboles de cálculo algebraico". Actas del decimoquinto simposio anual de ACM sobre teoría de la informática - STOC '83 . STOC '83. Nueva York, NY, EE.UU.: Asociación de Maquinaria de Computación. págs. 80–86. doi : 10.1145/800061.808735 . ISBN 978-0-89791-099-6. S2CID  1499957.
7. Dobkin, David; Lipton, Richard J. (1 de junio de 1976). "Problemas de búsqueda multidimensional". Revista SIAM de Computación . 5 (2): 181–186. doi :10.1137/0205015. ISSN  0097-5397.
8. Michael Steele, J; Yao, Andrew C (1 de marzo de 1982). "Límites inferiores de árboles de decisión algebraicos". Revista de algoritmos . 3 (1): 1–8. doi :10.1016/0196-6774(82)90002-5. ISSN  0196-6774.
9. Beals, R.; Buhrman, H.; Inteligente.; Mosca, M.; de Wolf, R. (2001). "Límites inferiores cuánticos por polinomios". Revista de la ACM . 48 (4): 778–797. arXiv : quant-ph/9802049 . doi :10.1145/502090.502097. S2CID  1078168.
10. Blum, M.; Impagliazzo, R. (1987). "Oráculos genéricos y clases de oráculos". Actas del 18º IEEE FOCS . págs. 118-126.
11. Hartmanis, J.; Hemachandra, L. (1987), "Funciones unidireccionales, robustez y no isomorfismo de conjuntos NP-completos", Informe técnico DCS TR86-796, Universidad de Cornell
12. Tardos, G. (1989). "Complejidad de la consulta, o ¿por qué es difícil separar NP ^A  ∩  coNP ^A de P ^A mediante oráculos aleatorios A ?". Combinatoria . 9 (4): 385–392. doi :10.1007/BF02125350. S2CID  45372592.
13. Nisan, N. (1989). "CREW PRAM y árboles de decisión". Actas del 21º ACM STOC . págs. 327–335.
14. Kulkarni, R. y Tal, A. Sobre la sensibilidad del bloque fraccional. Coloquio Electrónico sobre Complejidad Computacional (ECCC). vol. 20. 2013.
15. Ambainis, Andris; Balodis, Kaspars; Belovs, Aleksandrs; Lee, Troya; Santa, Miklos; Smotrovs, Juris (4 de septiembre de 2017). "Separaciones en la complejidad de consultas basadas en funciones de puntero". Revista de la ACM . 64 (5): 32:1–32:24. arXiv : 1506.04719 . doi :10.1145/3106234. ISSN  0004-5411. S2CID  10214557.
16. Aaronson, Scott; Ben-David, Shalev; Kothari, Robin; Rao, Sravas; Tal, Avishay (23 de octubre de 2020). "Grado versus grado aproximado e implicaciones cuánticas del teorema de sensibilidad de Huang". arXiv : 2010.12629 [cuántico-ph].
17. Midrijanis, Gatis (2004), "Complejidad de consulta cuántica exacta para funciones booleanas totales", arXiv : quant-ph/0403168
18. Midrijanis, Gatis (2005), "Sobre las complejidades de las consultas cuánticas y aleatorias", arXiv : quant-ph/0501142
19. Huang, Hao (2019). "Subgrafos inducidos de hipercubos y una prueba de la conjetura de la sensibilidad". Anales de Matemáticas . 190 (3): 949–955. arXiv : 1907.00847 . doi : 10.4007/annals.2019.190.3.6. ISSN  0003-486X. JSTOR  10.4007/anales.2019.190.3.6. S2CID  195767594.
20. Klarreich, Erica. "Conjetura informática de décadas de antigüedad resuelta en dos páginas". Revista Quanta . Consultado el 26 de julio de 2019 .

Encuestas

• Buhrman, Harry; de Wolf, Ronald (2002), "Medidas de complejidad y complejidad del árbol de decisión: una encuesta" (PDF) , Ciencias de la Computación Teórica , 288 (1): 21–43, doi : 10.1016/S0304-3975(01)00144-X