Conjetura de Aanderaa-Karp-Rosenberg

Problema no resuelto sobre la complejidad de las consultas gráficas

Problema sin resolver en informática :

Pruebe o refute la conjetura de Aanderaa–Karp–Rosenberg.

(más problemas sin resolver en informática)

En informática teórica , la conjetura de Aanderaa–Karp–Rosenberg (también conocida como conjetura de Aanderaa–Rosenberg o conjetura de evasividad ) es un grupo de conjeturas relacionadas sobre el número de preguntas de la forma "¿Hay una arista entre vértice y vértice ?" que deben responderse para determinar si un grafo no dirigido tiene o no una propiedad particular como planaridad o bipartidismo . Reciben su nombre en honor a Stål Aanderaa , Richard M. Karp y Arnold L. Rosenberg . Según la conjetura, para una amplia clase de propiedades, ningún algoritmo puede garantizar que podrá omitir alguna pregunta: cualquier algoritmo para determinar si el grafo tiene la propiedad, sin importar lo inteligente que sea, podría necesitar examinar cada par de vértices antes de poder dar su respuesta. Una propiedad que satisface esta conjetura se llama evasiva . ${\displaystyle u}$ ${\displaystyle v}$

Más precisamente, la conjetura de Aanderaa–Rosenberg establece que cualquier algoritmo determinista debe probar al menos una fracción constante de todos los pares de vértices posibles, en el peor de los casos , para determinar cualquier propiedad de grafo monótona no trivial. En este contexto, una propiedad es monótona si sigue siendo verdadera cuando se añaden aristas; por ejemplo, la planaridad no es monótona, pero la no planaridad sí lo es. Una versión más fuerte de esta conjetura, llamada conjetura de evasividad o conjetura de Aanderaa–Karp–Rosenberg, establece que se necesitan pruebas exactas para un grafo con vértices. También se han formulado y estudiado versiones del problema para algoritmos aleatorios y algoritmos cuánticos . ${\displaystyle {\tbinom {n}{2}}=n(n-1)/2}$ ${\displaystyle n}$

La conjetura determinista de Aanderaa-Rosenberg fue demostrada por Rivest y Vuillemin (1975), pero la conjetura más fuerte de Aanderaa-Karp-Rosenberg sigue sin demostrarse. Además, existe una gran brecha entre el límite inferior conjeturado y el mejor límite inferior demostrado para la complejidad de consultas aleatorias y cuánticas.

Ejemplo

La propiedad de no ser vacío (es decir, tener al menos una arista) es monótona, porque agregar otra arista a un grafo no vacío produce otro grafo no vacío. Hay un algoritmo simple para probar si un grafo no está vacío: recorrer todos los pares de vértices, probando si cada par está conectado por una arista. Si alguna vez se encuentra una arista de esta manera, salir del bucle e informar que el grafo no está vacío, y si el bucle se completa sin encontrar ninguna arista, entonces informar que el grafo está vacío. En algunos grafos (por ejemplo, los grafos completos ) este algoritmo terminará rápidamente, sin probar cada par de vértices, pero en el grafo vacío prueba todos los pares posibles antes de terminar. Por lo tanto, la complejidad de consulta de este algoritmo es : en el peor de los casos, el algoritmo realiza pruebas. ${\displaystyle {\tbinom {n}{2}}=n(n-1)/2}$ ${\displaystyle n(n-1)/2}$

El algoritmo descrito anteriormente no es el único método posible para probar la no vacuidad, pero la conjetura de Aanderaa–Karp–Rosenberg implica que cada algoritmo determinista para probar la no vacuidad tiene la misma complejidad de consulta en el peor de los casos, . Es decir, la propiedad de no ser vacío es evasiva . Para esta propiedad, el resultado es fácil de probar directamente: si un algoritmo no realiza pruebas, no puede distinguir el grafo vacío de un grafo que tiene una arista que conecta uno de los pares de vértices no probados, y debe dar una respuesta incorrecta en uno de estos dos grafos. ${\displaystyle n(n-1)/2}$ ${\displaystyle n(n-1)/2}$

Definiciones

En el contexto de este artículo, todos los grafos serán simples y no dirigidos , a menos que se indique lo contrario. Esto significa que las aristas del grafo forman un conjunto (y no un multiconjunto ) y cada arista es un par de vértices distintos. Se supone que los grafos tienen una representación implícita en la que cada vértice tiene un identificador o etiqueta único y en la que es posible probar la adyacencia de dos vértices cualesquiera, pero para los cuales la prueba de adyacencia es la única operación primitiva permitida.

