Suponiendo P= NP, ¿cómo se resolvería el problema de colorear el gráfico en el tiempo polinomial?

Question

Suponiendo que tenemos $ \ sf p= np $ , ¿cómo mostraría cómo resolver el problema de colorear gráfico en el tiempo polinomial?

Dado un gráfico $ g= (v, e) $ , encuentra un colorante válido $ \ chi (g): V \ a \ {1,2, \ CDOTS, K \ \} $ para algunos $ k $ satisfacer la propiedad que $ (u, v) \ in e $ implica $ \ chi (u) \ ne \ chi (v) $ paraMinimice el menor número $ k $ de "colores".

Answer 1

Hay dos casos:

1. $ p= np $ no constructivamente: Esto significa que hemos derivado una contradicción de la suposición de que $ P \ NEQ NP $ , y por lo tanto puede concluir que $ p= np $ por la ley del medio excluido. En este caso, tenemos Sin idea a qué se ve un algoritmo para resolver el color de la gráfica en el tiempo polinomial, o cualquier otro problema. Sabemos que existe, porque sabemos que si no existe, podemos derivar una contradicción. Por lo tanto, una prueba de este formulario es bastante inútil para resolver problemas rápidamente.

2. $ p= np $ constructivamente. En este caso, tenemos un algoritmo de tiempo polinomial para algunos $ np $ -hard problema, digamos $ l $ . Si $ l $ es NP-HARD, entonces debe resolver algún otro problema NP) en el tiempo polinomial (es decir, se reduce de ese problema). Ese problema, a su vez, se reduce de otro problema, o tiene una reducción directa de cada problema en $ np $ . Seguimos siguiendo el camino de las reducciones hasta que lleguemos a uno con una prueba directa (probablemente 3SAT).

   Al componer estas reducciones, obtenemos un algoritmo que resuelve 3SAT en tiempo polinomial (porque cada reducción solo hace un número polinomial de llamadas al algoritmo anterior, y nuestro algoritmo inicial para $ L $ se ejecuta en tiempo polinomial.

   Luego enchufes ese algoritmo a la reducción de cook-levin teorema , que nos da una manera de simularlo cualquier algoritmo que se ejecuta en tiempo polinomial con un número polinomial de llamadas a un solucionador 3SAT. Nuevamente, un número polinomial de llamadas a un algoritmo de tiempo polinómico se ejecuta en el tiempo polinomial.

   Finalmente, hay un simple algoritmo no determinista que resuelve coloración de gráficos en el tiempo polinomial: simplemente adivine un colorante y compruebe si es válido. Así que usamos Cook-Levin para simular este algoritmo en tiempo polinomial.

   Como puede imaginar, cada vez que tenemos que componer una reducción, el grado de nuestro polinomio se va a mejorar y más alto. Por lo que es completamente posible que $ p= np $ pero la coloración de gráficos solo se puede resolver, digamos, $ O (n ^ {100000000000000}) $ tiempo. Esto sigue siendo un tiempo polinomial, pero realmente no nos compra mucho en términos de resolver problemas prácticamente.

Answer 2

Si P= NP, eso significa que hay un problema determinado en NP, por ejemplo, el problema "es $ g $ $ k $ -colorable?", Donde $ g $ es un gráfico finito y $ k $ un entero, hay un algoritmo para resolverlo en tiempo polinomial.

Desafortunadamente, nuestro problema no está en NP. Queremos encontrar un $ k $ -coloring para el mínimo posible $ k $ . Ahora podemos encontrar el mínimo posible $ K $ en el tiempo polinomial simplemente resolviendo repetidamente el problema anterior para $ k= 1, 2, \ ldots $ , hasta que devuelva la respuesta "Sí". (Nota Esto sucede por el tiempo $ K $ alcanza el número de vértices, si no antes, por lo que solo se necesitan un número polinomial de instancias).

Pero ahora que sabemos $ k $ , ¿cómo encontramos un $ k $ -coloring ? Bueno, si $ k $ es igual a la cantidad de vértices, eso es fácil: cada vértice debe tener un color diferente. Si $ k $ es menor que el número de vértices, luego en cualquier color (y sabemos que uno existe), hay dos vértices $ x $ y $ y $ del mismo color (que debe ser no adyacente). Eso significa que podemos combinar $ x $ y $ y $ (elimínelos y reemplácelos con un nuevo vértice que es adyacente a todos los vecinos de $ x $ o $ y $ ), y los mismos trabajos para colorear Para este nuevo gráfico. Así que este nuevo gráfico también es $ k $ -colorable, y tiene un menor vértice.

Entonces, lo que podemos hacer es correr sobre todos los pares de vértices no adyacentes $ x, y $ y verifique si la nueva gráfica formada por combinación de $ x $ y $ y $ es $ k $ - Colorable, hasta que obtengan una respuesta "Sí" (esto debe ocurrir). Luego repitimos este proceso, realizamos un seguimiento de los cuales los vértices originales se combinaron para formar cada vértice actual, hasta que el gráfico solo tenga $ k $ vértices. Esto divide los vértices del gráfico original en $ k $ conjuntos, y podemos simplemente dar a cada uno su propio color para obtener un $ k $ -coloring of $ g $ .

Answer 3

El siguiente algoritmo esbozado, asumiendo P= NP, encuentra un color de 3 colores del gráfico de entrada si existe, en tiempo polinomial. Sin embargo, si no hay tal color, nunca termina.

Primero, aprenda a enumerar todos los algoritmos posibles (máquinas de Turing), y para simular el cálculo de cualquier máquina de tutería en la entrada arbitraria.

segundo, aprenda a enumerar todos los algoritmos posibles con un reloj de alarma de polietileno adjunto. (Eso significa que estaremos enumerando un caso especial de máquinas de Turing que conceptualmente hagan dos cosas en paralelo; en un conjunto de cintas, calculan el "problema principal", y en una cinta separada, simplemente cuentan a cero de un fijo una de las funciones N, 2 * N ^ 2, 3 * N ^ 3, ..., donde n es la longitud de la entrada al problema principal, deteniendo el cálculo (tal vez prematuramente desde la perspectiva del problema principal) una vez La cuenta regresiva en la cinta separada (llamada reloj de alarma) llega a cero antes de que se resuelva el problema principal. Por lo tanto, a veces el cálculo se termina porque se ha proporcionado una salida para el problema principal, y a veces el cálculo termina por el reloj de alarma, con la salida. cinta que contiene lo que suceda.)

El orden exacto en el que las máquinas de Turing con un reloj de alarma polinomial adjunto se enumeran deben ser exhaustivas: debe ser tal que encontraremos todas las combinaciones de una máquina de Turing y de una función de reloj de alarma entre las sugeridas anteriormente antes. o posterior.

Ahora, aprenda a simular todas estas máquinas de Turing con un reloj de alarma polinomial adjunto en paralelo, iniciándolos bien espaciados en el tiempo uno por uno. En particular, asegúrese de que casi la mitad del tiempo de funcionamiento total se dedique a la primera máquina de Turing con un reloj de alarma polinomial adjunto en la enumeración, casi una cuarta parte del tiempo total de funcionamiento a la segunda máquina, casi un octavo de la misma a la Tercera máquina y así sucesivamente. (Nos estamos asegurando que cada máquina de Turing en la enumeración reciba un rango de fracción constante conocido del tiempo de ejecución total, asumiendo que seguimos funcionando al menos hasta su primera transición).

¿Cómo podemos hacer eso? Ejemplo: simular una transición de la primera máquina. Luego, la misma otra vez, una transición más de la primera máquina. Luego una transición de la segunda máquina. Que todo esto de nuevo: dos transiciones más de la primera máquina y una más de la segunda máquina. Solo luego realice la primera transición de la tercera máquina, seguido de todo eso nuevamente (siete transiciones más en total) antes de simular la primera transición de la cuarta máquina.

De vez en cuando, una máquina termina, ya sea debido a su reloj de alarma o que ha resuelto su problema principal (que rara vez consistirá en una producción de 3 colorantes del gráfico de entrada, pero a quién le importa). Si una máquina terminó, verificamos si ha producido una coloración válida de 3 del gráfico de entrada en su cinta de salida, y de ser así, terminamos toda la simulación de todas las máquinas de Turing con relojes de alarma adjuntos, devolviendo la misma coloración 3 salida.

Para ser honesto, no he comprobado de cerca que puedo amortizar la sobrecarga de cambiar la atención de una máquina a una máquina, la sobrecarga de la iteración a través de las máquinas (es decir, generando el estado inicial de una nueva máquina en la enumeración. ), y la sobrecarga de verificar los estados del terminal (ya sea que una máquina terminante se topó con una coloración de 3 válidas o no); Pero ciertamente puedo asegurarme de pasar más tiempo en las transiciones simuladas de las máquinas de Turing individuales que en todos estos tipos de gastos generales, es decir, la sobrecarga total termina menos del 100%, nuevamente un factor constante.

Ahora, es bien sabido que la versión de función del problema de los 3 colorantes es autodescible para su versión de decisión. Hay un simple algoritmo de tiempo polinomial para el problema de la decisión (por P= NP) y, por lo tanto, el algoritmo auto-reductor que en realidad identifica de manera confiable un ejemplo 3 en el tiempo de polinomio cuando existe, ocurre en algún lugar en nuestra enumeración de todas las máquinas de Turing, y se produce en algún lugar, incluso con un reloj de alarma de tiempo polinomial, lo que le permite completar en cualquier momento que necesite. Buenas noticias es que dimos una fracción fija de atención (del recurso de tiempo) a esta máquina en particular en nuestra simulación de multitarea, por lo tanto, lo hemos desacelerado solo por un (enorme) factor constante, por las otras máquinas simultáneamente simuladas, y por El resto hasta el 100% superior. Por lo tanto, incluso esta simulación "universal" específica es capaz de proporcionar ejemplos de 3 colores en tiempo polinomial. Quod erat promisso.

===

(Me encantaría decir que esta simulación se acerca a preservar incluso el exponente óptimo de encontrar la coloración 3, pero eso simplemente no sería cierto. El mayor problema a este respecto es que el simulador "universal" puede tienen menos cintas y menos estados que la máquina simulada y simulando incluso

Una sola transición es un ejercicio costoso; La simulación preserva el tiempo polinomial, pero no el exponente específico.)

Desafortunadamente, cualquier simulación de este tipo solo se convierte en un algoritmo de tiempo polinomial para encontrar 3-colorantes si ahora lo equipamos con su propio reloj de alarma de tiempo polinomial (así lo disminuyen dos veces, y también garantiza que termina en cualquier entrada dentro del especificado. límite de tiempo); Y este último paso es constructivo. A diferencia de cualquier parte de la construcción hasta ahora, no sabemos qué polinomio entre N, 2 * N ^ 2, 3 * N ^ 3, ... debe ser elegido para el reloj de alarma. Sólo sabemos que existe un despertador suficientemente liberal, de modo que si lo adjuntamos a nuestra máquina (de lo contrario específica) "universal", obtendremos un algoritmo de tiempo polinomial haciendo 3 colorantes dondequiera que existan y rechazando (solo) gráficos que no estén 3 Colorable, o entradas que no codifican gráficos.

El método de simulación universal se puede extender incluso a su problema de coloración de gráficos con la ayuda de la técnica adicional descrita en esta respuesta . Lo que se vuelve más desordenado es que ya no podemos filtrar "respuestas incorrectas" que faciliten fácilmente; Si una máquina nos ofrece un color de 5 colores, ¿cómo sabemos si existe una 4 colores? La solución suficiente es simplemente esperarlo, ya sea que aparezca una salida de 4 colores en la salida de una máquina para niños mejor comportada o no, antes de que se agote el reloj de alarma maestro. Nuevamente, el último paso será no constructivo: sabemos que con un reloj de alarma de tiempo polinomial suficientemente liberal, obtendríamos un algoritmo polinomial que nos brindará colorantes óptimos, pero es difícil decir qué polinomio específico elegir si todo lo que sabemos es que todo lo que sabemos es que P= np. Si elegimos un reloj de alarma de tiempo polinomial demasiado agresivo (insuficiente), no solo, a veces, no podemos encontrar la coloración óptima, sino que a veces emitiremos una coloración subóptima que intentamos esperar, pero no lo suficientemente pacientemente.

Answer 4

Tener P= NP significa que es un algoritmo de tiempo polinomial.No significa que seamos sepan uno, o lo haremos saber uno, o podremos ser capaces de se ejecuta en tiempo polinomial.

y podríamos encontrar que hay un algoritmo que se ejecuta en O (n ^ 10000), lo que significa que podemos resolverlo sin instancias de tamaño> 1 .