Conjetura de Aanderaa-Karp-Rosenberg
Conjetura de Aanderaa–Karp–Rosenberg En la ciencia de la computación teórica, la conjetura Aanderaa-Karp-Rosenberg (también conocida como la conjetura Aanderaa-Rosenberg o la conjetura evasivas) es un grupo de conjeturas relacionadas sobre el número de preguntas del tipo "¿Hay un borde entre el vértice "u" y el vértice "v"? que tienen que ser respondidas para determinar si un grafo no dirigido tiene una propiedad particular, como la planitud o bipartiteness. Llevan el nombre de 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 será capaz de saltarse cualquier pregunta: cualquier algoritmo para determinar si la gráfica tiene la propiedad, no importa lo inteligente, podría tener que examinar cada par de vértices antes de que pueda dar su respuesta. Una propiedad satisfacer esta conjetura se llama evasiva.
Más precisamente, la conjetura Aanderaa-Rosenberg afirma que cualquier algoritmo determinista debe probar al menos una fracción constante de todos los posibles pares de vértices, en el peor de los casos, para determinar cualquier propiedad gráfica monótona no trivial; en este contexto, una propiedad es monótona si sigue siendo cierto cuando se añaden bordes (tan planitud no es monótona, pero no planaridad es monótona). Una versión más fuerte de esta conjetura, llamada la conjetura evasivas o la conjetura Aanderaa-Karp-Rosenberg, afirma que exactamente n (n - 1) / 2 se necesitan pruebas. Las versiones del problema de algoritmos aleatorios y algoritmos cuánticos también se han formulado y estudiado.
La determinación de la conjetura de Aanderaa-Rosenberg fue probada por Rivest y Vuillemin (1975), pero la más fuerte conjetura Aanderaa-Karp-Rosenberg sigue sin comprobarse. Además, hay una gran brecha entre el conjeturado límite inferior y el mejor demostrado límite inferior para la complejidad consulta aleatorizado y cuántica.
En la ciencia de la computación teórica, la conjetura Aanderaa-Karp-Rosenberg (también conocida como la conjetura Aanderaa-Rosenberg o la conjetura evasivas) es un grupo de conjeturas relacionadas sobre el número de preguntas del tipo "¿Hay un borde entre el vértice "u" y vértice "v"? "que tienen que ser respondidas para determinar si un grafo no dirigido tiene una propiedad particular, como la planitud o bipartiteness. Ellos llevan el nombre de 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 será capaz de saltarse cualquier pregunta: cualquier algoritmo para determinar si la gráfica tiene la propiedad, no importa lo inteligente, podría tener que examinar cada par de vértices antes de que pueda dar su respuesta. Una propiedad satisfacer esta conjetura se llama evasiva.
Más precisamente, la conjetura Aanderaa-Rosenberg afirma que cualquier algoritmo determinista debe probar al menos una fracción constante de todos los posibles pares de vértices, en el peor de los casos, para determinar cualquier propiedad gráfica monótona no trivial; en este contexto, una propiedad es monótona si sigue siendo cierto cuando se añaden bordes (tan planitud no es monótona, pero no planaridad es monótona). Una versión más fuerte de esta conjetura, llamada la conjetura evasivas o la conjetura Aanderaa-Karp-Rosenberg, afirma que exactamente n (n - 1) / 2 se necesitan pruebas. Las versiones del problema de algoritmos aleatorios y algoritmos cuánticos también se han formulado y estudiado.
El determinista conjetura Aanderaa-Rosenberg fue probada por Rivest y Vuillemin (1975), pero la más fuerte conjetura Aanderaa-Karp-Rosenberg sigue sin comprobarse. Además, hay una gran brecha entre el conjeturado límite inferior y el mejor demostrado límite inferior para la compleja consulta aleatoria cuántica.
Ejemplo editar
La propiedad de ser no vacía (es decir, que tiene al menos un borde) es monótona, porque la adición de otro borde para un gráfico no vacío produce otro gráfico no vacío. Hay un algoritmo simple para probar si un grafo es no vacía: bucle a través de todos los pares de vértices, probando si cada par está conectado por un borde. Si un borde es que se ha encontrado de esta manera, romper el lazo, y el informe que la gráfica es no vacío, y si el bucle finaliza sin haber encontrado ningún borde, luego de informar que el gráfico está vacía. En algunos gráficos (por ejemplo los gráficos completos) este algoritmo terminará rápidamente, sin la prueba de cada par de vértices, pero en el gráfico vacío que pone a prueba todos los pares posibles antes de terminar. Por lo tanto, la complejidad de la consulta de este algoritmo es n (n - 1) / 2: en el peor de los casos, el algoritmo realiza n (n - 1) / 2 pruebas.
El algoritmo descrito anteriormente no es el único método posible de las pruebas por falta de vacío, pero la conjetura Aanderaa-Karp-Rosenberg implica que cada algoritmo determinista para probar la no-vacío tiene la misma complejidad de la consulta, n (n - 1) / 2. Es decir, la propiedad de ser no vacío es evasiva. Para esta propiedad, el resultado es fácil de demostrar directamente: si un algoritmo no realiza n (n - 1) / 2 pruebas, no puede distinguir el gráfico vacío desde un gráfico que tiene un borde que conecta uno de los pares no probados de vértices, y debe dar una respuesta incorrecta en uno de estos dos gráficos.
Referencias editar
- Ambainis, Andris; Iwama, Kazuo; Nakanishi, Masaki; Nishimura, Harumichi; Raymond, Rudy; Tani, Seiichiro; Yamashita, Shigeru (2008), «Quantum query complexity of Boolean functions with small on-sets», Proceedings of the 19th International Symposium on Algorithms and Computation, Lecture Notes in Computer Science 5369, Gold Coast, Australia: Springer-Verlag, pp. 907-918, ISBN 978-3-540-92181-3, doi:10.1007/978-3-540-92182-0_79..
- Beals, Robert; Buhrman, Harry; Cleve, Richard; Mosca, Michele; de Wolf, Ronald (2001), «Quantum lower bounds by polynomials», Journal of the ACM 48 (4): 778-797, doi:10.1145/502090.502097..
- Best, M.R.; van Emde Boas, P.; Lenstra, H.W. (1974), A sharpened version of the Aanderaa-Rosenberg conjecture, Report ZW 30/74, Mathematisch Centrum Amsterdam, hdl: 1887/3792..
- Chakrabarti, Amit; Khot, Subhash (2001), «Improved Lower Bounds on the Randomized Complexity of Graph Properties», Proceedings of the 28th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science 2076, Springer-Verlag, pp. 285-296, ISBN 978-3-540-42287-7, doi:10.1007/3-540-48224-5_24..
- Chakrabarti, Amit; Khot, Subhash; Shi, Yaoyun (2001), «Evasiveness of subgraph containment and related properties», SIAM Journal on Computing 31 (3): 866-875, doi:10.1137/S0097539700382005..
- Friedgut, Ehud; Kahn, Jeff; Wigderson, Avi (2002), «Computing Graph Properties by Randomized Subcube Partitions», Randomization and Approximation Techniques in Computer Science, Lecture Notes in Computer Science 2483, Springer-Verlag, p. 953, ISBN 978-3-540-44147-2, doi:10.1007/3-540-45726-7_9..
- Gröger, Hans Dietmar (1992), «On the randomized complexity of monotone graph properties», Acta Cybernetica 10 (3): 119-127, archivado desde el original el 24 de septiembre de 2015, consultado el 16 de octubre de 2014..
- Hajnal, Péter (1991), «An Ω(n4/3) lower bound on the randomized complexity of graph properties», Combinatorica 11 (2): 131-143, doi:10.1007/BF01206357..
- Kahn, Jeff; Saks, Michael; Sturtevant, Dean (1983), «A topological approach to evasiveness», 24th Annual Symposium on Foundations of Computer Science (sfcs 1983), Los Alamitos, CA, USA: IEEE Computer Society, pp. 31-33, ISBN 0-8186-0508-1, doi:10.1109/SFCS.1983.4..
- King, Valerie (1988), «Lower bounds on the complexity of graph properties», Proc. 20th ACM Symposium on Theory of Computing, Chicago, Illinois, United States, pp. 468-476, ISBN 0-89791-264-0, doi:10.1145/62212.62258..
- Kleitman, D.J.; Kwiatkowski, DJ (1980), «Further results on the Aanderaa-Rosenberg conjecture», Journal of Combinatorial Theory. Series B 28: 85-95, doi:10.1016/0095-8956(80)90057-X..
- Kozlov, Dmitry (2008), Combinatorial Algebraic Topology, Springer-Verlag, ISBN 978-3-540-73051-4..
- Lutz, Frank H. (2001), «Some results related to the evasiveness conjecture», Journal of Combinatorial Theory, Series B 81 (1): 110-124, doi:10.1006/jctb.2000.2000..
- Korneffel, Torsten; Triesch, Eberhard (2010), «An asymptotic bound for the complexity of monotone graph properties», Combinatorica (Springer-Verlag) 30 (6): 735-743, ISSN 0209-9683, doi:10.1007/s00493-010-2485-3..
- Magniez, Frédéric; Santha, Miklos; Szegedy, Mario (2005), «Quantum algorithms for the triangle problem», Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, Vancouver, British Columbia: Society for Industrial and Applied Mathematics, pp. 1109-1117, arXiv:quant-ph/0310134..
- O'Donnell, Ryan; Saks, Michael; Schramm, Oded; Servedio, Rocco A. (2005), «Every decision tree has an influential variable», Proc 46th IEEE Symposium on Foundations of Computer Science, pp. 31-39, ISBN 0-7695-2468-0, doi:10.1109/SFCS.2005.34..
- Rivest, Ronald L.; Vuillemin, Jean (1975), «A generalization and proof of the Aanderaa-Rosenberg conjecture», Proc. 7th ACM Symposium on Theory of Computing, Albuquerque, New Mexico, United States, pp. 6-11, doi:10.1145/800116.803747..
- Rosenberg, Arnold L. (1973), «On the time required to recognize properties of graphs: a problem», SIGACT News 5 (4): 15-16, doi:10.1145/1008299.1008302..
- Scheidweiler, Robert; Triesch, Eberhard (2013), «A Lower Bound for the Complexity of Monotone Graph Properties», SIAM Journal on Discrete Mathematics 27 (1): 257-265, doi:10.1137/120888703.
- Triesch, Eberhard (1996), «On the recognition complexity of some graph properties», Combinatorica 16 (2): 259-268, doi:10.1007/BF01844851..
- Yao, Andrew Chi-Chih (1988), «Monotone bipartite graph properties are evasive», SIAM Journal on Computing 17 (3): 517-520, doi:10.1137/0217031..
- Yao, Andrew Chi-Chih (1991), «Lower bounds to randomized algorithms for graph properties», Journal of Computer and System Sciences 42 (3): 267-287, doi:10.1016/0022-0000(91)90003-N..