¿Cómo sabemos si un problema es más difícil en NP

Question

He leído que la definición de NP-completo es : Estos son los más difíciles problemas en NP. Un problema es NP-duro y en NP

¿Cómo podemos saber si un problema es más difícil en NP, y no es difícil problema existe. Entiendo que vamos a suponer que de alguna manera por arte de magia sabemos que un problema L es el más difícil en NP y, a continuación, podemos encontrar más problemas más difíciles H si podemos reducir H a L y viceversa.Pero mi pregunta es ¿cómo comenzar? ¿Cómo sabemos que 1 problema más duro para empezar?

También, para poder decir que algo es más difícil (o de cualquier extremo), necesitamos saber todos los posibles problemas en NP y, a continuación, discutir sobre el más difícil.. ¿Cómo sabemos que todos los posibles problemas NP? Es este, donde la máquina de turing viene útiles y mediante la representación de cadena de salida en forma de 1 y 0 en la salida de la cinta, podemos teóricamente hablar acerca de todos los posibles problemas NP.

Yo entiendo que yo no haya sido capaz de articular mi pregunta bien debido a la confusión.

Gracias,

Answer 1

Todo comenzó con el Cocinero-Levin teorema. La prueba de que utiliza la Máquina de Turing definición de NP y reduce todos los problemas en NP a SAT.

Cualquier libro de texto sobre Complejidad Computacional tendrá, al menos, una sección dedicada a esto. Yo recomendaría Papadimitrou, el libro de Complejidad Computacional para eso. He oído Sipser del libro es demasiado bueno, pero yo no he leído eso.

Así que para responder a tu pregunta, sí, se puede usar (y el teorema anterior en realidad no) la Máquina de Turing para hablar de todos los problemas en NP y probar la existencia de NP-Duro de problemas.

Answer 2

Si cada problema, $p$, en una complejidad de clase, $C$, puede ser reducido a otro problema $q$, $q$ se dice que ser Duro. (no es necesario que $q$ pertenecen a $C$)

Se puede concluir que si usted es capaz de resolver $q$, entonces usted puede resolver todos los problemas $p$ $C$ y por lo tanto debe ser más difícil la solución de cada problema $p$.

Si $q$ es Duro para $C$ $q$ pertenece a $C$, $q$ se dice que ser Completa.

Si $q$ es Completa, entonces significa que es uno de los más difíciles de resolver en $C$.