De manera informal, una propiedad de grafo es una propiedad de un grafo que es independiente del etiquetado. De manera más formal, una propiedad de grafo es una asignación de la clase de todos los grafos a tal que los grafos isomorfos se asignan al mismo valor. Por ejemplo, la propiedad de contener al menos un vértice de grado dos es una propiedad de grafo, pero la propiedad de que el primer vértice tenga grado dos no lo es, porque depende del etiquetado del grafo (en particular, depende de qué vértice es el "primer" vértice). Una propiedad de grafo se llama no trivial si no asigna el mismo valor a todos los grafos. Por ejemplo, la propiedad de ser un grafo es una propiedad trivial, ya que todos los grafos poseen esta propiedad. Por otro lado, la propiedad de estar vacío no es trivial, porque el grafo vacío posee esta propiedad, pero los grafos no vacíos no. Se dice que una propiedad de grafo es monótona si la adición de aristas no destruye la propiedad. Alternativamente, si un grafo posee una propiedad monótona, entonces cada supergrafo de este grafo en el mismo conjunto de vértices también la posee. Por ejemplo, la propiedad de no ser plano es monótona: un supergrafo de un grafo no plano es en sí mismo no plano. Sin embargo, la propiedad de ser regular no es monótona. ${\displaystyle \{0,1\}}$

La notación O mayúscula se utiliza a menudo para la complejidad de las consultas. En resumen, es (que se lee como "del orden de ") si existen constantes positivas y tales que, para todos , . De manera similar, es si existen constantes positivas y tales que, para todos , . Finalmente, es si es tanto y . ${\displaystyle f(n)}$ ${\displaystyle O(g(n))}$ ${\displaystyle g(n)}$ ${\displaystyle c}$ ${\displaystyle N}$ ${\displaystyle n\geq N}$ ${\displaystyle f(n)\leq c\cdot g(n)}$ ${\displaystyle f(n)}$ ${\displaystyle \Omega (g(n))}$ ${\displaystyle c}$ ${\displaystyle N}$ ${\displaystyle n\geq N}$ ${\displaystyle f(n)\geq c\cdot g(n)}$ ${\displaystyle f(n)}$ ${\displaystyle \Theta (g(n))}$ ${\displaystyle O(g(n))}$ ${\displaystyle \Omega (g(n))}$

Complejidad de la consulta

La complejidad de consulta determinista de evaluar una función en bits (donde los bits pueden etiquetarse como ) es la cantidad de bits que deben leerse en el peor de los casos mediante un algoritmo determinista que calcula la función. Por ejemplo, si la función toma el valor 0 cuando todos los bits son 0 y toma el valor 1 en caso contrario (esta es la función OR ), entonces su complejidad de consulta determinista es exactamente . En el peor de los casos, independientemente del orden que elija para examinar su entrada, los primeros bits leídos podrían ser todos 0, y el valor de la función ahora depende del último bit. Si un algoritmo no lee este bit, podría generar una respuesta incorrecta. (Estos argumentos se conocen como argumentos adversarios). La cantidad de bits leídos también se denomina cantidad de consultas realizadas a la entrada. Uno puede imaginar que el algoritmo pregunta (o consulta) a la entrada por un bit en particular y la entrada responde a esta consulta. ${\displaystyle n}$ ${\displaystyle x_{1},x_{2},\dots x_{n}}$ ${\displaystyle x_{i}}$ ${\displaystyle n}$ ${\displaystyle n-1}$

La complejidad de consulta aleatoria para evaluar una función se define de manera similar, excepto que se permite que el algoritmo sea aleatorio. En otras palabras, puede lanzar monedas y usar el resultado de estos lanzamientos de moneda para decidir qué bits consultar en qué orden. Sin embargo, el algoritmo aleatorio debe generar la respuesta correcta para todas las entradas: no se le permite cometer errores. Dichos algoritmos se denominan algoritmos de Las Vegas . (Una clase diferente de algoritmos, los algoritmos de Monte Carlo , pueden cometer algunos errores). La complejidad de consulta aleatoria se puede definir para los algoritmos de Las Vegas y de Monte Carlo, pero la versión aleatoria de la conjetura de Aanderaa–Karp–Rosenberg se refiere a la complejidad de consulta de Las Vegas de las propiedades de los grafos.

