¿Cuáles son las consecuencias de decir que una máquina de Turing no determinista puede resolver NP en tiempo polinomial?

Question

estos días he estado estudiando sobre problemas de NP, complejidad computacional y teoría. Creo que finalmente he entendido los conceptos de Turing Machine, pero tengo un par de dudas.

puedo aceptar que una máquina de Turing no determinista tiene varias opciones de qué hacer para un estado y un símbolo dado se está leyendo y que siempre va a elegir la mejor opción, según lo declarado por wikipedia

Cómo ¿la NTM "sabe" cuál de estas acciones debería tomar? Hay dos formas de mirarlo. Una es decir que la máquina es la "más afortunada adivinadora "; siempre elige la transición que finalmente lleva a un estado de aceptación, si hay una transición de tal . La otra es imaginar que la máquina "ramifica" en muchas copias , cada una de las cuales sigue una de las posibles transiciones. Mientras que un DTM tiene una sola "ruta de cálculo" que sigue, un NTM tiene un "árbol de cálculo" . Si cualquier rama de el árbol se detiene con una condición de "aceptar" , decimos que la NTM acepta la entrada.

Lo que no puedo entender es que, dado que se trata de una máquina imaginaria, ¿qué ganamos al decir que puede resolver problemas de NP en tiempo polinomial? Quiero decir, también podría teorizar sobre una máquina mágica que resuelve problemas NP en O (1), ¿qué obtengo de eso si es que nunca existe?

Gracias de antemano.

Answer 1

Una máquina de Turing no determinista es un concepto difícil de entender. Probar algunos otros puntos de vista:

1. En lugar de ejecutar una máquina de Turing mágico que es el adivinador más afortunada posible, ejecute un meta-máquina aún más mágico que pone en marcha un número infinito de adivinar al azar las máquinas de Turing independientes en universos paralelos. Toda posible secuencia de conjeturas se hace en algún universo. Si en al menos uno de los universos la máquina detiene y acepta la entrada, es suficiente: la metamatriz que configura estos universos paralelos acepta la instancia del problema. Si en todos los universos la máquina rechaza o no puede detenerse, la meta máquina rechaza la instancia.

2. En lugar de cualquier tipo de adivinanza o ramificación, piense en una persona que intenta convencer a otra persona de que la instancia debe ser aceptada. La primera persona proporciona el conjunto de elecciones que realizará la máquina de Turing no determinista, y la segunda persona verifica si la máquina acepta la entrada con esas elecciones. Si lo hace, la segunda persona está convencida; si no lo hace, la primera persona ha fallado (lo cual puede ser porque la instancia no puede ser aceptada con cualquier secuencia de elecciones, o porque la primera persona eligió una secuencia pobre de opciones).

3. Olvídese de las máquinas de Turing. Un problema está en NP si se puede describir con una fórmula en el second-order logic existencial. Es decir, se toma una lógica proposicional simple, se permiten los cuantificadores sobre las variables proposicionales y se permite unir al principio los cuantificadores existenciales sobre los conjuntos, las relaciones y las funciones.Por ejemplo, graph three-colorability puede ser descrito por una fórmula que comienza con cuantificación existencial sobre los colores (conjuntos de nodos):

   ∃ R ∃ G ∃ B

   Cada nodo debe ser de color:

   ∃ R ∃ G ∃ B (y forall; x (R (x) ∨ G (x) ∨ B (x)))

   y no hay dos nodos adyacentes pueden tener el mismo color – llamar a la relación borde E:

   ∃ R ∃ G ∃ B (y forall; x (R (x) ∨ G (x) ∨ B (x))) ∧ (y forall; x, y ¬ (E (x, y) ∧ ((R (x) ∧ R (y)) ∨ (G (x) ∧ G (y)) ∨ (B (x) ∧ B (y)))))

   La cuantificación existencial sobre las variables de segundo orden es como una máquina de Turing no determinista hacer conjeturas perfectos. Si desea convencer a alguien de que una fórmula ∃ X (...) es verdadera, puede comenzar dando el valor de X. Que las MNA de tiempo polinomial y estas fórmulas no solo "me gusta" sino que son equivalentes es el teorema de Fagin, que comenzó el campo de descriptive complexity: clases de complejidad caracterizadas no por máquinas de Turing sino por clases de fórmulas lógicas.

