Computazione e complessità

Cosa possono davvero fare i computer — e cosa no?

Livello Base — linguaggio semplice, senza matematica

I computer sembrano inarrestabili — fanno atterrare razzi, stracciano i grandi maestri a scacchi, dipingono scene fotorealistiche da una frase. Ed ecco una vera scossa: ci sono problemi che nessun computer, per quanto veloce o enorme o astutamente programmato, risolverà mai. Non perché non abbiamo ancora costruito la macchina giusta, ma perché è matematicamente impossibile, punto.

Alan Turing lo dimostrò nel 1936 — prima ancora che esistessero i computer veri. Non si può scrivere alcun programma che decida in modo affidabile se un dato programma finirà prima o poi o girerà per sempre. Si chiama problema della fermata, ed è dimostrabilmente irrisolvibile. Il trucco di Turing fu pura logica: se un tale verificatore esistesse, potresti puntarlo su sé stesso e fabbricare una contraddizione, esattamente come la frase "Questa affermazione è falsa."

Oltre ciò che è impossibile sta la domanda di ciò che è semplicemente difficile. Ordinare una lista richiede millisecondi; trovare il tour più breve attraverso 1.000 città sembra esigere di provare un numero sbalorditivo di combinazioni, senza speranza persino per un supercomputer. La più grande domanda aperta dell'informatica — e uno dei grandi problemi irrisolti di tutta la matematica — è se quei problemi difficili siano davvero difficili, o se siamo semplicemente stati troppo lenti a scorgere una scorciatoia. È P vs NP, e c'è un premio da 1.000.000 di dollari ad aspettare chi lo risolverà.

Macchine di Turing, decidibilità e lo zoo della complessità

Livello Studente — le equazioni principali

Una macchina di Turing è la computazione ridotta all'osso: un nastro infinito, una testina che legge e scrive una casella, e una manciata di stati con regole \(\delta(\text{stato}, \text{simbolo}) \to (\text{stato}', \text{simbolo}', \text{movimento})\). Sembra assurdamente primitiva, eppure la tesi di Church–Turing sostiene che qualsiasi cosa sia calcolabile è calcolabile da una di queste. E una singola macchina di Turing universale, ricevuta la descrizione di qualsiasi altra, può imitarla perfettamente — il seme teorico di ogni computer general-purpose che tu abbia mai usato.

Il problema della fermata di Turing salta fuori per diagonalizzazione. Supponi che un decisore \(H(M, w)\) sappia sempre dire se la macchina \(M\) si ferma sull'input \(w\). Costruisci un guastafeste \(D(M)\) che esegue \(H(M, M)\) e poi fa l'opposto — gira all'infinito se \(H\) dice "si ferma", si ferma se \(H\) dice "gira all'infinito". Ora dai a \(D\) la propria descrizione: \(D(D)\) si ferma esattamente quando non lo fa. Contraddizione, quindi \(H\) non può esistere. Il teorema di Rice generalizza il danno: ogni domanda non banale su cosa fa un programma è indecidibile, ed è per questo che il controllo automatico perfetto dei bug è fuori discussione.

Fra i problemi che sono risolvibili, ordiniamo per costo. P è tutto ciò che è decidibile in tempo polinomiale; NP è tutto ciò la cui risposta, una volta indovinata, può essere verificata in tempo polinomiale — Sudoku, colorazione di grafi, fattorizzazione. Un problema è NP-completo se è in NP e ogni altro problema NP si riduce a esso, quindi è difficile quanto l'intera classe in un colpo. Cook e Levin (1971) dimostrarono che la soddisfacibilità booleana (SAT) è uno di questi, e migliaia di problemi quotidiani si sono da allora uniti a esso. Risolvine uno solo efficientemente e hai dimostrato \(P = NP\) — e li hai risolti tutti.

Complessità dei circuiti, computazione randomizzata e i limiti della dimostrazione

Livello Esperto — profondità matematica completa

01P vs NP come domanda sulla dimensione dei circuiti

