Cercando di capire P vs NP vs NP Complete vs NP Hard

La prima cosa da capire è che P e NP classificano le lingue, non i problemi. Per capire cosa significa, abbiamo bisogno prima di altre definizioni.

Un alfabeto è un insieme finito non vuoto di simboli.

{01} è un alfabeto così come il set di caratteri ASCII. {} non è un alfabeto perché è vuoto. N (gli interi) non è un alfabeto perché non è finito.

Sia Σ un alfabeto. Una concatenazione ordinata di un numero finito di simboli da Σ è chiamata parola su Σ.

La stringa101è una parola sopra l’alfabeto {01}. La parola vuota (spesso scritta come ε) è una parola sopra qualsiasi alfabeto. La stringa penguin è una parola sopra l’alfabeto contenente i caratteri ASCII. La notazione decimale del numero π, non è una parola sopra l’alfabeto {.0123456789} perché non è finita.

La lunghezza di una parola w, scritta come| w/, è il numero di simboli in essa contenuti.

Ad esempio,/hello | = 5 e| ε / = 0. Per qualsiasi parola w, / w / N N e quindi finito.

Sia Σ un alfabeto. L’insieme Σ contains contiene tutte le parole su Σ, incluso ε. L’insieme Σ + contiene tutte le parole su Σ, escluso ε. Per n N N, Σn è l’insieme di parole di lunghezza n.

Per ogni alfabeto Σ, Σ id e Σ+ sono insiemi numerabili infiniti. Per il set di caratteri ASCII ΣASCII, le espressioni regolari .*e.+ denotano rispettivamente ΣASCII respectively e ΣASCII+.

{01}7 è l’insieme di codici ASCII a 7 bit {00000000000001111111101}32 è l’insieme di valori interi a 32 bit.

Sia Σ un alfabeto e L & subseteq; Σ＊. L è chiamato un linguaggio su Σ.

Per un alfabeto Σ, l’insieme vuoto e Σ＊ sono linguaggi banali su Σ. Il primo è spesso indicato come la lingua vuota. La lingua vuota {} e la lingua contenente solo la parola vuota {ε} sono diverse.

Il sottoinsieme di {01} 32 che corrisponde a valori in virgola mobile IEEE 754 non NaN è un linguaggio finito.

Le lingue possono avere un numero infinito di parole ma ogni lingua è numerabile. The set of strings {12, …} denoting the integers in decimal notation is an infinite language over the alphabet {0123456789}. L’infinita serie di stringhe {23571113, …} che indica il primo dei numeri in notazione decimale è un sottoinsieme proprio di esso. Il linguaggio contenente tutte le parole corrispondenti all’espressione regolare ?\d+\.\d*(?\d+)? è un linguaggio sopra il set di caratteri ASCII (che denota un sottoinsieme delle espressioni in virgola mobile valide come definite dal linguaggio di programmazione C).

Non esiste una lingua contenente tutti i numeri reali (in qualsiasi notazione) perché l’insieme di numeri reali non è numerabile.

Sia Σ un alfabeto e L & subseteq; Σ＊. Una macchina D decide L se per ogni ingresso w & in; Σ comp calcola la funzione caratteristica xL (w) in tempo finito. La funzione caratteristica è definita come

χL: Σ＊ → {0, 1} w ↦ 1, w ∈ L 0, otherwise.

Tale macchina è chiamata un decisore per L. Scriviamo “D(w) = x” per “dato w, D uscite x”.

Ci sono molti modelli di macchine. Il più generale che è in uso pratico oggi è il modello di una macchina di Turing. Una macchina di Turing ha un accumulo lineare illimitato raggruppato in celle. Ogni cella può contenere esattamente un simbolo di un alfabeto in qualsiasi momento. La macchina di Turing esegue il suo calcolo come una sequenza di passi di calcolo. In ogni passaggio, può leggere una cella, eventualmente sovrascriverne il valore e spostare la testina di lettura/scrittura di una posizione nella cella sinistra o destra. L’azione che la macchina eseguirà è controllata da un automa a stati finiti.

Una macchina ad accesso casuale con un insieme finito di istruzioni e storage illimitato è un altro modello di macchina che è potente come il modello di macchina di Turing.