La complejidad de consulta cuántica es la generalización natural de la complejidad de consulta aleatoria, lo que permite, por supuesto, consultas y respuestas cuánticas. La complejidad de consulta cuántica también se puede definir con respecto a los algoritmos de Monte Carlo o de Las Vegas, pero normalmente se entiende que se refiere a los algoritmos cuánticos de Monte Carlo.

En el contexto de esta conjetura, la función a evaluar es la propiedad del grafo, y la entrada puede considerarse como una cadena de tamaño , que describe para cada par de vértices si existe una arista con ese par como sus puntos finales. La complejidad de la consulta de cualquier función en esta entrada es como máximo , porque un algoritmo que realiza consultas puede leer toda la entrada y determinar el grafo de entrada por completo. ${\displaystyle n(n-1)/2}$ ${\displaystyle n(n-1)/2}$ ${\displaystyle n(n-1)/2}$

Complejidad de consulta determinista

Para los algoritmos deterministas, Rosenberg (1973) originalmente conjeturó que para todas las propiedades de grafos no triviales en los vértices, decidir si un grafo posee esta propiedad requiere La condición de no trivialidad es claramente requerida porque hay propiedades triviales como "¿es esto un grafo?" que pueden responderse sin ninguna consulta. ${\displaystyle n}$ ${\displaystyle \Omega (n^{2})}$

Un gráfico de escorpión. Uno de los tres vértices de la ruta roja es adyacente a todos los demás vértices y los otros dos vértices rojos no tienen otras adyacencias.

La conjetura fue refutada por Aanderaa, quien exhibió una propiedad de grafo dirigido (la propiedad de contener un "sumidero") que solo requería consultas para probar. Un sumidero , en un grafo dirigido, es un vértice de grado de entrada y grado de salida cero. La existencia de un sumidero se puede probar con menos de consultas (Best, van Emde Boas y Lenstra 1974). Una propiedad de grafo no dirigido que también se puede probar con consultas es la propiedad de ser un grafo de escorpión, descrito por primera vez en Best, van Emde Boas y Lenstra (1974). Un grafo de escorpión es un grafo que contiene un camino de tres vértices, de modo que un punto final del camino está conectado a todos los vértices restantes, mientras que los otros dos vértices del camino no tienen aristas incidentes distintas a las del camino. ${\displaystyle O(n)}$ ${\displaystyle n-1}$ ${\displaystyle 3n}$ ${\displaystyle O(n)}$

Luego, Aanderaa y Rosenberg formularon una nueva conjetura (la conjetura de Aanderaa-Rosenberg ) que dice que decidir si un grafo posee una propiedad de grafo monótono no trivial requiere consultas. ^[1] Esta conjetura fue resuelta por Rivest y Vuillemin (1975) al mostrar que al menos se necesitan consultas para probar cualquier propiedad de grafo monótono no trivial. El límite fue mejorado aún más a por Kleitman y Kwiatkowski (1980), a (para cualquier ) por Kahn, Saks y Sturtevant (1984), a por Korneffel y Triesch (2010), y a por Scheidweiler y Triesch (2013). ${\displaystyle \Omega (n^{2})}$ ${\displaystyle {\tfrac {1}{16}}n^{2}}$ ${\displaystyle {\tfrac {1}{9}}n^{2}}$ ${\displaystyle {\bigl (}{\tfrac {1}{4}}-\varepsilon {\bigr )}n^{2}}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle {\bigl (}{\tfrac {8}{25}}-\varepsilon {\bigr )}n^{2}}$ ${\displaystyle {\bigl (}{\tfrac {1}{3}}-\varepsilon {\bigr )}n^{2}}$

