Cómo probar que$P \neq NP$

Question

Cómo probar que $P \neq NP$?

Para demostrar que $P = NP$ todo lo que tenemos que hacer es resolver uno de los NP-Completos problema en el polinomio de tiempo para cualquier entrada, y porque todos los NP-Completos, problemas de reducción de uno hacia el otro, podemos decir $P = NP$.

Lo sería si he de ser capaz de demostrar que uno de los NP-Completos, los problemas no pueden ser resueltos en el tiempo polinomio. Hay algún problema que ha demostrado ser en NP y no en P?

No he probado a cualquier problema que sólo pertenece a NP y no al revés, solo estoy preguntando en general.

Edit: Algunos que se indica:

Si usted puede probar que existía una NP-Completos, problema que no puede ser resuelto en P, entonces implicaría que $P \neq NP$

Quiero hacer un comentario acerca de ello aquí. Si usted tiene problema de $A$ que podría ser resuelto por el polinomio de reducción del problema $B$, se puede decir que el $A$ no es más difícil que $B$. Si usted será capaz de resolver los $B$ en el polinomio de tiempo, también se aplicará a $A$, es el más bajo de los límites. Si usted ser capaz de demostrar que $B$ no puede ser resuelto en el polinomio tiempo, del departamento de educación, no de demostrar que $A$ no puede ser resuelto en el polinomio de tiempo. Un buen ejemplo de esto es 2-sat problema que podría ser reducida a 3-sat. 2-sat ha polinomio solución, no hemos encontrado ningún polinomio solución de 3-sat todavía.

Answer 1

Lo sería si he de ser capaz de demostrar que uno de los NP-Completos, los problemas no pueden ser resueltos en el tiempo polinomio.

Supongo que te refieres a "los problemas no pueden ser resueltos en el polinomio tiempo en una máquina de Turing determinista". NP, después de todo, significa "polinomial no determinista", e incluye los problemas de decisión que pueden ser resueltos en el polinomio tiempo en una máquina de Turing no determinista.

Lo sería si he de ser capaz de demostrar que uno de los NP-Completos, los problemas no pueden ser resueltos en el polinomio de tiempo [en una máquina de Turing determinista].

A continuación, habría que demostrar que todas las $\rm NP\text{-}complete$ problemas no tienen determinista polinomio de tiempo de los algoritmos.

La prueba por contradicción:

1. Imaginemos que tenemos algún algoritmo, $A$, puede resolver algunos de los $\rm NP\text{-}complete$ problema, $S$.
2. Deje que nosotros llamamos "una de las $\rm NP\text{-}complete$ problemas" $R$.
3. En consecuencia, $R$ no puede ser resuelto en tiempo polinomio (determinista); porque tienen dado la prueba.
4. Ya que ambos son $\rm NP\text{-}complete$ problemas, entonces por el Cocinero reducciones, se puede reducir el $R\stackrel{...}{\rightarrow} S$ en el polinomio de tiempo (determinista).
5. Entonces podemos usar $A(S)$ y solucionar $S$. Esta es una contradicción a $(3)$.

Hay algún problema que ha demostrado ser en NP y no en P?

No estoy seguro de lo que usted está realmente tratando de preguntar aquí, pero aquí es un resumen de la complejidad de las clases.

$\rm \mathbf P$: es la clase de problemas de decisión que pueden ser resueltos en tiempo polinomio (determinista).

Hay varias formas equivalentes de mirar a $\rm NP$.

$\rm \mathbf{NP}$:

• es la clase de problemas de decisión que pueden ser resueltos en el polinomio tiempo en una máquina de Turing no determinista.
• es la clase de problemas de decisión para los cuales fácilmente se puede comprobar las soluciones de sus correspondientes problemas de optimización (que también son pruebas de la decisión).

Las dos explicaciones anteriores son intuitivamente equivalente: El no-determinismo de un NTM puede utilizar la verificabilidad de la respuesta a "probar todas las soluciones" y mantener sólo el que se verifica con éxito.

$\rm {NP}$ obviamente incluye a todos los de $\rm P$.

$\rm \mathbf{NP\text{-}complete}$: es la clase de problemas de decisión que son los más difíciles problemas en $\rm NP$. Estos problemas han reducciones de la otra -. De hecho, todos los de $\rm P$ $\rm NP$ puede ser reducido a ninguna $\rm NP\text{-}complete$ problema.

$\rm\mathbf{P}$ vs $\rm\mathbf{NP}$: es la pregunta acerca de si la $\rm NP\text{-}complete$ clase de problemas puede ser resuelto tan rápido como los problemas en $\rm P$; en otras palabras, ¿el no determinismo hacer una máquina de "más rápido" (en el sentido de polinomio de tiempo=rápido, superpolynomial tiempo=lento).

