Cosa manca per questa prova P! = NP?

Question

Ho provato a recuperare una password. Quando ho pensato a questo, ho riconosciuto che il problema "recupero della password" è un esempio molto bello di un problema NP. Se conosci la password, è molto facile verificarla in tempo polinomiale. Ma se non conosci la password devi cercare l'intero spazio di possibili soluzioni che possono essere mostrati per richiedere tempo esponenziale.

Ora la mia domanda è: questo non dimostra che P! = NP poiché "Password Recovery" è un elemento di NP che può essere mostrato per richiedere più del tempo polinomiale da eseguire?

Answer 1

Il problema non mostra che il recupero della password non è polinomiale, poiché chiaramente lo è-devi cercare uno spazio esponenziale di risposte.

In realtà, "retrovery password" non è davvero una descrizione di uno standard problema computazionale. Sembra che, formalmente, gli algoritmi di rottura della password prendano una sorta di "Oracle" che può rispondere se una determinata stringa è la password corretta. Tuttavia, P e NP sono definiti in termini di macchine Turing, che prendono stringhe come input.

Answer 2

Se lo mostri qualunque L'algoritmo che risolve il "recupero della password" richiede più del tempo polinomiale, quindi dimostra che p ≠ np.

Altrimenti, se lo mostri solo una soluzione particolare Richiede più del tempo polinomiale, non dimostra nulla. Posso scrivere un tipo per richiedere tempo esponenziale (shuffle array fino a quando non è ordinato), ma ciò non significa che non ci sia soluzione polinomiale.

Answer 3

NP non significa "non poliinomi", se è quello che stavi pensando (e le mie scuse in anticipo se non lo facevi!). Significa "polinomio non deterministico". Un algoritmo non deterministico è uno che equivale a un numero illimitato di istanze parallele di un algoritmo. Ad esempio, trovare la password corretta di Brute Force è un polinomio non deterministico: se immagini che controlla la password, se la tua ipotesi sembra essere corretta, richiede tempo lineare (cioè polinomio) sulla lunghezza della password, ma che devi farlo Controlla un numero arbitrario di possibili password (k^n) in parallelo, quindi il costo di trovare la soluzione usando questo metodo è polinomio non deterministico.

Un algoritmo non deterministico può anche essere pensato a uno i cui rami statali su alcuni passi. Un semplice esempio di questo è un automobile finito non deterministico (NFA) - a volte non sai quale vantaggio prendere tra gli stati, quindi li prendi entrambi. È facile dimostrare che ogni NFA è equivalente a una FA deterministica, e quindi è allettante pensare che lo stesso possa essere dimostrato per altre interessanti classi di algoritmo. Sfortunatamente è difficile farlo per il caso generale dell'algoritmo polinomiale, e il sospetto generale è che non sono equivalenti, vale a dire che p! = Np.

Answer 4

Il ragionamento che il problema è in NP è corretto: se può essere verificato nel tempo polinomiale, è in NP. Anche problemi molto semplici sono in NP. Fondamentalmente, tutto P è incluso in NP. (*)

Ora, ecco un modo in cui potresti trasformarlo in una prova che p! = Np:

1) Mostra che il "recupero della password" è NP-completa. Cioè, qualsiasi problema in NP può essere ridotto a "Recupero della password" nel tempo polinomiale. (cioè esiste un algoritmo efficiente per convertire qualsiasi altro problema NP in "Recoverità password".)

2) Una volta che lo hai quindi, come menziona Pavel Shved, non è sufficiente dimostrare che l'algoritmo intuitivo non è polinomiale. Devi dimostrare che non esiste un algoritmo polinomiale per risolvere il "recupero della password". Un compito molto difficile.

(*) Edmund ha anche ragione: NP significa polinomio su una macchina non deterministica. Una verifica polinomiale è essenzialmente il percorso scelto dalla macchina non deterministica.

Answer 5

1. Come affermato, il "recupero della password" non è un problema decisionale.
2. Non hai dimostrato che il "recupero della password" non ha un algoritmo a tempo polinomiale, hai semplicemente discusso per motivi intuitivi che non lo fa. Solo perché uno spazio di soluzione è gigantesco non significa che non ci sono algoritmi veloci per trovare la soluzione; Ad esempio, ci sono n! Permutazioni di un insieme di n numeri interi distinti ma solo uno è ordinato ascendente, ma possiamo trovarlo in n log n volta. Per un esempio più divertente, vedi Project Euler #67.
3. Anche se hai riformulato il "recupero della password" come problema di decisione e sei stato in grado di dimostrare che non esiste un algoritmo a tempo polinomiale per risolverlo, ora devi dimostrare che il "recupero della password" è NP-completa.

Per i dettagli su P/NP/ecc. guarda questo domanda precedente.

Answer 6

La dichiarazione formale di questo problema sarebbe quella che accetta come input il valore hash (e sale) e tenta di trovare un Password che genererà quell'hash: il tuo problema di ricerca di collisione Cyphertext noto di base.

A seconda della qualità dell'hash, questo potrebbe no richiedono tempo esponenziale. In effetti, molti hash crittografici in uso diffuso hanno identificato attacchi che funzionano più velocemente delle ricerche di spazio di keys.

Vale a dire: tu (e alcuni degli altri soccorritori) presunto Che la routine di munging della password abbia tutte le proprietà che i progettisti volevano che avessero. Questo dovrebbe essere dimostrato.

Answer 7

Scrivere questa risposta perché ho avuto questa idea ad un certo punto e le risposte qui non erano soddisfacenti.

Hai dimostrato che p =/= np sotto la presenza di un "Oracle" (questa è la cosa che dice se la password è giusta o no).

È stato dimostrato che in realtà non è possibile dimostrare l'originale P vs NP usando Oracle (questa tecnica si chiama relativizzazione).

Per dimostrare il problema originale devi definire l'oracolo in termini di una macchina Turing. In altre parole, devi descrivere cosa fa il verificatore della password con l'input e quindi dimostrare che non esiste un algoritmo che possa indovinare la password data il codice verificatore della password.

Si noti che devi farlo per ogni possibile verificatore di password rapida. L'unico requisito dell'algoritmo del verificatore della password è che funziona in tempo polinomiale per quanto riguarda la lunghezza della password.

Quindi, dato qualsiasi possibile algoritmo che controlla se la password è giusta o meno in tempo polinomiale, devi scrivere un algoritmo che legge l'algoritmo verificatore e cerca di indovinare la password è in tempo polinomiale. Se puoi dimostrare o smorzare che tale algoritmo esiste, hai risolto il problema.