NP duro / completo

7

Nunca he sido muy claro en este concepto. Por favor ayuda:

Al final del día, deberíamos querer identificar problemas útiles para los cuales no tenemos una solución polinomial hasta el momento y solo tenemos soluciones exponenciales. Queremos seguir encontrando si podemos encontrar una solución polinómica para estos problemas y el uso de las reducciones es solo para poder identificar nuevos problemas únicos de solución exponencial con la ayuda de los problemas exponenciales conocidos existentes.

¿Por qué el concepto de determinismo y el no determinismo se incorpora a este concepto de problemas de solución exponencial y polinomial? ¿Cómo es útil esta noción?

¿Cómo llamamos a los problemas para los cuales solo tenemos una solución exponencial hasta ahora, pero no hemos podido encontrar una reducción a un NP conocido - problemas difíciles / completos ...?

Gracias,

    
pregunta xyz 20.05.2011 - 16:41

3 respuestas

4

No hay nada obvio sobre el determinismo y el no determinismo que lleve a esto. Es un poco técnico.

Un autómata determinista corresponde a lo que realmente podemos construir, ya sea en hardware o en software.

Un autómata no determinista intenta todas las soluciones posibles, pero para estar en tiempo polinomial tiene que poder verificar una solución posible en tiempo polinomial. Si te basas en la teoría, reconocerás que una NA es equivalente a una DA con un oráculo que da misteriosamente una solución, por lo que una NA puede resolver algo en tiempo polinomial si una DA puede verificar una solución propuesta en tiempo polinomial. Un autómata no determinista es equivalente a un autómata determinista que prueba todas las combinaciones posibles, y el conjunto de todas las combinaciones posibles tiene exponencialmente más miembros que el conjunto de cosas que se combinan, por lo que si una NA puede hacer algo en el tiempo polinomial, un DA puede hacerlo. en exponencial.

NP es el conjunto de problemas de decisión, por lo que un DA (por lo tanto, una computadora real) puede verificar una solución en tiempo polinomial. Si no podemos verificar una solución propuesta en tiempo polinomial, ciertamente no podremos generar una, por lo que NP es esencialmente el conjunto de problemas de decisión que pueden tener soluciones en tiempo real para polinomios.

El problema del vendedor ambulante, como se suele dar, no está en NP porque no está claro cómo verificar que una ruta dada sea la más barata en tiempo polinomial. Sin embargo, una variante del TSP en la que la pregunta es si hay una solución con un costo inferior a X está en NP, ya que es fácilmente verificable y si podemos resolver ese problema podemos determinar la ruta más barata fácilmente. Por lo tanto, el TSP como se suele afirmar es NP-duro, lo que significa que es tan difícil de resolver como un problema NP-completo.

Hay problemas que no tienen soluciones polinomiales conocidas para una AN, y problemas que sabemos que no están en la NP. Esos problemas generalmente se clasifican por clases de complejidad adicionales (los problemas de PSpace, por ejemplo, se pueden resolver en el espacio polinomial, pero posiblemente solo en el tiempo exponencial), o se pueden catalogar como indecidibles. No conozco ningún término para un problema, por ejemplo, que es PSpace pero no se sabe que esté en NP.

    
respondido por el David Thornley 20.05.2011 - 17:12
7

NP toma su nombre del hecho de que se puede resolver en polinomio mediante máquina de Turing no determinista . El truco es que los medios no deterministas en ese caso, como si pudiera evaluar mágicamente todas las ramas en paralelo. Es un modelo teórico, no debes intentar compararlo con las computadoras de la vida real. De hecho, tiene mucho más que ver con el área de matemáticas conocida como lenguajes formales y teoría de computabilidad .

NDTM se puede "reducir" a una máquina determinista de Turing, pero en tiempo exponencial. Es por eso que no hay soluciones polinomiales para los problemas de NP-completos en las computadoras, lo que (como usted señaló correctamente) es determinista.

    
respondido por el vartec 20.05.2011 - 16:56
1

El concepto de determinista contra no determinista entra en juego por la forma en que estos problemas se están estudiando en las máquinas de Turing.

Conceptualmente, una máquina de Turing puede resolver cualquier problema de Turing completo mediante uno de estos dos métodos:

  1. Cada acción se realiza secuencialmente sin bifurcarse cuando se toma una decisión, es decir, es determinista porque puede seguir la ruta exacta de ejecución.
  2. Cada acción se realiza de forma secuencial, pero se produce una rama cada vez que se toma una decisión para poder explorar cada rama, es decir, una máquina de Turing no determinista.

Por lo tanto, en una máquina no determinista, si el algoritmo puede encontrar una solución, usted sabe que existe una solución que se encontró en el tiempo polinomial, pero no sabe qué rama de ejecución se usó para encontrar esa solución. Sin embargo, las cosas se ponen interesantes porque una máquina de Turing puede simular una máquina de Turing no determinista, pero para ello debe calcular cada ruta a través del código y aquí es donde está la naturaleza exponencial de los problemas de NP.

Las máquinas de Turing se utilizan para este tipo de estudio debido a su naturaleza simple, lo que hace que entenderlas a un nivel matemático sea mucho más fácil cuando le preocupan las matemáticas básicas del problema sin tener que preocuparse por los gastos generales con los que podría estar involucrado. Utilizando diferentes tipos de máquinas.

En lo que respecta a un problema para el cual tenemos una solución exponencial en una máquina de Turing determinista pero no hay reducción a un problema conocido, sería EXPTIME .

    
respondido por el rjzii 20.05.2011 - 17:14

Lea otras preguntas en las etiquetas