Conjetura de Aanderaa-Karp-Rosenberg
# 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

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.

