En complejidad computacional el modelo de árbol de decisión es el modelo de cómputo 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 la prueba. realizado a continuación.
Por lo general, estas pruebas tienen una pequeña cantidad de resultados (como una pregunta de sí o no) y se pueden realizar rápidamente (por ejemplo, con un costo computacional unitario), por lo que la complejidad de tiempo en el 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 del á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 comparación los artículos deben llevar comparaciones. Para tipos de comparación, una consulta es una comparación de dos elementos, con dos resultados (asumiendo que ningún elemento es igual): o . Los tipos 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.
Árboles de comparación y límites inferiores para ordenar
Los árboles de decisión se emplean a menudo para comprender los algoritmos de clasificación y otros problemas similares; esto fue hecho por primera vez por Ford y Johnson. [1]
Por ejemplo, muchos algoritmos de clasificación son tipos de 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 ordenarán son todos distintos y comparables, esto se puede reformular como una pregunta de sí o no: es?
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 de la lista de elementos completamente ordenada. (La inversa de esta permutación,, reordena la secuencia de entrada.)
Se puede demostrar que los tipos de comparación deben utilizar comparaciones a través de un argumento simple: para que un algoritmo sea correcto, debe ser capaz de generar cada posible permutación 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:sale de. Cualquier árbol binario con al menos las hojas tienen profundidad al menos , por lo que este es un límite inferior en el tiempo de ejecución de un algoritmo de clasificación de comparación. En este caso, la existencia de numerosos algoritmos de clasificación por comparación que tienen esta complejidad de tiempo, como mergesort y heapsort , demuestra que el límite es estrecho. [2] : 91
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, esta es una reformulación del argumento de la teoría de la información de que un algoritmo de clasificación correcto debe aprender al menosbits de información sobre la secuencia de entrada. Como resultado, esto también funciona para árboles de decisión aleatorios.
Otros límites inferiores del árbol de decisión utilizan que la consulta es una comparación. Por ejemplo, considere la tarea de usar solo comparaciones para encontrar el número más pequeño entrenú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 más) en al menos una comparación. Entonces, se necesita al menoscomparaciones para encontrar el mínimo. (El argumento teórico de la información aquí solo da un límite inferior de.) Un argumento similar funciona para los límites inferiores generales para calcular estadísticas de orden . [2] : 214
Árboles de decisión lineales y algebraicos
Los árboles de decisión lineal generalizan los árboles de decisión de comparación anteriores para calcular funciones 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, muestra 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 . A partir de su definición, los árboles de decisión lineal solo pueden especificar funcionescuyas fibras se pueden construir tomando uniones e intersecciones de semiespacios.
Los árboles de decisión algebraicos son una generalización de árboles de decisión lineales que permiten que las funciones de prueba sean polinomios de grado. Geométricamente, el espacio se divide en conjuntos semi-algebraicos (una generalización del hiperplano).
Estos modelos de árboles de decisión, definidos por Rabin [3] y Reingold, [4] se utilizan a menudo para probar límites inferiores en geometría computacional . [5] Por ejemplo, Ben-Or mostró que la singularidad del elemento (la tarea de computar, dónde es 0 si y solo si existen coordenadas distintas tal que ) requiere un árbol de decisión algebraico de profundidad . [6] Esto fue mostrado por primera vez para modelos de decisión lineal por Dobkin y Lipton. [7] También muestran unlímite inferior para árboles de decisión lineal en el problema de la mochila, generalizado a árboles de decisión algebraicos por Steele y Yao. [8]
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 poco de la entrada,, y la salida es . Cada consulta puede depender de consultas anteriores. Existen 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 .
Árbol de decisión determinista
Si la salida de un árbol de decisiones es , para todos , se dice que el árbol de decisiones "calcula" . La profundidad de un árbol es el número máximo de consultas que pueden ocurrir antes de que se alcance una hoja y se obtenga un resultado., la complejidad determinista del árbol de decisiones de es la profundidad más pequeña entre todos los árboles de decisión deterministas que calculan .
Á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 definirlo 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 en el apoyo de la distribución subyacente. se define como la complejidad del árbol de decisión aleatorio de menor profundidad cuyo resultado es con probabilidad al menos para todos (es decir, con error de 2 caras acotado).
se conoce como la complejidad del árbol de decisión aleatorio de Monte Carlo , porque se permite que el resultado sea incorrecto con un error de dos caras acotado. La complejidad del árbol de decisiones de Las Vegasmide la profundidad esperada de un árbol de decisión que debe ser correcto (es decir, tiene cero error). También hay una versión de error acotado unilateral que se denota por.
Á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 la complejidad del certificado de esa función. Mide el número de bits de entrada que un algoritmo no determinista necesitaría mirar para evaluar la función con certeza.
Formalmente, la complejidad del certificado de a es el tamaño del subconjunto más pequeño de índices tal que, para todos , Si para todos , luego . La complejidad del certificado de es la máxima complejidad del certificado sobre todas . La noción análoga en la que solo se requiere que el verificador sea correcto con 2/3 de probabilidad se denota.
Árbol de decisión cuántica
La complejidad del árbol de decisiones cuánticas es la profundidad del árbol de decisión cuántica 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ántica 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 consulta cuántica , porque la definición directa de un árbol de decisión cuántica es más complicada que en el caso clásico. Similar al caso aleatorio, definimos y .
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 satisfactorio para todos . El grado aproximado de, denotado , es el grado más pequeño de cualquier polinomio satisfactorio cuando sea y cuando sea .
Beals y col. estableció que y . [9]
Relaciones entre medidas de complejidad de funciones booleanas
De las definiciones se desprende inmediatamente que para todos -bit funciones booleanas ,, 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.
Todos estos tipos de complejidad de consultas están relacionados polinomialmente. 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á relacionada polinomialmente con la complejidad del árbol de decisión determinista:. [13] (Nisan también mostró 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 decisiones cuánticas,, y este límite es estrecho. [16] [15] Los midrijanis demostraron que, [17] [18] mejorando una unión cuártica debido a Beals et al. [9]
Es importante notar que estas relaciones polinomiales son válidas solo para funciones booleanas totales . Para funciones booleanas parciales , que tienen un dominio un subconjunto de, una separación exponencial entre y es posible; Deutsch y Jozsa descubrieron el primer ejemplo de tal problema .
Conjetura de sensibilidad
Para una función booleana , la sensibilidad de se define como la máxima sensibilidad de general , donde la sensibilidad de a es el número de cambios de un solo bit en que cambian el valor de . La sensibilidad está relacionada con la noción de influencia total del análisis de funciones booleanas , que es igual a la sensibilidad promedio sobre todos.
La conjetura de sensibilidad es la conjetura de que la sensibilidad está relacionada polinomialmente con la complejidad de la consulta; es decir, existe exponente tal que, para todos , y . Uno puede demostrar a través de un simple argumento 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 discutidas anteriormente están relacionadas polinomialmente, el tipo preciso de medida de complejidad no es relevante. Sin embargo, esto se suele formular como la cuestión de relacionar la sensibilidad con la sensibilidad de bloqueo.
La sensibilidad de bloque de, denotado , se define como la máxima sensibilidad de bloque de general . La sensibilidad de bloque de a es el número máximo de subconjuntos disjuntos tal que, para cualquiera de los subconjuntos , volteando los trozos de correspondiente a cambia el valor de . [13]
Dado que la sensibilidad del bloque toma un máximo sobre más opciones de subconjuntos, . Además, la sensibilidad de bloque está relacionada polinomialmente con las medidas de complejidad discutidas anteriormente; Por ejemplo, el artículo de Nisan que presenta la sensibilidad al bloque mostró que. [13] Entonces, uno podría reformular la conjetura de sensibilidad para mostrar que, para algunos, . En 1992, Nisan y Szegedy conjeturaron quees suficiente. [19] Esto sería estricto, ya que Rubinstein en 1995 mostró una separación cuadrática entre sensibilidad y sensibilidad de bloque. [20]
En julio de 2019, 27 años después de que se planteó inicialmente la conjetura, Hao Huang de la Universidad de Emory demostró la conjetura de sensibilidad, mostrando que. [21] Esta prueba es notablemente sucinta, demostrando esta afirmación en dos páginas cuando el progreso previo hacia la conjetura de sensibilidad había sido limitado. [22] [23]
Resumen de resultados conocidos
2 | 2, 3 | 2 | 2, 3 | 2, 3 | 3, 6 | 2, 3 | 2, 3 | 4 | 4 | ||
1 | 2 | 2 | 2, 3 | 2, 3 | 3, 6 | 2, 3 | 2, 3 | 3, 4 | 4 | ||
1 | 1 | 2 | 2, 3 | 2, 3 | 3, 6 | 1,5, 3 | 2, 3 | 3, 4 | 4 | ||
1 | 1 | 1, 2 | 2 | 2 | 2,22, 5 | 1,15, 3 | 1,63, 3 | 2, 4 | 2, 4 | ||
1 | 1 | 1 | 1 | 1,5, 2 | 2, 4 | 1,15, 2 | 1,63, 2 | 2 | 2 | ||
1 | 1 | 1 | 1 | 1 | 2, 4 | 1,15, 2 | 1,63, 2 | 2 | 2 | ||
1 | 1 | 1 | 1 | 1 | 1 | 1,15, 2 | 1,63, 2 | 2 | 2 | ||
1 | 1,33, 2 | 1,33, 3 | 2 | 2, 3 | 2, 3 | 3, 6 | 2, 3 | 2, 4 | 4 | ||
1 | 1,33, 2 | 1,33, 2 | 2 | 2 | 2 | 2 | 1 | 2 | 2 | ||
1 | 1 | 1 | 2 | 2, 3 | 2, 3 | 3, 6 | 1 | 2, 3 | 4 | ||
1 | 1 | 1 | 2 | 2 | 2 | 2 | 1 | 1 | 1 |
Esta tabla resume los resultados de las separaciones entre las medidas de complejidad de la función booleana. Las medidas de complejidad son, en orden, complejidades deterministas, aleatorias con cero errores, aleatorias con errores de dos caras, certificado, certificado aleatorizado, sensibilidad de bloque, sensibilidad, cuántica exacta, grado, cuántico y grado aproximado.
El número en el -th fila y -th columna denota límites en el exponente , que es el mínimo de todos satisfactorio para todas las funciones booleanas . Por ejemplo, la entrada en la fila D-ésima y la columna s-ésima es "3, 6", por lo que para todos , y existe una función tal que .
Ver también
- Orden de comparación
- Árbol de decisión
- Conjetura de Aanderaa-Karp-Rosenberg
- Árbol de expansión mínimo # Árboles de decisión
Referencias
- ^ Jr, Lester R. Ford; Johnson, Selmer M. (1 de mayo de 1959). "Un problema de torneo" . The American Mathematical Monthly . 66 (5): 387–389. doi : 10.1080 / 00029890.1959.11989306 . ISSN 0002-9890 .
- ^ a b Introducción a los algoritmos . Cormen, Thomas H. (Tercera ed.). Cambridge, Mass .: MIT Press. 2009. ISBN 978-0-262-27083-0. OCLC 676697295 .CS1 maint: otros ( enlace )
- ^ Rabin, Michael O. (1 de diciembre de 1972). "Demostrando positividad simultánea de formas lineales" . Revista de Ciencias de la Computación y Sistemas . 6 (6): 639–650. doi : 10.1016 / S0022-0000 (72) 80034-5 . ISSN 0022-0000 .
- ^ 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 .
- ^ Preparata, Franco P. (1985). Geometría computacional: una introducción . Shamos, Michael Ian. Nueva York: Springer-Verlag. ISBN 0-387-96131-3. OCLC 11970840 .
- ^ Ben-Or, Michael (1 de diciembre de 1983). "Límites inferiores para árboles de cálculo algebraico" . Actas del Decimoquinto Simposio Anual ACM sobre Teoría de la Computación . STOC '83. Nueva York, NY, EE. UU.: Association for Computing Machinery: 80–86. doi : 10.1145 / 800061.808735 . ISBN 978-0-89791-099-6. S2CID 1499957 .
- ^ 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 .
- ^ Michael Steele, J; Yao, Andrew C (1 de marzo de 1982). "Límites inferiores para árboles de decisión algebraica" . Revista de algoritmos . 3 (1): 1–8. doi : 10.1016 / 0196-6774 (82) 90002-5 . ISSN 0196-6774 .
- ^ a b 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 .
- ^ Blum, M .; Impagliazzo, R. (1987). "Oráculos genéricos y clases de oráculo". Actas del 18º IEEE FOCS . págs. 118-126.
- ^ Hartmanis, J .; Hemachandra, L. (1987), "Funciones unidireccionales, robustez y no isomorfismo de conjuntos NP-completos", Informe técnico DCS TR86-796, Universidad de Cornell
- ^ Tardos, G. (1989). "Consulta la complejidad, o ¿por qué es difícil separar NP A ∩ coNP A de P A por oráculos aleatorios A ?". Combinatorica . 9 (4): 385–392. doi : 10.1007 / BF02125350 . S2CID 45372592 .
- ^ a b c Nisan, N. (1989). "CREW PRAMs y árboles de decisión". Actas de la 21ª ACM STOC . págs. 327–335.
- ^ Kulkarni, R. y Tal, A. Sobre la sensibilidad del bloque fraccional. Coloquio Electrónico sobre Complejidad Computacional (ECCC). Vol. 20. 2013.
- ^ a b Ambainis, Andris; Balodis, Kaspars; Belovs, Aleksandrs; Lee, Troy; Santha, Miklos; Smotrovs, Juris (4 de septiembre de 2017). "Separaciones en la complejidad de las 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 .
- ^ a b Aaronson, Scott; Ben-David, Shalev; Kothari, Robin; Rao, Shravas; Tal, Avishay (23 de octubre de 2020). "Grado frente a grado aproximado e implicaciones cuánticas del teorema de sensibilidad de Huang". arXiv : 2010.12629 [ quant-ph ].
- ^ Midrijanis, Gatis (2004), "Complejidad de consulta cuántica exacta para funciones booleanas totales", arXiv : quant-ph / 0403168
- ^ Midrijanis, Gatis (2005), "On Randomized and Quantum Query Complexities", arXiv : quant-ph / 0501142
- ^ Nisan, Noam; Szegedy, Mario (1 de julio de 1992). "Sobre el grado de funciones booleanas como polinomios reales" . Actas del Vigésimo Cuarto Simposio Anual de ACM sobre Teoría de la Computación . STOC '92. Victoria, Columbia Británica, Canadá: Asociación de Maquinaria de Computación: 462–467. doi : 10.1145 / 129712.129757 . ISBN 978-0-89791-511-3. S2CID 6919144 .
- ^ Rubinstein, David (1 de junio de 1995). "Sensibilidad vs sensibilidad de bloque de funciones booleanas" . Combinatorica . 15 (2): 297–299. doi : 10.1007 / BF01200762 . ISSN 1439-6912 . S2CID 41010711 .
- ^ Huang, Hao (2019). "Subgrafos inducidos de hipercubos y una prueba de la conjetura de sensibilidad". Annals of Mathematics . 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 .
- ^ Klarreich, Erica. "Conjetura de la informática de décadas de antigüedad resuelta en dos páginas" . Revista Quanta . Consultado el 26 de julio de 2019 .
- ^ Hatami, Pooya; Kulkarni, Raghav; Pankratov, Denis (22 de junio de 2011). "Variaciones sobre la conjetura de la sensibilidad" . Teoría de la Computación . 1 : 1–27. doi : 10.4086 / toc.gs.2011.004 . ISSN 1557-2862 . S2CID 6918061 .
Encuestas
- Buhrman, Harry; de Wolf, Ronald (2002), "Medidas de complejidad y complejidad del árbol de decisión: una encuesta" (PDF) , Informática teórica , 288 (1): 21–43, doi : 10.1016 / S0304-3975 (01) 00144-X