No determinismo Bounded asocia una función con una clase de las lenguas aceptadas por las máquinas de Turing deterministas-delimitada de recursos, para formar una nueva clase - . Esta clase consta de aquellos lenguajes que son aceptados por alguna máquina de Turing no determinista obedece a los mismos límites de recursos que se utilizan para definir , pero donde tiene permitido realizar a lo sumo movimientos no deterministas. (Estoy usando la notación de Goldsmith, Levy y Mundhenk, en lugar del original de Kintala y Fischer, es el tamaño de la entrada).
Mi pregunta:
¿Hay una constante tal que GRAPH ISOMORPHISM está en - ?
( Editar: Joshua Grochow señaló que una respuesta positiva a esta pregunta implicaría un algoritmo para IG que tiene mejores límites de tiempo de ejecución asintóticos que los que se conocen actualmente. Por lo tanto, me complacería relajar el límite, permitiendo movimientos no deterministas.)
Fondo
Por cada constante fija , - , ya que movimientos no deterministas crean como máximo un número polinómico de configuraciones para explorar de forma determinista. Además , y mediante el relleno se pueden exhibir idiomas NP-completos en - para cada .
Kintala y Fischer observaron que decidir si un gráfico de entrada con vértices tiene una camarilla es -complete, pero está en - . Para ver esto, descarte los vértices que tienen como máximo vecinos. Si quedan muy pocos vértices restantes, rechazar. De lo contrario, los vértices restantes forman un gráfico de tamaño . Luego adivine un subconjunto de vértices | V | / 3 usando | V | = O (\ sqrt {n}) pasos no deterministas y verifique que formen una camarilla en tiempo polinómico.
Algunos otros idiomas de gráficos densos en también están en - . Este es el caso de cualquier problema en el que un subconjunto de los vértices sirve como certificado, y el tamaño del gráfico de entrada es . Ejemplos son las versiones prometedoras de Induced Path o 3-Coloring para el caso de gráficos densos. Otros problemas parecen requerir certificados más grandes, por ejemplo, una lista de vértices que definen un circuito hamiltoniano parece requerir bits . No me queda claro si uno podría usar una cantidad de no determinismo que es demasiado pequeña para adivinar el certificado para decidir tales problemas.
Dado que - puede contener lenguajes NP-completos, entonces parece interesante preguntar en qué parte de la jerarquía limitada del no determinismo caen los lenguajes potencialmente más fáciles. Uno podría esperar que GI, como un lenguaje que no parece ser NP-complete, esté en la jerarquía más cercana a - que a - . Sin embargo, el certificado obvio para GI especifica el mapa usandobits, que es .
Otra forma de pensar sobre esta pregunta: ¿es especificar un mapa entre los conjuntos de vértices el certificado más corto posible para GI?
Editar: Siguen algunos comentarios adicionales (corregidos), para abordar los comentarios de Joshua Grochow.
Si un certificado usa bits y puede verificarse en tiempo polinómico, entonces la fuerza bruta proporciona un algoritmo para que GI tome tiempo. Con un certificado de tamaño , la fuerza bruta proporciona un algoritmo que tarda tiempo, mientras que un certificado de tamaño produce un enfoque de fuerza bruta que tarda tiempo. El límite superior de larga data de Luks es tiempo, que se encuentra entre estos dos límites hasta exponentes constantes.
Estas consideraciones sugieren que podría haber un enfoque alternativo para IG. El enfoque de Luks parece basarse en la identificación de un subconjunto de generadores de un grupo asociado. Por lo tanto, una máquina no determinista podría adivinar un subconjunto del grupo. Estos subconjuntos podrían entonces verificarse exhaustivamente para obtener un algoritmo determinista. Si la lista de elementos se puede especificar de manera sucinta, ya sea porque el grupo asociado nunca es mucho mayor que el tamaño del gráfico, o porque el número de generadores requeridos es siempre pequeño, y verificar cada subconjunto candidato no toma demasiado tiempo, entonces esto podría dar un enfoque alternativo a GI.
- Chandra MR Kintala y Patrick C. Fischer, Refinando el no determinismo en la computación limitada en el tiempo polinomial relativizado , SIAM Journal on Computing 9 (1), 46–53, 1980. doi: 10.1137 / 0209003
- Judy Goldsmith, Matthew A. Levy, Martin Mundhenk, No determinismo limitado , SIGACT News 27 (2), 20–29, 1996. doi: 10.1145 / 235767.235769
- László Babai y Eugene M. Luks, Etiquetado canónico de gráficos , STOC 1983, 171-183. doi: 10.1145 / 800061.808746
fuente
Respuestas:
Primero, (como se ha editado en el enunciado de la pregunta) una respuesta positiva a su pregunta mejoraría de inmediato el estado del arte en el peor de los casos para el isomorfismo gráfico. Para un algoritmo produce un algoritmo determinista de tiempo , pero el mejor conocido actualmente para GI es soloO(n−−√)−PTIME 2O(n√) 2O(nlogn√)
En segundo lugar, ni siquiera me queda claro de inmediato si el mejor algoritmo actual es o no un algoritmo , aunque la primera parte es claramente, en Algún sentido. El algoritmo primero adivina un conjunto de vértices de tamaño para individualizar (el truco de Zemlyachenko: vea aquí una exposición en inglés), que se puede hacer adivinando bits de forma no determinista . Sin embargo, después de adivinarlos e individualizar (en tiempo polivinílico determinista), aplica la prueba de isomorfismo de grado acotado más conocida, que lleva tiempo (Teorema 9.1 de este documento ), y lo aplica en el caso deO(nlogn−−−−−√)−PTIME n/logn−−−−−−√ nlogn−−−−−√ nO(d/logd) d=O(nlogn−−−−−√) . Tendría que pensar detenidamente si el último algoritmo podría convertirse en un algoritmo (parece una pregunta interesante ...)O(nlogn−−−−−√)−PTIME
fuente