Richard Karp conjeturó la afirmación más fuerte (que ahora se llama conjetura de evasividad o conjetura de Aanderaa–Karp–Rosenberg ) de que "toda propiedad de grafo monótona no trivial para grafos en vértices es evasiva". ^[2] Una propiedad se llama evasiva si determinar si un grafo dado tiene esta propiedad a veces requiere todas las consultas posibles. ^[3] Esta conjetura dice que el mejor algoritmo para probar cualquier propiedad monótona no trivial debe (en el peor de los casos) consultar todas las aristas posibles. Esta conjetura aún está abierta, aunque varias propiedades de grafos especiales han demostrado ser evasivas para todos . La conjetura ha sido resuelta para el caso donde es una potencia prima por Kahn, Saks y Sturtevant (1984) utilizando un enfoque topológico . La conjetura también ha sido resuelta para todas las propiedades monótonas no triviales en grafos bipartitos por Yao (1988). También se ha demostrado que las propiedades menores cerradas son evasivas para las grandes (Chakrabarti, Khot y Shi 2001). ${\displaystyle n}$ ${\displaystyle n(n-1)/2}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$

En Kahn, Saks y Sturtevant (1984) la conjetura se generalizó también a propiedades de otras funciones (no gráficas), conjeturando que cualquier función monótona no trivial que sea débilmente simétrica es evasiva. Este caso también se resuelve cuando es una potencia prima Lovász y Young (2002). ${\displaystyle n}$

Complejidad de consulta aleatoria

Richard Karp también conjeturó que se requieren consultas para probar propiedades monótonas no triviales incluso si se permiten algoritmos aleatorios. No se conoce ninguna propiedad monótona no trivial que requiera menos de consultas para probarse. Un límite inferior lineal (es decir, ) en todas las propiedades monótonas se desprende de una relación muy general entre las complejidades de consulta aleatorias y deterministas . El primer límite inferior superlineal para todas las propiedades monótonas fue dado por Yao (1991) quien demostró que se requieren consultas. Esto fue mejorado aún más por King (1991) a , y luego por Hajnal (1991) a . Esto fue mejorado posteriormente al límite inferior actual mejor conocido (entre los límites que se cumplen para todas las propiedades monótonas) de por Chakrabarti y Khot (2007). ${\displaystyle \Omega (n^{2})}$ ${\displaystyle {\tfrac {1}{4}}n^{2}}$ ${\displaystyle \Omega (n)}$ ${\displaystyle \Omega {\bigl (}n(\log n)^{1/12}{\bigr )}}$ ${\displaystyle \Omega (n^{5/4})}$ ${\displaystyle \Omega (n^{4/3})}$ ${\displaystyle \Omega {\bigl (}n^{4/3}(\log n)^{1/3}{\bigr )}}$

Algunos resultados recientes dan límites inferiores que están determinados por la probabilidad crítica de la propiedad del grafo monótono en consideración. La probabilidad crítica se define como el número único en el rango tal que un grafo aleatorio (obtenido al elegir aleatoriamente si cada arista existe, independientemente de las otras aristas, con probabilidad por arista) posee esta propiedad con probabilidad igual a . Friedgut, Kahn y Wigderson (2002) demostraron que cualquier propiedad monótona con probabilidad crítica requiere consultas. Para el mismo problema, O'Donnell et al. (2005) mostraron un límite inferior de . ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle [0,1]}$ ${\displaystyle G(n,p)}$ ${\displaystyle p}$ ${\displaystyle {\tfrac {1}{2}}}$ ${\displaystyle p}$ $${\displaystyle \Omega \left(\min \left\{{\frac {n}{\min(p,1-p)}},{\frac {n^{2}}{\log n}}\right\}\right)}$$ ${\displaystyle \Omega (n^{4/3}/p^{1/3})}$

Al igual que en el caso determinista, existen muchas propiedades especiales para las que se conoce un límite inferior. Además, se conocen límites inferiores mejores para varias clases de propiedades de grafos. Por ejemplo, para comprobar si el grafo tiene un subgrafo isomorfo a cualquier grafo dado (el llamado problema de isomorfismo de subgrafos ), el límite inferior mejor conocido se debe a Gröger (1992). ${\displaystyle \Omega (n^{2})}$ ${\displaystyle \Omega (n^{3/2})}$

Complejidad de consulta cuántica