$\rm\mathbf{NP\text{-}hard}$: son el conjunto de problemas de decisión (algunas definiciones incluyen la búsqueda y optimización de problemas) que son al menos tan duro como $\rm NP\text{-}complete$ de los problemas. Así, todos los $\rm NP\text{-}complete$ también $\rm NP\text{-}hard$ de los problemas.

Una bonita imagen de la wikipedia:

Así que volviendo a tu pregunta:

Hay algún problema que ha demostrado ser en NP y no en P?

EDIT: para que quede claro, tengo entendido que esto significa:

Hay algún problema que ha demostrado ser en NP y [probado] no [] en P?

La respuesta es NO, porque eso implicaría $\rm P\ne NP$. La prueba por contradicción:

1. Imagine $\rm P=NP$
2. Imagine que hay un problema, $R$$\rm NP$, pero no en $\rm P$.
3. $\rm NP\text{-}complete$ problemas son los más difíciles en $\rm NP$ (todos los problemas en NP puede de hecho ser reducidos a cualquier $\rm NP\text{-}complete$ problema).
4. Todos los $\rm NP\text{-}complete$ problemas debe ser al menos tan duro como $R$, lo que sigue a partir de la $(2,3)$.
5. Todos los $\rm NP\text{-}complete$ problemas no están en $\rm P$ $R$ no $\rm P$, e $\rm NP\text{-}complete$ problemas hare más difícil de lo $R$ ( $(2,4)$ ). Por lo tanto,$\rm NP \not\in P$, lo $\rm P\ne NP$. Esto contradice $(1)$.

Answer 2

existe cierta confusión en la cuestión, demuestra una falta de algunos conocimientos básicos de la teoría de la NP integridad que está bien documentado en muchos lugares. particularmente en esta pregunta:

Hay algún problema que ha demostrado ser en NP?

sí, todos los NP completo de los problemas en NP. hay cientos, tal vez miles de NP completo de los problemas y variantes menores. véase, por ejemplo Garey/Johnson, Equipos Y Inflexibilidad, la teoría de la NP integridad

Cómo probar que P≠NP?

obviamente a nadie, incluso con el somero conocimiento en el área, esta es la Gran Pregunta Abierta que ha eludido a los investigadores durante más de cuatro décadas, la respuesta corta es que nadie sabe aún después de graves/intenso esfuerzo de líderes mundiales expertos. hay muchas ideas. un par de líderes:

• teoría de circuitos/complejidad. demostrar que los circuitos lógicos que calcular NP completo los problemas deben ser "intrínsecamente grandes". algunas éxito [es decir los límites inferiores] se ha logrado con los modelos más simples, por ejemplo la monotonía de los circuitos.
• GCT es una nueva idea usando la geometría de las ideas.
• descriptiva de la complejidad. relacionada con el poder de las pruebas. Fagins teorema muestra una correspondencia con los conjuntos P y una específica de la prueba del sistema.
• etc! muchos otros!

Answer 3

Si usted encuentra un algoritmo general que resuelve un problema NP-completo solo en tiempo Polinómico, entonces habrán probado efectivamente que $P=NP$.

Tenga en cuenta que resolver un caso de un problema específico no es suficiente, tienes que dar un algoritmo que soluciona todas las instancias del problema con los datos de entrada y demostrar que el algoritmo es polinomial en el tamaño de la entrada.

Answer 4

Si usted piensa acerca de esto por un minuto, usted verá que es exactamente igual de duro para demostrar que un determinado $NP$-completa el problema no puede ser resuelto en el polinomio tiempo como para demostrar que $P=NP$. A la carne que si $P=NP$, entonces por supuesto que no hay $NP$-completar los problemas que no pueden resolverse en el polinomio de tiempo. Por otro lado, si incluso hay un solo problema en $NP$ que no se encuentra en $P$, independientemente de si es $NP$-completar, a continuación,$P\neq NP$. (Aunque si no es un problema, debe existir un $NP$-completa.)

No entiendo muy bien lo que quieres decir por segunda pregunta, "¿qué pasa si encuentro un caso especial...?" En cuanto a la pregunta después de eso, hay un montón de problemas en los $NP:$ cualquier problema en $P$ cualquier $NP$-problema completo, etc...La pregunta interesante, que puede ser lo que usted está conduciendo, es si hay algún problema en los $NP$, pero no en $P$. Pero, como se describe en el párrafo anterior, si existiera, entonces el $P$ frente al $NP$ problema estaría resuelto.

Answer 5

Ya que has aceptado que mostrando un problema NP-completo solo a estar en P, implica que son todo en P.

Eso significa que si comprobar que algunos problema NP-completo (llamémosle A) no está en P, entonces ninguno de ellos puede ser. ¿Por qué? Porque si uno de los otros problemas era en P, entonces A que también. No es que lo sabemos.

También, puesto que P vs NP sigue siendo un problema abierto, significa que no hemos encontrado ningún problema en NP que no sabe están en P.