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

Question

Traté de recuperar una contraseña. Al pensar en esto, reconocí que el problema "recuperación de contraseña" es un muy 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 posibles soluciones que se puede demostrar que toman tiempo exponencial.

Ahora mi pregunta es: ¿No demuestra esto que P! = NP ya que la "recuperación de contraseña" es un elemento de NP que se puede demostrar que requiere más que tiempo polinómico para ejecutar?

Answer 1

El problema no muestra que la recuperación de contraseña no es polinomio, ya que claramente lo es: debe buscar un espacio exponencial de respuestas.

En realidad, la "contraseña de recuperación" no es realmente una descripción de un estándar problema computacional. Parece que, formalmente, los algoritmos de ruptura de contraseña toman algún tipo de "Oracle" que puede responder si una cadena determinada es la contraseña correcta. Sin embargo, P y Np se definen en términos de máquinas Turing, que toman cadenas como entrada.

Answer 2

Si muestras que ningún Algoritmo que resuelve "recuperación de contraseña" requiere más que tiempo polinomial, luego demuestra que p ≠ np.

De lo contrario, si solo muestra que una solución particular requiere más que tiempo polinomial, no demuestra nada. Puedo escribir un tipo para requerir tiempo exponencial (matriz de barras hasta que esté ordenada), pero eso no significa que no haya una solución polinomial.

Answer 3

NP no significa "no polinómico", 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 equivalente a un número ilimitado de instancias paralelas de un algoritmo. Como ejemplo, encontrar la contraseña correcta de la fuerza bruta es un polinomio no determinista: si imagina que verificar la contraseña, si su suposición es correcta, lleva tiempo lineal (es decir, polinomio) en la longitud de la contraseña, pero que necesita que debe Verifique un número arbitrario de contraseñas posibles (k^n) en paralelo, entonces el costo de encontrar la solución utilizando este método es polinomio no determinista.

Un algoritmo no determinista también puede considerarse uno cuyas ramas estatales en algunos pasos. Un ejemplo simple de esto es un autómata finito no determinista (NFA); a veces no sabes qué borde tomar entre los estados, por lo que los toma a ambos. Es fácil demostrar que cada NFA es equivalente a una FA determinista, por lo que es tentador pensar que podría probarse lo mismo para otras clases interesantes de algoritmo. Desafortunadamente, es difícil hacerlo para el caso general del algoritmo polinomial, y la sospecha general es que no son equivalentes, es decir, P! = NP.

Answer 4

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

Ahora, aquí hay una forma en que podría convertir esto en una prueba de que p! = Np:

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

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

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

Answer 5

1. Como se indicó, la "recuperación de contraseñas" no es un problema de decisión.
2. No ha demostrado que la "recuperación de contraseñas" no tenga un algoritmo de tiempo polinómico, simplemente ha argumentado por motivos intuitivos que no lo hace. 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 n! permutaciones de un conjunto de n enteros distintos pero solo uno se clasifica ascendiendo pero podemos encontrarlo en n log n tiempo. Para un ejemplo más divertido, ver Proyecto Euler #67.
3. Incluso si reformuló la "recuperación de contraseñas" como un problema de decisión y pudiera demostrar que no hay un algoritmo de tiempo polinómico para resolverlo, ahora debe demostrar que la "recuperación de contraseña" es NP-complete.

Para detalles sobre P/NP/etc. mira esto Pregunta anterior.

Answer 6

La declaración formal de este problema sería una que acepte como entrada el valor hash (y sal) e intenta encontrar a Contraseña que generará ese hash: su problema básico de búsqueda de colisión Cyphertext conocida.

Dependiendo de la calidad del hash, esto tal vez no requiere tiempo exponencial. De hecho, muchos hash criptográficos en uso generalizado han identificado ataques que funcionan más rápido que las búsquedas de espacio de teclado.

Es decir: usted (y algunos de los otros respondedores) tienen ficticio que la rutina de contraseña tiene todas las propiedades que los diseñadores querían que tenían. Esto tendría que ser demostrado.

Answer 7

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

Has demostrado que p =/= np bajo la presencia de un 'oráculo' (esto es lo que dice si la contraseña es correcta o no).

Se ha demostrado que en realidad no puede probar el P vs NP original mediante el uso de oráculos (esta técnica se llama relativización).

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

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

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