Debe un algoritmo que decide un problema en NP también producir una solución?

Question

Creo que tengo una incomprensión básica en la definición de un problema de decisión.

Es generalizada la opinión de que una prueba de que P=NP rompería toda la moderna criptografía, por ejemplo:-

• http://security.stackexchange.com/questions/12802/how-will-security-need-to-be-changed-if-p-np
• http://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/fulltext

No estoy seguro de entender por qué.

---

Por ejemplo, 3-SAT es NP-Completo. Así que si hemos tenido un algoritmo que podría decidir conste o unsatisfiable en el polinomio tiempo, podríamos probar que P=NP. La correcta?

Eso no significa que necesitamos un algoritmo que puede encontrar una solución que satisfaga a la entrada, la única que puede decidir si desea o no existe una solución, ¿correcto?

---

O, de manera equivalente, el uso de claves Diffie-Hellman exchange (citado de wikipedia porque no tengo suficiente rep de publicar más de 2 enlaces):-

• Alice y Bob están de acuerdo para utilizar un número primo p y base de g
• Alice elige un secreto entero de una, luego se envía a Bob A = g^un mod p
• Bob elige un secreto entero b, a continuación, envía a Alice B = g^b mod p
• Alice calcula s = B^un mod p
• Bob calcula s = A^b mod p
• Alice y Bob, ahora comparten s.

Claramente si Eva podría calcular a y b a partir de a y B, que sería problemático, pero una prueba de que P=NP sería sólo garantiza la existencia de un algoritmo que dados a, B, g, y p pueden decidir si o no a y b existen tales que A^b mod p = B^un mod p. Sería tan problemático?

---

Para expresar mi pregunta más general:-

• Debe un algoritmo que decide un problema en NP también ser capaz de construir una solución para ese problema que luego pueden ser verificados en el polinomio de tiempo?

• Sería un algoritmo que decide (pero no construir una "solución") NP-completos problema en el polinomio de tiempo será suficiente para demostrar que P=NP?

• Sería tal prueba tiene ningún impacto en la criptografía?

• O he entendido mal algo básico?

Answer 1

Si usted podría decidir SAT problemas en el polinomio tiempo, entonces también se puede encontrar una solución (para aquellos casos que disponen de ellos) en el polinomio de tiempo.
Es decir, si la expresión Booleana $A$ es válido y $x$ es una variable que aparece en $A$, elija una de las expresiones de $A|_{x=T}$ $A|_{x=F}$ (obtenido mediante el establecimiento $x$ a "true" o "false", respectivamente) que conste (al menos uno debe ser). Recurse hasta los trabajos de todas las variables se han encontrado.

Esto se extiende a todos los problemas en NP que pueden ser reducidos a un SAT de tal manera que una solución para el SAT problema genera (en el polinomio de tiempo) una solución para el problema original. La mayoría de los clásicos de los casos de NP-completitud son de este tipo.

En tu ejemplo, necesitamos generalizar un poco, desde el problema

Dado $A,B,g,p$, ¿ no existir $a,b$ ...

a

Dado $A,B,g,p$$a_0, b_0, n$, ¿no existir $a,b$ tal que $a \equiv a_0 \mod 2^n, b \equiv b_0 \mod 2^n$, y ...

Answer 2

Debe un algoritmo que decide un problema en NP también ser capaz de construir una solución para ese problema que luego pueden ser verificados en el polinomio de tiempo?

No, pero una solución puede ser fácilmente obtenidos mediante el procedimiento de la decisión de la NP problemas, porque todos los NP-completos son problemas de baja auto-reducible y todos los problemas NP se puede reducir a la NP-completo los problemas.

Sería un algoritmo que decide (pero no construir una "solución") NP-completos problema en el polinomio de tiempo será suficiente para demostrar que P=NP?

Sí. P y NP son las clases de problemas de decisión. Binarias (sí/no contesta es todo lo que se requiere para la toma de problemas. Gracias a la auto-reducibilidad un procedimiento de decisión es todo lo que se necesita para construir una solución así.

Sería tal prueba tiene ningún impacto en la criptografía?

Tal vez. Si el grado del polinomio de grado necesario para resolver problemas del tipo NP-completo de los problemas es grande en el peor de los casos, luego de descifrar convencionalmente cadenas cifradas todavía puede llegar a ser duro, no sólo de manera exponencial. Si el título es pequeña, de una sola vez almohadillas van a disfrutar de un renacimiento.

Answer 3

La existencia de funciones solo implica $\mathbf{P}\ne \mathbf{NP}$, por lo tanto, si $\mathbf{P} = \mathbf{NP}$, de una manera de la función no existe. A su vez, la seguridad de la mayoría de cifrado construcciones (generadores pseudoaleatorios, los esquemas de cifrado, ...) implica la existencia de una vía de funciones, por lo que no puede existir si la forma en que las funciones no existen.

Tenga en cuenta que la cuestión de la $\mathbf{P}$ vs $\mathbf{NP}$ pueden ser menos relevantes para la práctica de la criptografía de lo que usted piensa: si podemos invertir un solo sentido de la función en $p(n)$ tiempo pero el grado de $p$ es razonablemente grande, entonces la inversión seguirá siendo inviable en la práctica. Es, sin embargo, muy relevante a los fundamentos teóricos de cyptography, por lo que la criptografía en la práctica sería más sospechoso, incluso si no totalmente imposible. (Tal vez la NSA sabe un polinomio de grado menor...)