También dijo

que también podría teorizar de una máquina mágica que resuelve los problemas NP en O (1)

Sí, se puede. Estos se llaman oracle machines (sin relación con el DBMS) y han arrojado resultados interesantes en la teoría de la complejidad. Por ejemplo, Baker – Gill – El teorema de Solovay establece que hay oráculos A y B tales que para las máquinas de Turing que tienen acceso a A, P = NP, pero para las máquinas de Turing que tienen acceso a B, P ≠ NP. (A es un oráculo muy poderoso que hace irrelevante el no determinismo, la definición de B es un poco complicada e implica un truco de diagonalización). Este es un tipo de meta-resultado: cualquier prueba que resuelva la pregunta P vs NP debe ser sensible suficiente para la definición de una máquina de Turing que falla cuando se agregan algunos tipos de oráculos.

---

El valor de las máquinas de Turing no determinista es que ofrecen un comparativamente simple caracterización, computacional de la clase de complejidad NP (y otros): en lugar de árboles de cálculo o fórmulas lógicas de segundo orden, que se pueda imaginar una computadora casi ordinaria que ha sido (comparativamente) ligeramente modificada para que pueda hacer conjeturas perfectas.

Answer 2

Lo que gana de eso es que puede demostrar que hay un problema en NP demostrando que puede ser resuelto por un NTM en tiempo polinomial.

En otras palabras, puede usar las MNA para averiguar si un problema determinado está en NP o no.

Answer 3

De Wikipedia en Hebreo - "NTM es principalmente una herramienta para pensar, y es imposible implementar realmente tal máquina". Puede reemplazar el término "NTM" por "Algoritmo que en cada paso prueba todos los pasos posibles" o "Algoritmo que en cada paso elige el siguiente paso mejor" ... Y creo que comprende el resto. NTM está aquí solo para ayudarnos a visualizar dicho algoritmo. Puede ver here cómo se supone que debe ayudarlo a visualizar (en la respuesta de Pascal Cuoq).

Answer 4

Por definición, NP significa tiempo polinomial no determinista como se puede buscar en Wikipedia.

Una encarnación de una máquina de Turing no determinista que elige al azar y examina (o ensambla) la siguiente solución potencial resolverá un problema de NP en tiempo polinomial con cierta probabilidad (resolvería el problema en tiempo de polietileno con absoluta certeza si fuera el "adivino más afortunado posible").

Por lo tanto, decir que una NTM puede resolver un problema en tiempo polinomial significa que ese problema está en NP. De nuevo, esto es equivalente a la definición de la clase de problemas NP.

Answer 5

Lo que ganamos es que si tenemos el poder mágico para adivinar el paso correcto, que siempre será correcto, podemos resolver problemas de NPC en POLYTIME.Por supuesto, no siempre podemos "adivinar" el paso correcto. Entonces es imaginario Pero así como los números imaginarios son aplicables a problemas del mundo real, las consecuencias pueden ser teóricamente útiles.

Un aspecto positivo de transformar los problemas originales de esta manera es que podemos abordarlos desde diferentes ángulos. En un dominio teórico, es algo bueno porque tenemos (1) más enfoques que podemos tomar (por lo tanto, más documentos) y (2) más herramientas que podemos usar si pueden redactarse en otros campos.

Answer 6

Creo que su respuesta es su pregunta. En otras palabras, dado un problema puede probar que es un problema de NP si puede encontrar una NTM que lo resuelva.

Los problemas de NP son una clase especial de problemas, y la NTM es solo una herramienta para verificar si el problema dado pertenece a la clase o no.

Tenga en cuenta que la NTM no es una máquina específica, es una clase completa de máquinas con reglas bien definidas de lo que pueden y no pueden hacer. Para utilizar máquinas "mágicas", necesita definirlas y mostrar qué clase de complejidad de problemas corresponden.

Ver http://en.wikipedia.org/wiki/Computational_complexity_theory#Complexity_classes para obtener más información.