Cómo es ineficiente gráfico menores teorema?

Question

Una muy interesante Robertson-Seymour (los gráficos de los menores de edad) teorema dice:

Cualquier colección infinita de los gráficos de $C$ con la propiedad de que si $G\in C $, a continuación, sus los menores de edad también se tiene la forma $\{$gráficos $G$ que no contienen ninguna $E_i\}$ para algunos finito de la colección de $E = \{E_i\}$.

Así, el teorema dice que podría crear una lista de prohibida a menores de edad para averiguar si el gráfico es torically integrable, pero esto no ayuda mucho, ya que la lista es de los dos no completamente conocidos y grandes.

Me pregunto si esta dificultad es porque

1. de hecho, es difícil probar esta propiedad de un gráfico
2. el teorema de hace girar fácilmente comprobable propiedades en largas listas de
3. no se sabe cómo efectivamente transformar fácilmente comprobable propiedades en las listas de

He aquí la cuestión formal:

Considere la posibilidad de un polinomio algoritmo de $P$ que devuelve una pregunta de sí/no, dado un grafo como una entrada y que siempre devuelve sí, para los menores de edad de cualquier gráfico para la cual se devuelve sí. Existe $E$, la excepcional lista de una colección definida por $P$. Lo que se sabe acerca de la computabilidad del mapa $P\mapsto E$?

Answer 1

Para una referencia sobre este problema, consulte Cattell et al, "En la computación gráfica menor obstrucción de conjuntos", Teori. Comput. Sci. 2000.

Creo que la respuesta a su pregunta es que es recursivamente enumerable (uno puede poner a prueba todos los gráficos de uso de P para ver si pertenecen a la E), pero no recursivo (sin más información, no hay ninguna manera de saber que uno ha encontrado todas las obstrucciones).

He aquí una construcción específica que muestra esto: dada una instancia h de la detención problema, construir un algoritmo que reconozca todos los gráficos si h es un no-detener la instancia, o que reconoce los gráficos sin K_s menor si h se detiene en s pasos. No es difícil hacer esto de tal manera que siempre es un polinomio de tiempo del algoritmo, pero uno no puede decir si el Correo está vacío o no vacío sin resolver la suspensión problema.

Answer 2

Para responder algunas de sus preguntas: 1. Sí, las pruebas de tales propiedades es generalmente difícil. Por ejemplo, antes de la gráfica menores teorema tuvimos propiedades para que ningún algoritmo fue conocido en todo! (Tal vez un recursivamente enumerable algoritmo se conoce, no recuerdo.) Después de que el gráfico de menores del teorema de tales propiedades se convirtió comprobable en el polinomio tiempo! Ahora que es un gran salto de ningún algoritmo conocido para el polinomio de tiempo. (Si recuerdo correctamente, el polinomio es como O(n log n), que es casi el tiempo lineal.)

Como para la 2. y 3., Yo no conozco a ninguna propiedad que fácilmente se puede probar, por que no sabemos lo prohibido a menores de edad. Me gustaría saber a estas propiedades, si se conocen. A mí me parece que si tenemos un algoritmo para la facilidad de la prueba de una propiedad, realmente entendemos la propiedad, y por lo tanto debe ser capaz de llegar con una lista de prohibidos a los menores de alguna manera. Por supuesto, esto es sólo un sentimiento.

EDIT: se me ha corregido en los comentarios. Por favor, lea Gil Kalai y David Eppstein comentarios.