Modelo de árbol de decisión
En complejidad computacional el modelo de árbol de decisión es el modelo de computación en que un algoritmo es considerado básicamente como un árbol de decisión, i.e., una secuencia de consultas o pruebas que se realizan adaptativamente, así que el resultado de las pruebas anteriores puede influir la prueba que se realiza después.
Por lo general, estas pruebas tienen una pequeña cantidad de resultados (tales como preguntas de sí o no) y se pueden realizar rápidamente (por ejemplo, con un costo computacional unitario), por lo que la complejidad temporal de un algoritmo en el peor de los casos 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 consulta .
Los modelos de árboles de decisión son fundamentales para establecer cuotas inferiores para la teoría de la complejidad para ciertas clases de problemas y algoritmos computacionales. Se han introducido varias variantes de modelos de árboles de decisión, según el modelo computacional y el tipo de algoritmos de consulta que se les permite realizar.
Por ejemplo, un argumento de árbol de decisión se usa para mostrar que un ordenamiento por comparación de objetos debe tomar comparaciones. Para ordenamientos por comparación, una consulta es una comparación de dos elementos , con dos resultados (suponiendo que ningún par de elementos sean iguales): o . Los ordenamientos por comparación se pueden expresar como un árbol de decisión en este modelo, ya que dichos algoritmos de ordenamiento solo realizan este tipo de consultas.
Árboles de comparación y cuotas inferiores para ordenamientos
Los árboles de decisión a menudo se emplean para comprender los algoritmos de ordenamiento y otros problemas similares; esto fue hecho por primera vez por Ford y Johnson.[1]
Por ejemplo, muchos algoritmos de ordenamiento son ordenamientos 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 a clasificar 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, el resultado corresponde a una permutación que describe cómo se codificó la secuencia de entrada de la lista completa de elementos ordenados. (El inverso de esta permutación, , reordena la secuencia de entrada. )
Se puede mostrar que los ordenamientos de comparación deben usar comparaciones a través de 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, es decir, hojas. Cualquier árbol binario con al menos hojas tendrá una profundidad de al menos , por lo que este es un límite inferior en el tiempo de ejecución de un algoritmo de ordenamiento por comparación. En este caso, la existencia de numerosos algoritmos de ordenamiento por comparación que tienen esta complejidad de tiempo, como ordenamiento por mezcla (mergesort) y heapsort, demuestra que la cuota es rígida.[2] : 91
Este argumento no utiliza nada acerca del tipo de consulta, por lo que, de hecho, demuestra una cuota inferior para cualquier algoritmo de ordenamiento que pueda modelarse como un árbol de decisión binario. En esencia, esta es una reformulación del argumento en 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.
Otras cuotas inferiores para el modelo de árbol de decisión utilizan que la consulta es una comparación. Por ejemplo, considera la tarea de usar solo comparaciones para encontrar el número más pequeño entre 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 mayor) en al menos una comparación. Entonces, se necesita al menos comparaciones para encontrar el mínimo. (El argumento teórico de la información aquí solo da una cuota inferior de . ) Un argumento similar funciona para las cuotas inferiores generales para calcular estadísticos de orden .[2] : 214
Árboles de decisión lineales y algebraicos
Los árboles de decisión lineales generalizan los árboles de decisión de comparación anteriores para computar funciones que toman vectores reales como entradas. Las pruebas en árboles de decisión lineales son funciones lineales: para una elección particular de números reales , emite 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 . Por su definición, los árboles de decisión lineales solo pueden especificar funciones cuyas fibras se pueden construir tomando uniones e intersecciones de semiespacios.
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 semialgebráicos (una generalización del hiperplano).
Estos modelos de árboles de decisión, definidos por Rabin[3] y Reingold,[4] se utilizan a menudo para demostrar cuotas inferiores en geometría computacional .[5] Por ejemplo, Ben-Or demostró que la unicidad de los elementos (la tarea de calcular , 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 los modelos de decisión lineal por Dobkin y Lipton.[7] También muestran una cuota inferior de para árboles de decisión lineales en el problema de la mochila, generalizado a árboles de decisión algebraicos por Steele y Yao.[8]
Complejidades del árboles de decisión booleanos
Para árboles de decisión Booleana, la tarea es calcular el valor de una función booleana de bits para una entrada . Las consultas corresponden a leer un bit de la entrada, , y la salida es . Cada consulta puede depender de las consultas anteriores. Son muchos los tipos de modelos computacionales que utilizan árboles de decisión que se podrían considerar, admitiendo múltiples nociones de complejidad, denominadas medidas de complejidad .
Á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 que se alcance una hoja y se obtenga un resultado. , la complejidad del árbol de decisión determinista de es la profundidad más pequeña entre todos los árboles de decisión deterministas que calculan .
Árbol de decisión aleatorizada
Una forma de definir un árbol de decisión aleatorio es agregando nodos adicionales al árbol, cada uno controlado por una probabilidad . Otra definición equivalente lo construye 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 soporte 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 dos colas 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 colas acotado. La complejidad del árbol de decisión de Las Vegas mide la profundidad esperada de un árbol de decisión que debe ser correcto (es decir, tiene cero errores). 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 la cantidad de bits de entrada que un algoritmo no determinista necesitaría consultar 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, por todo , si para todos , después . La complejidad del certificado de es la complejidad máxima del certificado sobre todos . 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 decisión cuántico es la profundidad del árbol de decisión cuántico de menor profundidad que da el resultado con probabilidad al menos para todo . Otra cantidad, denominada , está definida 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 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 acotadas por las nociones de grado y grado aproximado. El grado de , denotado , es el grado más pequeño de cualquier polinomio que satisface para toda . El grado aproximado de , denotado , es el grado más pequeño de cualquier polinomio que satisface cuando y cuando .
Beals et al. estableció que y .[9]
Relaciones entre medidas de complejidad de funciones booleanas
Se sigue inmediatamente de las definiciones que para toda funcn Booleana de ,
,
y
.
Encontrar las mejores posibles cuotas superiores en la dirección inversa es un objetivo importante en el campo de complejidad de consultas.
Todos estos tipos de complejidad de consulta 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á relacionada polinómicamente con la complejidad del árbol de decisión determinista de la siguiente manera: .[13] (Nisan también mostró que ). Se conoce una desigualdad más estrecha entre los modelos Monte Carlo y Las Vegas: .[14] Esta relación es óptima módulo factores polilogarítmicos.[15] En cuanto a las complejidades del árbol de decisión cuántica, , y esta cuota es estrecha.[15] Midrijanis demostró que , mejorando una cuota cuártica debida a Beals et al.[9]
Es importante señalar que estas relaciones polinómicas son válidas solo para funciones booleanas totales . Para funciones Booleanas parciales, que tienen como dominio un subconjunto de , una separación exponencial entre y es posible; el primer ejemplo de tal problema fue descubierto por Deutsch y Jozsa .
Conjetura de sensibilidad
Para una función booleana , la sensibilidad de se define como la máxima sensibilidad de en cualquier , donde la sensibilidad de en es el número de cambios de un solo bit en que cambia 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 los valores .
La conjetura de sensibilidad dice que la sensibilidad está polinomialmente relacionada con la complejidad de consulta; es decir, existen exponentes tales que, para toda , y . Uno puede mostrar a través de un argumento simple que , por lo que la conjetura se ocupa específicamente de encontrar una cuota inferior para la sensibilidad. Dado que todas las medidas de complejidad discutidas anteriormente están relacionadas polinómicamente, el tipo preciso de medida de complejidad no es relevante. Sin embargo, esto normalmente se expresa como la cuestión de relacionar la sensibilidad con la sensibilidad de bloque.
La sensibilidad de bloque de , denotado , se define como la máxima sensibilidad de bloque de en cualquiera . La sensibilidad de bloque de en es el número máximo de subconjuntos disjuntos tal que, para cualquiera de los subconjuntos , volteando los pedacitos de correspondiente a cambia el valor de .[13]
Dado que la sensibilidad de bloque toma su máximo valor en más opciones de subconjuntos, . Además, la sensibilidad de bloque está relacionada polinómicamente con las medidas de complejidad discutidas previamente; por ejemplo, el artículo de Nisan que introdujo la sensibilidad a los bloques mostró que .[13] Por lo tanto, uno podría reformular la conjetura de la sensibilidad mostrando que, para algunos , . En 1992, Nisan y Szegedy conjeturaron que es suficiente[16] Esto sería un valor escrio, ya que Rubinstein en 1995 mostró una separación cuadrática entre la sensibilidad y la sensibilidad de bloque.[17]
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 la sensibilidad, mostrando que .[18] Esta prueba es notablemente sucinta. Huang prueba esto en dos páginas, mientras que el progreso previo hacia la conjetura de sensibilidad había sido limitado.[19][20]
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 funciones booleanas. Las medidas de complejidad son, en orden, complejidades deterministas, aleatorias con cero errores, aleatorias con errores bilaterales, certificado, certificado aleatorio, sensibilidad de bloque, sensibilidad, cuántico exacto, grado, cuántica, y grado aproximado.
El número en la -ésima fila y -ésima columna denota las cuotas en el exponente , que es el ínfimo de toda que satisface para todas las funciones booleanas . Por ejemplo, la entrada en la D-ésima fila y la s-ésima columna es "3, 6", por lo que para toda , y existe una función tal que .
Véase también
- Sorteo por comparación
- Árbol de decisión
- Conjetura de Aanderaa-Karp-Rosenberg
- Árbol de expansión mínima#Árboles de decisión
Referencias
- ↑ Jr, Lester R. Ford; Johnson, Selmer M. (1 de mayo de 1959). «A Tournament Problem». The American Mathematical Monthly 66 (5): 387-389. ISSN 0002-9890. doi:10.1080/00029890.1959.11989306.
- ↑ a b Introduction to algorithms. Cormen, Thomas H. (Third edición). Cambridge, Mass.: MIT Press. 2009. ISBN 978-0-262-27083-0. OCLC 676697295.
- ↑ Rabin, Michael O. (1 de diciembre de 1972). «Proving simultaneous positivity of linear forms». Journal of Computer and System Sciences (en inglés) 6 (6): 639-650. ISSN 0022-0000. doi:10.1016/S0022-0000(72)80034-5.
- ↑ Reingold, Edward M. (1 de octubre de 1972). «On the Optimality of Some Set Algorithms». Journal of the ACM 19 (4): 649-659. ISSN 0004-5411. doi:10.1145/321724.321730.
- ↑ Preparata, Franco P. (1985). Computational geometry : an introduction. Shamos, Michael Ian. New York: Springer-Verlag. ISBN 0-387-96131-3. OCLC 11970840.
- ↑ Ben-Or, Michael (1 de diciembre de 1983). «Lower bounds for algebraic computation trees». Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing. STOC '83 (New York, NY, USA: Association for Computing Machinery): 80-86. ISBN 978-0-89791-099-6. doi:10.1145/800061.808735.
- ↑ Dobkin, David; Lipton, Richard J. (1 de junio de 1976). «Multidimensional Searching Problems». SIAM Journal on Computing 5 (2): 181-186. ISSN 0097-5397. doi:10.1137/0205015.
- ↑ Michael Steele, J; Yao, Andrew C (1 de marzo de 1982). «Lower bounds for algebraic decision trees». Journal of Algorithms (en inglés) 3 (1): 1-8. ISSN 0196-6774. doi:10.1016/0196-6774(82)90002-5.
- ↑ a b Beals, R.; Buhrman, H.; Cleve, R.; Mosca, M.; de Wolf, R. (2001). «Quantum lower bounds by polynomials». Journal of the ACM 48 (4): 778-797. arXiv:quant-ph/9802049. doi:10.1145/502090.502097.
- ↑ . 1987. pp. 118-126. Falta el
|título=
(ayuda) - ↑ Hartmanis, J.; Hemachandra, L. (1987), «One-way functions, robustness, and non-isomorphism of NP-complete sets», Technical Report DCS TR86-796, Cornell University .
- ↑ Tardos, G. (1989). «Query complexity, or why is it difficult to separate NPA ∩ coNPA from PA by random oracles A?». Combinatorica 9 (4): 385-392. doi:10.1007/BF02125350.
- ↑ a b c . 1989. pp. 327-335. Falta el
|título=
(ayuda) - ↑ Kulkarni, R. and Tal, A. On Fractional Block Sensitivity. Electronic Colloquium on Computational Complexity (ECCC). Vol. 20. 2013.
- ↑ a b Ambainis, Andris; Balodis, Kaspars; Belovs, Aleksandrs; Lee, Troy; Santha, Miklos; Smotrovs, Juris (4 de septiembre de 2017). «Separations in Query Complexity Based on Pointer Functions». Journal of the ACM 64 (5): 32:1-32:24. ISSN 0004-5411. arXiv:1506.04719. doi:10.1145/3106234.
- ↑ Nisan, Noam; Szegedy, Mario (1 de julio de 1992). «On the degree of Boolean functions as real polynomials». Proceedings of the Twenty-fourth Annual ACM Symposium on Theory of Computing. STOC '92 (Victoria, British Columbia, Canada: Association for Computing Machinery): 462-467. ISBN 978-0-89791-511-3. doi:10.1145/129712.129757.
- ↑ Rubinstein, David (1 de junio de 1995). «Sensitivity vs. block sensitivity of Boolean functions». Combinatorica (en inglés) 15 (2): 297-299. ISSN 1439-6912. doi:10.1007/BF01200762.
- ↑ Huang, Hao (2019). «Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture». Annals of Mathematics 190 (3): 949-955. ISSN 0003-486X. arXiv:1907.00847. doi:10.4007/annals.2019.190.3.6.
- ↑ Klarreich, Erica. «Decades-Old Computer Science Conjecture Solved in Two Pages». Quanta Magazine. Consultado el 26 de julio de 2019.
- ↑ Hatami, Pooya; Kulkarni, Raghav; Pankratov, Denis (22 de junio de 2011). «Variations on the Sensitivity Conjecture». Theory of Computing (en inglés) 1: 1-27. ISSN 1557-2862. doi:10.4086/toc.gs.2011.004.
Encuestas
- Buhrman, Harry; de Wolf, Ronald (2002), «Complexity Measures and Decision Tree Complexity: A Survey», Theoretical Computer Science 288 (1): 21-43, doi:10.1016/S0304-3975(01)00144-X .
Datos: Q5249246