Para la complejidad de consulta cuántica de error acotado , el límite inferior más conocido es el observado por Andrew Yao. ^[4] Se obtiene combinando el límite inferior aleatorio con el método del adversario cuántico. El mejor límite inferior posible que se podría esperar lograr es , a diferencia del caso clásico, debido al algoritmo de Grover que proporciona un algoritmo de consulta para probar la propiedad monótona de no vacío. De manera similar al caso determinista y aleatorio, hay algunas propiedades que se sabe que tienen un límite inferior, por ejemplo, el no vacío (que se desprende de la optimalidad del algoritmo de Grover) y la propiedad de contener un triángulo . Hay algunas propiedades de grafos que se sabe que tienen un límite inferior, e incluso algunas propiedades con un límite inferior. Por ejemplo, la propiedad monótona de no planaridad requiere consultas (Ambainis et al. 2008) y la propiedad monótona de contener más de la mitad del número posible de aristas (también llamada función mayoritaria) requiere consultas (Beals et al. 2001). ${\displaystyle \Omega {\bigl (}n^{2/3}(\log n)^{1/6}{\bigr )}}$ ${\displaystyle \Omega (n)}$ ${\displaystyle O(n)}$ ${\displaystyle \Omega (n)}$ ${\displaystyle \Omega (n^{3/2})}$ ${\displaystyle \Omega (n^{2})}$ ${\displaystyle \Theta (n^{3/2})}$ ${\displaystyle \Theta (n^{2})}$

Notas

1. Triesch (1996)
2. Lutz (2001)
3. Kozlov (2008, págs. 226-228)
4. El resultado no está publicado, pero se menciona en Magniez, Santha y Szegedy (2005).

Referencias

