Che cos'è "P = NP?", E perché è una domanda così famosa? [chiuso]

Question

La domanda se P = NP sia forse il più famoso in tutta l'Informatica. Cosa significa? E perché è così interessante?

Oh, e per ulteriore credito, si prega di pubblicare una prova della verità o della falsità della dichiarazione. :)

Answer 1

P sta per tempo polinomiale. NP sta per tempo polinomiale non deterministico.

Definizioni:

• Tempo polinomiale indica che la complessità dell'algoritmo è O (n ^ k), dove n è la dimensione dei dati (ad esempio il numero di elementi in un elenco da ordinare) e k è una costante.

• Complessità è il tempo misurato nel numero di operazioni che sarebbe necessario, in funzione del numero di elementi di dati.

• Operazione è ciò che ha senso come un'operazione di base per un determinato compito. Per l'ordinamento dell'operazione di base è un confronto. Per la moltiplicazione matriciale l'operazione di base è la moltiplicazione di due numeri.

Ora la domanda è: cosa significa deterministico vs. non deterministico. Esiste un modello computazionale astratto, un computer immaginario chiamato una macchina di Turing (TM). Questa macchina ha un numero finito di stati e un nastro infinito, che ha celle discrete in cui è possibile scrivere e leggere un insieme finito di simboli. In qualsiasi momento, la TM si trova in uno dei suoi stati e sta guardando una cella particolare sul nastro. A seconda di ciò che legge da quella cella, può scrivere un nuovo simbolo in quella cella, spostare il nastro di una cella in avanti o indietro e passare a uno stato diverso. Questa è chiamata transizione di stato. Abbastanza sorprendentemente, costruendo accuratamente stati e transizioni, è possibile progettare una TM, che equivale a qualsiasi programma per computer che può essere scritto. Questo è il motivo per cui viene utilizzato come modello teorico per dimostrare cose su ciò che i computer possono e non possono fare.

Ci sono due tipi di TM che ci riguardano qui: deterministici e non deterministici. Una TM deterministica ha solo una transizione da ciascuno stato per ogni simbolo che sta leggendo dal nastro. Una TM non deterministica può avere diverse di queste transizioni, i. e. è in grado di verificare più possibilità contemporaneamente. È un po 'come generare più thread. La differenza è che una TM non deterministica può generare altrettante "discussioni". come vuole, mentre su un vero computer è possibile eseguire solo un numero specifico di thread alla volta (pari al numero di CPU). In realtà, i computer sono sostanzialmente TM deterministici con nastri finiti. D'altra parte, una TM non deterministica non può essere realizzata fisicamente, tranne forse con un computer quantistico.

È stato dimostrato che qualsiasi problema che può essere risolto da una TM non deterministica può essere risolto da una TM deterministica. Tuttavia, non è chiaro quanto tempo ci vorrà. L'affermazione P = NP significa che se un problema impiega tempo polinomiale su una TM non deterministica, allora si può costruire una TM deterministica che risolva lo stesso problema anche in tempo polinomiale. Finora nessuno è stato in grado di dimostrare che si può fare, ma nessuno è stato in grado di dimostrare che neanche questo può essere fatto.

Problema NP-completo significa un problema NP X, tale che qualsiasi problema NP Y può essere ridotto a X mediante una riduzione polinomiale. Ciò implica che se qualcuno dovesse mai trovare una soluzione in tempo polinomiale a un problema NP completo, ciò darebbe anche una soluzione in tempo polinomiale a qualsiasi problema NP. Quindi ciò proverebbe che P = NP. Al contrario, se qualcuno dovesse dimostrare che P! = NP, allora saremmo certi che non c'è modo di risolvere un problema NP in tempo polinomiale su un computer convenzionale.

Un esempio di un problema NP-completo è il problema di trovare un'assegnazione di verità che renderebbe vera un'espressione booleana contenente n variabili.
Per il momento in pratica qualsiasi problema che richiede tempo polinomiale sulla TM non deterministica può essere fatto solo in tempo esponenziale su una TM deterministica o su un computer convenzionale.
Ad esempio, l'unico modo per risolvere il problema di assegnazione della verità è provare 2 ^ n possibilità.

Answer 2

1. Un problema sì o no si trova in P ( P tempo olinomiale) se la risposta può essere calcolata in tempo polinomiale.
2. Un problema sì-no-no si trova in NP ( N tempo olinomiale P on-deterministico) se una risposta sì può essere < em> verificato in tempo polinomiale.

Intuitivamente, possiamo vedere che se un problema si trova in P , allora è in NP . Data una potenziale risposta per un problema in P , possiamo verificare la risposta semplicemente ricalcolando la risposta.

Meno ovvio e molto più difficile rispondere è se tutti i problemi in NP sono in P . Il fatto che possiamo verificare una risposta in tempo polinomiale significa che possiamo calcolare quella risposta in tempo polinomiale?