Un angolo promettente su \(P\) vs \(NP\) lo riformula in hardware. Qualsiasi computazione può essere disposta come un circuito booleano — un grafo di porte AND, OR e NOT — e il suo costo è il numero di porte. Tutto ciò che è in \(P\) ha circuiti di dimensione polinomiale, quindi se potessi dimostrare che qualche problema \(NP\) richiede superpolinomialmente tante porte, avresti separato le classi. Il piano è pulito; l'esecuzione si è rivelata brutale.

02Le funzioni difficili esistono — solo che non riusciamo a indicarne una

Curiosamente, sappiamo che le funzioni difficili sono ovunque. Un semplice argomento di conteggio (Shannon) mostra che quasi ogni funzione booleana su \(n\) bit richiede un circuito di dimensione \(\Omega(2^n/n)\) — astronomicamente grande — quindi la stragrande maggioranza delle funzioni è difficile. L'intoppo è che l'argomento è non costruttivo: dimostra che le funzioni difficili abbondano senza nominarne una sola. Per funzioni esplicite in \(NP\), i migliori limiti inferiori che qualcuno abbia dimostrato restano vicini a \(\Omega(n \log n)\), una distanza risibile dall'esponenziale. Siamo circondati da problemi difficili e non riusciamo a dimostrarne difficile quasi nessuno.

03La barriera delle prove naturali

Peggio, ci sono prove che le strategie ovvie non possano funzionare. Razborov e Rudich (1994) mostrarono che qualsiasi prova "naturale" — costruttiva e applicabile alla maggior parte delle funzioni, come lo sono quasi tutti gli argomenti sui circuiti — se dimostrasse forti limiti inferiori, ti consegnerebbe anche un algoritmo per rompere i generatori pseudocasuali crittografici. Così una prova naturale di \(P \ne NP\) distruggerebbe le stesse funzioni a senso unico che la crittografia moderna assume esistano. Gli strumenti che sembrano ovvi sono dimostrabilmente troppo grossolani.

04Le altre mura: relativizzazione e algebrizzazione

Altre due barriere cingono il campo. La maggior parte delle tecniche classiche relativizza — funzionerebbe ancora se ogni macchina avesse un oracolo magico — eppure esistono mondi con oracolo dove \(P = NP\) e altri dove \(P \ne NP\), quindi nessuna prova che relativizza può deciderlo. I metodi algebrici che risolsero \(IP = PSPACE\) schivano quello ma colpiscono la successiva barriera dell'algebrizzazione. Fra loro, tre barriere escludono essenzialmente ogni metodo che abbiamo attualmente — ed è per questo che una risoluzione richiederebbe un'idea genuinamente nuova, non una versione più affilata di una vecchia.

05La casualità è davvero necessaria?

Un filo diverso chiede se il lancio di monete aggiunga vera potenza. BPP è ciò che puoi risolvere in tempo polinomiale ammettendo un piccolo errore a due code, e per decenni sembrò strettamente più ricco di \(P\). La sorpresa (Impagliazzo–Wigderson, 1997) è che probabilmente non lo è: se esistono funzioni sufficientemente difficili, allora \(BPP = P\) e ogni algoritmo randomizzato può essere derandomizzato. La difficoltà, il cattivo della storia P-vs-NP, si rivela esattamente ciò che servirebbe per rendere la casualità superflua.

06Prove interattive e uno shock dal 2020

Lascia che un verificatore interroghi un dimostratore e la portata della computazione si espande in modo sbalorditivo. Shamir dimostrò \(IP = PSPACE\): qualsiasi cosa risolvibile in memoria polinomiale può essere verificata tramite conversazione. Aggiungi più dimostratori che condividono entanglement quantistico ed esplode fino a \(MIP^* = RE\) (Ji et al., 2020) — l'intera classe dei problemi ricorsivamente enumerabili, inclusi quelli indecidibili. Quel risultato non solo sbalordì i teorici della complessità; risolse la congettura di immersione di Connes nell'algebra degli operatori pura, un promemoria che la teoria della computazione ora si spinge negli angoli remoti della matematica.