¿Qué falta para esta prueba de P! = NP?

Question

Intenté recuperar una contraseña. Al pensar en esto, reconocí que el problema de "recuperación de contraseñas" es un buen ejemplo de un problema NP. Si conoce la contraseña, es muy fácil verificarla en tiempo polinomial. PERO, si no conoce la contraseña, debe buscar todo el espacio de soluciones posibles que se puede demostrar que demoran exponencialmente.

Ahora mi pregunta es: ¿Esto no demuestra que P! = NP ya que la "recuperación de contraseñas" es un elemento de NP que se puede demostrar que requiere más tiempo que el polinomio para ejecutarse?

Answer 1

El problema no es que la recuperación de contraseñas no sea polinómica, ya que está claro que hay que buscar en un espacio exponencial de respuestas.

En realidad, "recuperación de contraseña" no es realmente una descripción de un estándar computational problem. Parece que, formalmente, los algoritmos de descifrado de contraseñas toman algún tipo de "oráculo" que puede responder si una cadena dada es la contraseña correcta. Sin embargo, P y NP se definen en términos de máquinas de Turing, que toman cadenas como entrada.

Answer 2

Si usted demuestra que cualquier algoritmo que resuelve "recuperación de la contraseña" requiere más tiempo polinómico, entonces sí demuestra que P ≠ NP.

De lo contrario, si solo muestra que requiere una solución en particular requiere más tiempo que el polinomio, no demuestra nada. Puedo escribir un género para requerir un tiempo exponencial (reorganizar la matriz hasta que esté ordenada), pero eso no significa que no haya una solución polinómica.

Answer 3

¿Se acaba de verificación pertenecen a la misma clase de problemas como búsqueda?

Answer 4

NP no significa "no polinomio", si eso es lo que estabas pensando (¡y mis disculpas de antemano si no lo fueras!). Significa "polinomio no determinista". Un algoritmo no determinista es aquel que es equivalente a un número ilimitado de instancias paralelas de un algoritmo. Como ejemplo, encontrar la contraseña correcta por fuerza bruta es un polinomio no determinista: si imagina que verificando la contraseña, si su suposición es correcta, toma tiempo lineal (es decir, polinomial) en la longitud de la contraseña, pero que necesita Verifique un número arbitrario de contraseñas posibles (k^n) en paralelo, luego el costo de encontrar la solución usando este método es un polinomio no determinista.

Un algoritmo no determinista también se puede considerar como uno cuyo estado se bifurca en algunos pasos. Un ejemplo simple de esto es un autómata finito no determinista (NFA): a veces no se sabe qué margen tomar entre los estados, por lo que se toman ambos. Es fácil mostrar que cada NFA es equivalente a un FA determinista, por lo que es tentador pensar que podría probarse lo mismo para otras clases de algoritmos interesantes. Desafortunadamente, es difícil hacerlo para el caso general del algoritmo polinómico, y la sospecha general es que no son equivalentes, es decir, que P! = NP.

Answer 5

El razonamiento de que el problema está en NP es correcto: si se puede verificar en tiempo polinomial, está en NP. Incluso los problemas más simples están en NP. Básicamente, todo P está incluido en NP. (*)

Ahora, aquí es una forma en que podría ir en convertir esto en una prueba de que P = NP:

1) Demostrar que "la recuperación de la contraseña" es NP-completo. Es decir, cualquier problema en NP puede reducirse a "recuperación de contraseña" en tiempo polinomial. (es decir, existe un algoritmo eficiente para convertir cualquier otro problema NP en "recuperación de contraseña").

2) Una vez que tenga eso, como lo menciona Pavel Shved, no es suficiente mostrar que el algoritmo intuitivo no es polinomio. Debes demostrar que no existe un algoritmo polinomial para resolver la "recuperación de contraseñas". Una tarea muy difícil.

(*) Edmund también tiene razón: NP significa polinomio en una máquina no determinista. Una verificación polinómica es esencialmente la ruta elegida por la máquina no determinista.

Answer 6

1. Como se indicó, la "recuperación de contraseña" no es un problema de decisión.
2. No ha probado que la "recuperación de contraseña" no tiene un algoritmo de tiempo polinomial, simplemente ha argumentado por motivos intuitivos que no es así. El hecho de que un espacio de solución sea gigantesco no significa que no haya algoritmos rápidos para encontrar la solución; por ejemplo, hay permutaciones n! de un conjunto de n enteros distintos, pero solo uno está ordenado de forma ascendente pero podemos encontrarlo en n log n time. Para un ejemplo más divertido, vea Project Euler #67.
3. Incluso si reformuló "recuperación de contraseña" como un problema de decisión y pudo demostrar que no hay un algoritmo de tiempo polinomial para resolverlo, ahora debe probar que la "recuperación de contraseña" es NP-completa.

Para detalles sobre P/NP/etc. vea esto previous question.

Answer 7

La declaración formal de este problema sería uno que acepta como entrada el valor hash (y sal) y los intentos de encontrar una contraseña que generará ese resumen: el problema básico búsqueda de texto cifrado conocido colisión.

Dependiendo de la calidad del hash, este podría no requerir tiempo exponencial. De hecho, muchos hash criptográficos de uso generalizado han identificado ataques que se ejecutan más rápido que las búsquedas en el espacio de claves.

Cuál es decir: usted (y algunos de los otros respondedores) tienen asumió que la rutina que munging de la contraseña tiene todas las características que los diseñadores quisieron tener. Esto debería ser probado.

Answer 8

Escribo esta respuesta porque tuve esta idea en algún momento, y las respuestas aquí no fueron satisfactorias.

Ha demostrado que P =/= NP bajo la presencia de un 'Oracle' (esto es lo que dice si la contraseña es correcta o no).

Se ha demostrado que no se puede probar el P original frente a NP usando Oracles (esta técnica se denomina relativización).

Para demostrar el problema original, debe definir Oracle en términos de una máquina de turing. En otras palabras, debe describir lo que hace el verificador de contraseñas con la entrada, y luego probar que no existe un algoritmo que pueda adivinar la contraseña dado el código del verificador de contraseñas.

Tenga en cuenta que debe hacer esto para cualquier posible verificador rápido de contraseñas. El único requisito del algoritmo del verificador de contraseñas es que se ejecute en tiempo polinomial con respecto a la longitud de la contraseña.

Por lo tanto, dado cualquier posible algoritmo que compruebe si la contraseña es correcta o no en tiempo polinomial, debe escribir un algoritmo que lea el algoritmo verificador e intente adivinar que la contraseña está en tiempo polinomial. Si puede probar o refutar que existe ese algoritmo, entonces ha resuelto el problema.