Per il bene di questa discussione, non ci disturberemo con il modello preciso della macchina che usiamo, ma piuttosto basti dire che la macchina ha un’unità di controllo deterministica finita, una memoria illimitata ed esegue un calcolo come una sequenza di passi che possono essere contati.

Dal momento che l’hai usato nella tua domanda, presumo che tu abbia già familiarità con la notazione “big-O”, quindi ecco solo un rapido aggiornamento.

Sia f: N → una funzione. L’insieme O(f) contiene tutte le funzioni g: N → N per le quali esistono costanti n0 N N e c c N tali che per ogni n with N con n > n0 è vero che g(n) ≤ c f(n).

Ora siamo pronti ad affrontare la vera domanda.

La classe P contiene tutti i linguaggi L per i quali esiste una macchina di Turing D che decide L e una costante k N N tale che per ogni input w, D si arresta al massimo dopo T (|w/) passi per una funzione T O O(n n nk).

Poiché O(n n nk), mentre matematicamente corretto, è scomodo da scrivere e leggere, la maggior parte delle persone – ad essere onesti, tutti tranne me stesso – di solito scrive semplicemente O(nk).

Si noti che il limite dipende dalla lunghezza di w. Pertanto, l’argomento che si crea per il linguaggio dei numeri primi è corretto solo per i numeri nelle codifiche unaray, dove per la codifica w di un numero n, la lunghezza della codifica |w| è proporzionale a n. Nessuno userebbe mai una tale codifica in pratica. Usando un algoritmo più avanzato rispetto al semplice tentativo di tutti i possibili fattori, si può dimostrare, tuttavia, che il linguaggio dei numeri primi rimane in P se gli input sono codificati in binario (o in qualsiasi altra base). (Nonostante enorme interesse, questo potrebbe essere dimostrato solo da Manindra Agrawal, Neeraj Kayal, e Nitin Saxena in un documento premiato nel 2004 in modo da poter intuire che l’algoritmo non è molto semplice.)

I linguaggi banali {} e Σ＊ e il linguaggio non banale {ε} sono ovviamente in P (per qualsiasi alfabeto Σ). Puoi scrivere funzioni nel tuo linguaggio di programmazione preferito che prendono una stringa come input e restituiscono un booleano che dice se la stringa è una parola dalla lingua per ognuna di queste e dimostrare che la tua funzione ha complessità polinomiale in fase di esecuzione?

Ogni lingua normale (una lingua descritta da un’espressione regolare) è in P.

Sia Σ un alfabeto e L& subseteq; Σ＊. Una macchina V che prende una tupla codificata di due parole w, c Σ Σ outputs e emette 0 o 1 dopo un numero finito di passaggi è un verificatore per L se ha le seguenti proprietà.

• Dato (w, c), V emette 1 solo se w L L.
• Per ogni w L L, esiste un c Σ Σ such tale che V(w, c) = 1.

Il c nella definizione di cui sopra è chiamato un testimone (o certificato).

Un verificatore è autorizzato a fornire falsi negativi per il testimone sbagliato anche se w è effettivamente in L. Tuttavia, non è consentito fornire falsi positivi. È anche necessario che per ogni parola nella lingua esista almeno un testimone.

Per il linguaggio COMPOSITO, che contiene le codifiche decimali di tutti gli interi che non sono primi, un testimone potrebbe essere una fattorizzazione. Ad esempio, (659, 709) è un testimone per 467231 COMPOSITE COMPOSITE. Si può facilmente verificare che su un foglio di carta, mentre senza il testimone dato, dimostrando che 467231 non è primo sarebbe difficile senza l’utilizzo di un computer.

Non abbiamo detto nulla su come trovare un testimone appropriato. Questa è la parte non deterministica.

La classe NP contiene tutti i linguaggi L per i quali esiste una macchina di Turing V che verifica L e una costante k N N tale che per ogni input (w, c), V si arresta al massimo dopo T (|w/) passaggi per una funzione T O O(n n nk).

Si noti che la definizione precedente implica che per ogni w L L esiste un testimone c con| c| ≤ T (|w/). (La macchina di Turing non può guardare più simboli del testimone.)

NP è un superset di P (perché?). Non è noto se esistano linguaggi che sono in NP ma non in P.