Esistono molti problemi importanti noti per essere NP completi (in pratica, se si verifica che questi problemi si trovano in P , quindi tutti i problemi NP sono stati riscontrati in P ). Se P = NP , tutti questi problemi avranno una soluzione efficiente (tempo polinomiale).

La maggior parte degli scienziati ritiene che P ! = NP . Tuttavia, non è stata ancora stabilita alcuna prova per P = NP o P ! = NP . Se qualcuno fornisce una prova per entrambe le congetture, vinceranno $ 1 milione .

Answer 3

Per dare la risposta più semplice mi viene in mente:

Supponiamo di avere un problema che richiede un certo numero di input e che presenta varie soluzioni potenziali, che possono o meno risolvere il problema per determinati input. Un puzzle di logica in una rivista di puzzle sarebbe un buon esempio: gli input sono le condizioni ("George non vive nella casa blu o verde") e la potenziale soluzione è un elenco di affermazioni ("George vive in la casa gialla, coltiva i piselli e possiede il cane "). Un esempio famoso è il problema del commesso viaggiatore: dato un elenco di città e i tempi per passare da una città a un'altra, e un limite di tempo, una potenziale soluzione sarebbe un elenco di città nell'ordine in cui il venditore le visita, e funzionerebbe se la somma dei tempi di viaggio fosse inferiore al limite di tempo.

Un simile problema si presenta in NP se possiamo controllare in modo efficiente una potenziale soluzione per vedere se funziona. Ad esempio, dato un elenco di città che il venditore deve visitare in ordine, possiamo sommare i tempi per ogni viaggio tra le città e vedere facilmente se è inferiore al limite di tempo. Un problema è in P se riusciamo a trovare in modo efficiente una soluzione se esiste.

(Qui, efficacemente, ha un preciso significato matematico. In pratica, significa che i grandi problemi non sono irragionevolmente difficili da risolvere. Quando si cerca una possibile soluzione, un modo inefficiente sarebbe di elencare tutte le possibili soluzioni potenziali, o qualcosa del genere vicino a ciò, mentre un modo efficiente richiederebbe una ricerca di un set molto più limitato.)

Pertanto, il problema P = NP può essere espresso in questo modo: se riesci a verificare una soluzione per un problema del tipo sopra descritto in modo efficiente, puoi trovare una soluzione (o dimostrare che non ce ne è) in modo efficiente? La risposta ovvia è "Perché dovresti essere in grado di?", Ed è praticamente lì che si trova la questione oggi. Nessuno è stato in grado di dimostrarlo in un modo o nell'altro, e questo disturba molti matematici e scienziati informatici. Ecco perché chiunque sia in grado di provare la soluzione è in palio per un milione di dollari dalla Fondazione Claypool.

In genere supponiamo che P non sia uguale a NP, che non esiste un modo generale per trovare soluzioni. Se risultasse che P = NP, molte cose cambieranno. Ad esempio, la crittografia diventerebbe impossibile e con essa qualsiasi tipo di privacy o verificabilità su Internet. Dopotutto, possiamo prendere in modo efficiente il testo crittografato e la chiave e produrre il testo originale, quindi se P = NP potremmo trovare in modo efficiente la chiave senza conoscerla in anticipo. Il crack delle password diventerebbe banale. D'altra parte, ci sono intere classi di problemi di pianificazione e problemi di allocazione delle risorse che potremmo risolvere in modo efficace.

Potresti aver sentito la descrizione NP-complete. Un problema NP-completo è NP (ovviamente) e ha questa proprietà interessante: se è in P, ogni problema NP è, e quindi P = NP. Se riuscissi a trovare un modo per risolvere in modo efficiente il problema del commesso viaggiatore o puzzle logici da riviste di puzzle, potresti risolvere in modo efficiente qualsiasi cosa in NP. Un problema NP completo è, in un certo senso, il tipo più difficile di problema NP.

Quindi, se riesci a trovare una tecnica di soluzione generale efficiente per qualsiasi problema NP-completo, o prova che non esiste, fama e fortuna sono le tue.

Answer 4

Un breve riassunto delle mie umili conoscenze:

