NP duro/completa

Question

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

Al final del día, debemos identificar útil problemas para los que no tenemos el polinomio solución hasta el momento y sólo han exponencial soluciones.Queremos mantener a encontrar si podemos encontrar un polinomio solución a estos problemas y el uso de las reducciones es sólo para ser capaz de identificar nuevas sólo exponencial de los problemas pueden resolverse con la ayuda de los actuales conocido exponencial de problemas.??

¿Por qué es el concepto de determinismo y no determinismo trajo a este concepto de la exponencial y el polinomio de resolver problemas?? Cómo es esta noción útil?

¿Cómo llamamos a los problemas para los que sólo tenemos solución exponencial hasta ahora, pero no hemos sido capaces de encontrar la reducción a un conocido NP - duro/completar los problemas..??

Gracias,

Answer 1

El: Si $\text{P} \neq \text{NP}$ implica NP-Duro de problemas requieren tiempo exponencial algoritmos es un mito común, lo que parece bastante frecuente.

De hecho, hemos sabido NP-Duro de los problemas que tienen sub-exponencial algoritmos! Por ejemplo, ver aquí: http://hal.inria.fr/docs/00/47/66/86/PDF/cops_journal_2008_10_16.pdf

Dicho esto, no es una conjetura, llamado el Tiempo Exponencial Hipótesis de que los estados que 3-SAT (y algunas de sus variantes) no puede ser resuelto en sub-exponencial del tiempo.

Ahora usted podría preguntarse ¿por qué el anterior sub-exponencial algoritmo para NP-Duro problema no falsificar el Tiempo Exponencial Hipótesis, como podemos última forma de una reducción de 3-SAT?

La razón es que las reducciones están autorizados a volar la entrada exponencialmente. Decir $A$ reduce a $B$ $B$ $\theta(2^{\sqrt{n}})$ de tiempo del algoritmo. Ahora bien, si la reducción hace que el tamaño de la entrada a$B$$n^2$$n$$A$), que todavía nos da un $\theta(2^n)$ de tiempo del algoritmo para $A$. Así que a pesar de $A$ nunca ha sub-algoritmos de tiempo exponencial, aún tiene que reducir a un problema que ha sub-algoritmos de tiempo exponencial.

En cuanto a por qué tenemos no-determinismo, estoy adivinando esto fue iniciado por Rabin y Scott en sus trabajos sobre el autómata finito determinista y no determinista autómata finito.

Una vez que Cook/Levin introdujo el concepto de NP-Completitud y Karp et al dio un seminales de la lista de 21 años natural de los problemas que son NP-Completos, NP se convirtió en una clase muy importante.

Creo que fue Edmonds, quien primero se caracteriza NP como 'problemas con el polinomio de certificados".

(Nota: Los tres párrafos de la memoria y yo no lo he comprobado).

De hecho, hay caracterizaciones de NP que no uso no-determinismo. El actual tema ha sido el uso de PCP Teorema para probar varios NP-resultados de Dureza para la aproximación a las versiones de NP-Duro de problemas.

Así, el no-determinismo es todavía parte de la definición de NP y es históricamente importante, pero la situación actual es que no es obligatorio.

Answer 2

Yo diría que el concepto de 'no determinismo' es uno de los grandes arenques rojos en la discusión de NP-completo los problemas. A mi mente es mucho mejor pensar en un problema que se está en NP como un criterio para la confirmación de soluciones'; si nos ha dado una hipotética solución instancia de un problema, podemos comprobar que en el polinomio tiempo?'. Visto de esta manera, una gran cantidad de problemas en NP convertido en una forma mucho más clara: por ejemplo, Satisfiability (de una expresión booleana) es verificado con sólo enchufar el intento de cesión a todas las variables de la expresión y la confirmación de que el resultado es cierto; el Problema del Viajante de comercio puede ser verificada mediante la confirmación de que la propuesta de una ruta que llega a todas las ciudades, no ir a cualquier ciudad de más de una vez, y tiene una longitud total bajo el requisito de obligado; etc. Todos estos, obviamente, se polinomio de tiempo para confirmar. 'Exponencial de solvencia" es realmente un rojo-arenque; lo que ocurre es que hay una evidente exponencial en tiempo de un algoritmo de tipo NP-completo los problemas (utilizar nuestro polinomio de comprobación en tiempo del algoritmo en cada uno de los exponencialmente-muchas posibilidades de solución de casos), pero la exponentiality no está realmente en el corazón de estos problemas; es simplemente una expresión de que el tamaño del espacio de búsqueda. Visto de esta manera, el P vs NP pregunta es " si podemos confirmar de manera eficiente una solución, podemos buscar de forma eficiente una solución?' - pero esto no tiene nada que ver con la exponencial problemas de tiempo y de sí mismo.

Answer 3

El NP problemas son aquellos para los que tenemos un (determinista) algoritmo para comprobar que una solución propuesta es realmente una solución. Por lo tanto, la cuestión de si una determinada expresión lógica es satisifiable es NP, ya que se puede verificar correctamente si una propuesta de verdad asignación es satisfactorio o no en el polinomio de tiempo. La cuestión de si un determinado vendedor mapa de viaje tiene una ruta visitando cada ciudad dentro de un plazo de presupuesto de viaje es NP, ya que podemos comprobar si cualquier ruta propuesta se ajusta a los requisitos en el polinomio de tiempo. La parte más difícil de un problema NP, más bien, es dar con la solución propuesta, para llegar a la satisfacción de la verdad cesión o eficiente de la ruta del viaje.

Estos problemas NP son todos de tiempo exponencial solución, porque el tonto algoritmo de probar todas las combinaciones posibles a su vez toma de tiempo exponencial. No-determinismo viene en la foto, porque uno puede ver el procedimiento de "adivinar la respuesta correcta" y, a continuación, comprobar como un algoritmo no determinista. Por lo tanto, NP problemas son aquellos que tienen un no-determinista polinomio de tiempo del algoritmo.