La fattorizzazione intera non è un linguaggio di per sé. Tuttavia, possiamo costruire un linguaggio che rappresenta il problema decisionale ad esso associato. Cioè, un linguaggio che contiene tutte le tuple (n, m) in modo tale che n abbia un fattore d con d ≤ m. Chiamiamo questo FATTORE di linguaggio. Se si dispone di un algoritmo per decidere il FATTORE, può essere utilizzato per calcolare una fattorizzazione completa con solo overhead polinomiale eseguendo una ricerca binaria ricorsiva per ciascun fattore primo.

È facile mostrare che il FATTORE è in NP. Un testimone appropriato sarebbe semplicemente il fattore d stesso e tutto ciò che il verificatore dovrebbe fare è verificare che d ≤ m e n mod d = 0. Tutto questo può essere fatto in tempo polinomiale. (Ricorda, ancora una volta, che è la lunghezza della codifica che conta e che è logaritmica in n.)

Se puoi mostrare che il FATTORE è anche in P, puoi essere sicuro di ottenere molti fantastici premi. (E hai rotto una parte significativa della crittografia di oggi.)

Per ogni linguaggio in NP, esiste un algoritmo di forza bruta che lo decide in modo deterministico. Esegue semplicemente una ricerca esaustiva su tutti i testimoni. (Si noti che la lunghezza massima di un testimone è delimitata da un polinomio.) Quindi, il tuo algoritmo per decidere i numeri PRIMI era in realtà un algoritmo di forza bruta per decidere il COMPOSITO.

Per affrontare la tua ultima domanda, dobbiamo introdurre la riduzione. Le riduzioni sono un concetto molto potente di informatica teorica. Ridurre un problema ad un altro significa fondamentalmente risolvere un problema per mezzo di risolvere un altro problema.

Sia Σ un alfabeto e A e B lingue su Σ. A è il tempo polinomiale many-one riducibile a B se esiste una funzione f: Σ → → Σ properties con le seguenti proprietà.

• w A A f f(w) B B per tutti i w Σ Σ..
• La funzione f può essere calcolata da una macchina di Turing per ogni input w in un numero di passaggi delimitati da un polinomio in |w|.

In questo caso, scriviamo un ≤p B.

Ad esempio, sia A il linguaggio che contiene tutti i grafici (codificati come matrice di adiacenza) che contengono un triangolo. (Un triangolo è un ciclo di lunghezza 3.) Sia ulteriormente B il linguaggio che contiene tutte le matrici con traccia diversa da zero. (La traccia di una matrice è la somma dei suoi principali elementi diagonali.) Quindi A è il tempo polinomiale many-one riducibile a B. Per dimostrarlo, dobbiamo trovare una funzione di trasformazione appropriata f. In questo caso, possiamo impostare f per calcolare la terza potenza della matrice di adiacenza. Ciò richiede due prodotti matrice-matrice, ognuno dei quali ha complessità polinomiale.

È banalmente vero che L ≤p L. (Puoi dimostrarlo formalmente?)

Applicheremo questo a NP ora.

Una lingua L è NP-difficile se e solo se L’ ≤p L per ogni lingua L’ NP NP.

Un linguaggio NP-difficile può o non può essere in NP stesso.

Un linguaggio L è NP-completo se e solo se

• L NP NP e
• L è NP-difficile.

Il linguaggio NP-completo più famoso è SAT. Contiene tutte le formule booleane che possono essere soddisfatte. Ad esempio, (a b b) SAT (a b b) SAT SAT. Un testimone valido è {a = 1, b = 0}. La formula (a b b) SAT (a b b) SAT b SAT SAT. (Come lo dimostreresti?)

Non è difficile mostrare che SAT NP NP. Per mostrare la NP-durezza di SAT è un lavoro, ma è stato fatto nel 1971 da Stephen Cook.

Una volta che un linguaggio NP-completo era noto, era relativamente semplice mostrare la NP-completezza di altri linguaggi tramite riduzione. Se il linguaggio A è noto per essere NP-hard, allora mostrare che A ≤p B mostra che anche B è NP-hard (tramite la transitività di “≤p”). Nel 1972 Richard Karp pubblicò un elenco di 21 lingue che poteva mostrare come NP-complete attraverso la riduzione (transitiva) di SAT. (Questo è l’unico documento in questa risposta che in realtà ti consiglio di leggere. A differenza degli altri, non è difficile da capire e dà un’idea molto buona di come funziona la dimostrazione della NP-completezza tramite la riduzione.)