Esistono alcuni problemi computazionali facili (come trovare il percorso più breve tra due punti in un grafico), che possono essere calcolati abbastanza velocemente (O (n ^ k), dove n è la dimensione dell'input e k è una costante (nel caso dei grafici, è il numero di vertici o spigoli)).

Altri problemi, come trovare un percorso che attraversa tutti i vertici in un grafico o ottenere la chiave privata RSA dalla chiave pubblica è più difficile (O (e ^ n)).

Ma CS speak dice che il problema è che non possiamo "convertire" una macchina di Turing non deterministica in una deterministica, tuttavia possiamo trasformare automi finiti non deterministici (come il parser regex) in quelli deterministici ( bene, puoi, ma il tempo di esecuzione della macchina richiederà molto tempo). Cioè, dobbiamo provare ogni possibile percorso (di solito i professori CS intelligenti possono escluderne alcuni).

È interessante perché nessuno ha nemmeno idea della soluzione. Alcuni dicono che è vero, alcuni dicono che è falso, ma non c'è consenso. Un'altra cosa interessante è che una soluzione sarebbe dannosa per le crittografie di chiavi pubbliche / private (come RSA). Potresti romperli facilmente come lo è ora generare una chiave RSA.

Ed è un problema piuttosto stimolante.

Answer 5

Non c'è molto che io possa aggiungere alla cosa cosa e perché della parte P =? NP della domanda, ma per quanto riguarda la prova. Non solo una prova meriterebbe un po 'di credito extra, ma risolverebbe uno dei Problemi del millennio . Recentemente è stato condotto un sondaggio interessante e i risultati pubblicati (PDF) vale sicuramente la pena leggere riguardo all'argomento di una prova.

Answer 6

Innanzitutto, alcune definizioni:

• Un particolare problema è in P se è possibile calcolare una soluzione in tempo inferiore a n ^ k per alcuni k , dove n è la dimensione dell'input. Ad esempio, l'ordinamento può essere eseguito in n log n che è inferiore a n ^ 2 , quindi l'ordinamento è tempo polinomiale.

• In NP esiste un problema se esiste un k tale che esiste al massimo una soluzione di dimensioni n ^ k che è possibile verificare in tempo a la maggior parte di n ^ k . Prendi una 3 colorazione dei grafici: dato un grafico, una 3 colorazione è un elenco di coppie (vertice, colore) che ha dimensione O (n) e puoi verificare in tempo O ( m) (o O (n ^ 2) ) se tutti i vicini hanno colori diversi. Quindi un grafico è a 3 colori solo se esiste una soluzione breve e facilmente verificabile.

Una definizione equivalente di NP è "problemi risolvibili da una macchina di Turing non deterministica N in P tempo olinomiale". Mentre questo ti dice da dove viene il nome, non ti dà la stessa sensazione intuitiva di come sono i problemi NP.

Nota che P è un sottoinsieme di NP: se riesci a trovare una soluzione in tempo polinomiale, c'è una soluzione che può essere verificata in tempo polinomiale - controlla che la soluzione data sia uguale a quella che puoi trovare.

Perché la domanda P =? NP interessante? Per rispondere a ciò, bisogna prima vedere quali sono i problemi NP-completi. In parole povere,

• Un problema L è NP completo se (1) L è in P, e (2) un algoritmo che risolve L può essere usato per risolvere qualsiasi problema L 'in NP; cioè, data un'istanza di L 'è possibile creare un'istanza di L che ha una soluzione se e solo se l'istanza di L' ha una soluzione. Formalmente parlando, ogni problema L 'in NP è riducibile a L.

Notare che l'istanza di L deve essere calcolabile a tempo polinomiale e avere dimensioni polinomiali, nella dimensione di L '; in questo modo, risolvere un problema NP completo in tempo polinomiale ci offre una soluzione temporale polinomiale per tutti problemi NP.

Ecco un esempio: supponiamo di sapere che la 3-colorazione dei grafici è un problema NP-difficile. Vogliamo dimostrare che anche la decisione sull'affidabilità delle formule booleane è un problema difficile per NP.

Per ogni vertice v, hanno due variabili booleane v_h e v_l e il requisito (v_h o v_l): ogni coppia può avere solo i valori {01, 10, 11}, che possiamo pensare come colore 1, 2 e 3.

Per ogni fronte (u, v), è necessario che (u_h, u_l)! = (v_h, v_l). Cioè,

  

not ((u_h e non u_l) e (v_h e non v_l) o ...)   enumerando tutte le configurazioni uguali e stipulando che nessuno dei due è il caso.

AND 'riunendo tutti questi vincoli fornisce una formula booleana che ha dimensioni polinomiali ( O (n + m) ). Puoi anche verificare che ci vuole del tempo polinomiale per calcolare: stai facendo cose semplici O (1) per vertice e per bordo.

Se riesci a risolvere la formula booleana che ho creato, puoi anche risolvere la colorazione del grafico: per ogni coppia di variabili v_h e v_l, lascia che il colore di v sia quello corrispondente ai valori di quelle variabili. Con la costruzione della formula, i vicini non avranno gli stessi colori.

Quindi, se la 3 colorazione dei grafici è NP-completa, lo è anche la soddisfazione della formula booleana.

Sappiamo che la 3-colorazione dei grafici è NP-completa; tuttavia, storicamente abbiamo imparato che mostrando prima la completezza NP della soddisfacibilità del circuito booleano e poi riducendola a 3 colorabilità (invece del contrario).