• Ambainis, Andris ; Iwama, Kazuo ; Nakanishi, Masaki; Nishimura, Harumichi; Raymond, Rudy; Tani, Seiichiro; Yamashita, Shigeru (2008), "Complejidad de consultas cuánticas de funciones booleanas con conjuntos pequeños", en Hong, Seok-Hee ; Nagamochi, Hiroshi; Fukunaga, Takuro (eds.), Actas del XIX Simposio Internacional sobre Algoritmos y Computación (ISAAC 2008) , Lecture Notes in Computer Science , vol. 5369, Springer-Verlag , págs. 907–918, doi :10.1007/978-3-540-92182-0_79, ISBN 978-3-540-92181-3, Sr.  2539981
• Beals, Robert; Buhrman, Harry; Cleve, Richard ; Mosca, Michele ; de ​​Wolf, Ronald (2001), "Límites inferiores cuánticos mediante polinomios", Journal of the ACM , 48 (4): 778–797, arXiv : quant-ph/9802049 , doi :10.1145/502090.502097, MR  2144930
• Mejor, señor; van Emde Boas, P .; Lenstra, HW (1974), Una versión mejorada de la conjetura de Aanderaa-Rosenberg , Informe ZW 30/74, Mathematisch Centrum Amsterdam , hdl :1887/3792
• Chakrabarti, Amit; Khot, Subhash (2007), "Límites inferiores mejorados en la complejidad aleatoria de las propiedades de gráficos", Random Structures & Algorithms , 30 (3): 427–440, doi :10.1002/rsa.20164, MR  2309625, S2CID  8384071
• Chakrabarti, Amit; Khot, Subhash ; Shi, Yaoyun (2001), "Evasión de la contención del subgrafo y propiedades relacionadas", SIAM Journal on Computing , 31 (3): 866–875, CiteSeerX  10.1.1.29.3131 , doi :10.1137/S0097539700382005, MR  1896462
• Friedgut, Ehud; Kahn, Jeff; Wigderson, Avi (2002), "Computing graph properties by randomized subcube particions", en Rolim, José DP; Vadhan, Salil (eds.), Actas del 6º Taller internacional sobre técnicas de aleatorización y aproximación en ciencias de la computación (RANDOM 2002) , Lecture Notes in Computer Science , vol. 2483, Springer-Verlag , págs. 105–113, doi :10.1007/3-540-45726-7_9, ISBN 978-3-540-44147-2
• Gröger, Hans Dietmar (1992), "Sobre la complejidad aleatoria de las propiedades de los gráficos monótonos" (PDF) , Acta Cybernetica , 10 (3): 119–127, MR  1206981
• Hajnal, Péter (1991), "Un límite inferior en la complejidad aleatoria de las propiedades de los gráficos", Combinatorica , 11 (2): 131–143, doi :10.1007/BF01206357, MR  1136162, S2CID  28514616 ${\displaystyle \Omega (n^{4/3})}$
• Kahn, Jeff; Saks, Michael ; Sturtevant, Dean (1984), "Un enfoque topológico de la evasión", Combinatorica , 4 (4): 297–306, doi :10.1007/BF02579140, MR  0779890, S2CID  5215059
• King, Valerie (1991), "Un límite inferior en la complejidad aleatoria de las propiedades de los gráficos", Combinatorica , 11 (1): 23–32, doi :10.1007/BF01375470, MR  1112271, S2CID  34416460 ${\displaystyle \Omega (n^{5/4})}$
• Kleitman, DJ ; Kwiatkowski, DJ (1980), "Resultados adicionales sobre la conjetura de Aanderaa-Rosenberg", Journal of Combinatorial Theory, Serie B , 28 : 85–95, doi : 10.1016/0095-8956(80)90057-X
• Kozlov, Dmitry (2008), Topología algebraica combinatoria , Springer-Verlag, ISBN 978-3-540-73051-4
• Lutz, Frank H. (2001), "Algunos resultados relacionados con la conjetura de evasión", Journal of Combinatorial Theory, Serie B , 81 (1): 110–124, doi : 10.1006/jctb.2000.2000
• Korneffel, Torsten; Triesch, Eberhard (2010), "Un límite asintótico para la complejidad de las propiedades de los gráficos monótonos", Combinatorica , 30 (6), Springer-Verlag: 735–743, doi :10.1007/s00493-010-2485-3, S2CID  27956060
• Magniez, Frédéric; Santha, Miklos; Szegedy, Mario (2005), "Algoritmos cuánticos para el problema del triángulo", Actas del decimosexto simposio anual ACM-SIAM sobre algoritmos discretos (SODA 2005), Vancouver, Columbia Británica: Society for Industrial and Applied Mathematics , pp. 1109–1117, arXiv : quant-ph/0310134 , Bibcode :2003quant.ph.10134M, ISBN 978-0-89871-585-9
• O'Donnell, Ryan ; Saks, Michael ; Schramm, Oded ; Servedio, Rocco A. (2005), "Cada árbol de decisión tiene una variable influyente", Actas del 46.º Simposio IEEE sobre Fundamentos de la informática (FOCS 2005) , págs. 31–39, arXiv : cs/0508071 , doi :10.1109/SFCS.2005.34, ISBN 978-0-7695-2468-9, Número de identificación del sujeto  3259694
• Rivest, Ronald L. ; Vuillemin, Jean (1975), "Una generalización y prueba de la conjetura de Aanderaa-Rosenberg", Actas del 7º Simposio ACM sobre teoría de la computación (STOC 1975): Albuquerque, Nuevo México, Estados Unidos, págs. 6–11, CiteSeerX  10.1.1.309.7236 , doi :10.1145/800116.803747, S2CID  16220596
• Rosenberg, Arnold L. (1973), "Sobre el tiempo necesario para reconocer propiedades de grafos: un problema", SIGACT News , 5 (4): 15–16, doi : 10.1145/1008299.1008302
• Scheidweiler, Robert; Triesch, Eberhard (2013), "Un límite inferior para la complejidad de las propiedades de los gráficos monótonos", SIAM Journal on Discrete Mathematics , 27 (1): 257–265, doi :10.1137/120888703
• Triesch, Eberhard (1996), "Sobre la complejidad de reconocimiento de algunas propiedades de grafos", Combinatorica , 16 (2): 259–268, doi :10.1007/BF01844851, S2CID  40830285
• Yao, Andrew Chi-Chih (1988), "Las propiedades de los gráficos bipartitos monótonos son evasivas", SIAM Journal on Computing , 17 (3): 517–520, doi :10.1137/0217031
• Yao, Andrew Chi-Chih (1991), "Límites inferiores para algoritmos aleatorios para propiedades de grafos", Journal of Computer and System Sciences , 42 (3): 267–287, doi : 10.1016/0022-0000(91)90003-N

Lectura adicional

• Bollobás, Béla (2004), "Capítulo VIII. Complejidad y empaquetamiento", Teoría de grafos extremos , Nueva York: Dover Publications , pp. 401–437, ISBN 978-0-486-43596-1.
• Lovász, László ; Young, Neal E. (2002), "Notas de la conferencia sobre la evasividad de las propiedades de los gráficos", arXiv : cs/0205031v1
• Chronaki, Catherine E (1990), Un estudio sobre la evasión: límites inferiores de la complejidad del árbol de decisión de las funciones booleanas , CiteSeerX  10.1.1.37.1041 .
• Michael Saks , Árboles de decisión: problemas y resultados, antiguos y nuevos (PDF)