Infine, un breve riassunto. Useremo i simboli NPH e NPC per indicare rispettivamente le classi di linguaggi NP-hard e NP-complete.

• P&sottoinsieme q; NP
• NPC & sottoinsieme; NP e NPC &sottoinsieme; NPH, in realtà NPC = NP ∩ NPH per definizione
• (A ∈ NP) ∧ (B ∈ NPH) ⇒ A ≤p B

si noti che l’inclusione NPC &sottoinsieme; NP è corretta anche nel caso che P = NP. Per vedere questo, chiarisci che nessun linguaggio non banale può essere ridotto a uno banale e ci sono linguaggi banali in P e linguaggi non banali in NP. Questo è un caso d’angolo (non molto interessante), però.

La tua fonte primaria di confusione sembra essere che stavi pensando a “n” in “O(n f f(n))” come l’interpretazione dell’input di un algoritmo quando si riferisce effettivamente alla lunghezza dell’input. Questa è una distinzione importante perché significa che la complessità asintotica di un algoritmo dipende dalla codifica utilizzata per l’input.

Questa settimana è stato raggiunto un nuovo record per il più grande Mersenne prime conosciuto. Il più grande numero primo attualmente noto è 274 207 281 − 1. Questo numero è così grande che mi dà un mal di testa quindi userò uno più piccolo nel seguente esempio: 231 – 1 = 2 147 483 647. Può essere codificato in modi diversi.

• dal suo Mersenne esponente come numero decimale: 31 (2 byte)
• come numero decimale: 2147483647 (10 byte)
• come unario numero: 11111…11 dove … viene sostituita da 2 147 483 640 di più 1s (quasi 2 GiB)

Tutte queste stringhe codificate lo stesso numero e data una qualsiasi di questi, si può facilmente costruire una qualsiasi altra codifica dello stesso numero. (È possibile sostituire la codifica decimale con binario, ottale o esadecimale se lo si desidera. Cambia solo la lunghezza di un fattore costante.)

L’algoritmo ingenuo per testare la primalità è solo polinomiale per codifiche unarie. Il test di primalità AKS è polinomiale per decimale (o qualsiasi altra base b ≥ 2). Il test di primalità di Lucas-Lehmer è l’algoritmo più noto per i primi di Mersenne Mp con p un primo dispari, ma è ancora esponenziale nella lunghezza della codifica binaria dell’esponente di Mersenne p (polinomio in p).

Se vogliamo parlare della complessità di un algoritmo, è molto importante che siamo molto chiari su quale rappresentazione usiamo. In generale, si può supporre che venga utilizzata la codifica più efficiente. Cioè, binario per interi. (Si noti che non tutti i numeri primi sono un primo di Mersenne, quindi l’uso dell’esponente di Mersenne non è uno schema di codifica generale.)

Nella crittografia teorica, a molti algoritmi viene formalmente passata una stringa completamente inutile di k 1s come primo parametro. L’algoritmo non guarda mai questo parametro ma gli consente di essere formalmente polinomiale in k, che è il parametro di sicurezza utilizzato per ottimizzare la sicurezza della procedura.

Per alcuni problemi per i quali il linguaggio decisionale nella codifica binaria è NP-completo, il linguaggio decisionale non è più NP-completo se la codifica dei numeri incorporati viene commutata in unario. I linguaggi decisionali per altri problemi rimangono NP-completi anche allora. Questi ultimi sono chiamati fortemente NP-completi. L’esempio più noto è bin packing.

È anche (e forse più) interessante vedere come cambia la complessità di un algoritmo se l’input è compresso. Per l’esempio dei numeri primi di Mersenne, abbiamo visto tre codifiche, ognuna delle quali è logaritmicamente più compressa rispetto al suo predecessore.

Nel 1983, Hana Galperin e Avi Wigderson hanno scritto un interessante articolo sulla complessità degli algoritmi grafici comuni quando la codifica di input del grafico viene compressa logaritmicamente. Per questi input, il linguaggio dei grafici contenenti un triangolo dall’alto (dove era chiaramente in P) diventa improvvisamente NP-completo.

E questo perché le classi linguistiche come P e NP sono definite per le lingue, non per problemi.