Per il vincitore del Premio Turing, tutto è calcolo e alcuni problemi sono irrisolvibili

Il lavoro pionieristico di Avi Wigderson sulla casualità ha avanzato l'idea che alcuni problemi potrebbero semplicemente essere al di là anche dei computer più potenti.

"È una delle domande intellettuali più fondamentali mai poste", afferma Avi Wigderson, destinatario dell'ACM Turing Award 2024, riguardo alla questione P=NP. "Se tutti hanno torto e P è uguale a NP, le conseguenze sono sorprendenti."

Mercoledì l'Association for Computing Machinery (ACM) ha annunciato di aver assegnato il premio A.M. Il Premio Turing, spesso definito Premio Nobel per l'informatica, è stato assegnato allo scienziato informatico e matematico Avi Wigderson dell'Institute for Advanced Study di Princeton, nel New Jersey.

Wigderson è stato riconosciuto per i contributi fondamentali che hanno fatto avanzare quella che è conosciuta come la teoria del calcolo, con particolare distinzione nel "rimodellare la nostra comprensione del ruolo della casualità nel calcolo" e "decenni di leadership intellettuale nell'informatica teorica", ha affermato l'ACM.

Prende il nome dal matematico e informatico britannico Alan M. Turing, il premio prevede un premio di 1 milione di dollari con il sostegno finanziario fornito da Google.

Wigderson, il professore Herbert H. Maass presso l'Istituto, ha dimostrato nel corso di decenni una profonda comprensione del fatto che il calcolo è qualcosa di più che semplici macchine. Il calcolo è un fenomeno presente in tutto l’universo.

"Il calcolo è un concetto davvero fondamentale", ha affermato Wigderson in un'intervista a ZDNET. "Non si tratta solo di algoritmi nei computer: tutto calcola."

"Quando vedi una conchiglia sulla spiaggia, con qualche disegno notevole, che è stata calcolata con passaggi estremamente semplici: cresceva da un granello e, localmente, questi granelli calcolavano i granelli vicini e erano collegati - questo processo davvero semplice, tu evolvilo e otterrai dei modelli sorprendenti."

Queste semplici regole di cambiamento locale e incrementale - “che conosciamo molto bene”, ha affermato Wigderson - “possono creare fenomeni molto complessi”. Gli esempi computazionali abbondano. Il calcolo è il modo in cui l'ovulo fecondato diventa un essere umano, o il modo in cui le cellule umane si dividono nel corso della vita. "Inoltre, pettegolezzi", ha aggiunto Wigderson. "Quando racconti qualcosa che ti è stato detto, o su Facebook, il modo in cui si evolvono le informazioni, queste sono domande computazionali che possono essere inquadrate in modelli computazionali completi."

Assegnare il premio Turing a Wigderson è particolarmente appropriato perché il suo campo, la teoria del calcolo, fu iniziato da Turing nel 1936 con il suo articolo fondamentale, "Sui numeri computabili, con un'applicazione all'Entscheidungsproblem".

Turing ha gettato le basi per una definizione estremamente ampia di computazione come evoluzione di un ambiente attraverso cambiamenti locali e incrementali, dove l'"ambiente" può essere esseri umani, galassie, conchiglie sulla spiaggia, informazioni o qualsiasi numero di fenomeni.

Visto attraverso la lente di Turing, come avanzata nel corso di decenni da Wigderson e colleghi, ogni fenomeno naturale è un calcolo. "Come le termiti costruiscono questi castelli, o le api, che in qualche modo sanno dove andare a cercare il miele, in realtà si evolvono per creare, anche se hanno cellule cerebrali molto piccole", ha spiegato Wigderson.

Il premio riconosce Wigderson specificatamente per il suo contributo alla comprensione del ruolo svolto dalla casualità nel calcolo. I computer convenzionali, dai mainframe agli iPhone, sono “deterministi”; nel senso che seguono uno schema prevedibile di passaggi. Ma molti degli esempi più intriganti di calcolo in natura coinvolgono elementi di casualità, dalla conchiglia allo stormo di storni noto come murmuration.

Wigderson e collaboratori hanno utilizzato l'esplorazione della casualità per migliorare la comprensione di quali problemi possono e non possono essere calcolati "in modo efficiente". Ci sono numerosi problemi nel mondo - nella scienza, nella matematica e nell’ingegneria - per i quali non esistono algoritmi efficienti, ovvero un algoritmo che possa operare in “tempo polinomiale”, piuttosto che in tempo esponenziale.

Ad esempio, la fattorizzazione di grandi numeri interi nei loro fattori primi non dispone di un algoritmo noto che possa essere eseguito in un tempo inferiore a quello esponenziale. Ma non basta trovare un simile algoritmo; gli informatici e i matematici vogliono dimostrare, sapere con certezza, in un modo o nell'altro, se potrebbe esistere una soluzione per problemi così "difficili".

I tre documenti principali citati dall’ACM formano una sequenza, una progressione, ha detto Wigderson a ZDNET.

"La domanda era quanto sia potente la casualità negli algoritmi", ha affermato Wigderson. A partire dagli anni Ottanta, gli informatici avevano trovato molti modi per utilizzare la casualità come percorso verso algoritmi efficienti, "E quindi, sembrava che la casualità fosse molto potente".

"Questi lavori miravano a dimostrare che la casualità non è così potente", ha detto. Wigderson e colleghi hanno invece sviluppato generatori di numeri pseudocasuali in grado di risolvere alcuni problemi difficili in modo efficiente e deterministico.

"In tutti questi articoli, prendi un problema difficile e crei un generatore pseudocasuale in grado di generare in modo deterministico bit che sembrano casuali, e puoi sostituire input casuali in un algoritmo probabilistico [e modellarne] uno deterministico."

L'eliminazione della casualità, sostituendola con un approccio deterministico, è culminata nell'articolo finale con il più sofisticato generatore pseudocasuale. La lezione, ha osservato Wigderson: "Potremmo concludere che qualsiasi algoritmo probabilistico in tempo polinomiale può essere reso deterministico in tempo polinomiale".

Un effetto collaterale sorprendente di queste scoperte è che se si riesce a rimuovere la casualità da un algoritmo, si può dimostrare la durezza del problema: un sorprendente modo segreto per risolvere la questione se un problema sia o meno difficile. .

"In qualche modo, questi due concetti [casualità e durezza], che sono molto diversi, sono intimamente connessi", ha affermato Wigderson. "Sono quasi la stessa cosa. Rimuovere la casualità dagli algoritmi probabilistici e dimostrare la durezza dei problemi computazionali sono, in un certo senso, problemi doppi."

Per coloro che desiderano approfondire il lavoro sulla casualità, gli articoli sono elencati di seguito. Tuttavia, puoi semplicemente leggere il capitolo sulla casualità nel grande volume di Wigderson, "Math and Computation", disponibile come download gratuito. Se scorri quel libro, sarai una spanna sopra la maggior parte delle persone al tuo prossimo cocktail party.

• "Durezza vs. casualità" (scritto in collaborazione con Noam Nisan)
  Tra gli altri risultati, questo articolo ha introdotto un nuovo tipo di generatore pseudocasuale e ha dimostrato che una simulazione deterministica efficiente di algoritmi randomizzati è possibile con presupposti molto più deboli di quelli precedentemente noti.

• "BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs" (scritto in collaborazione con László Babai, Lance Fortnow e Noam Nisan)
  Questo articolo ha utilizzato l'"amplificazione della durezza" per dimostrare che il tempo polinomiale probabilistico con errore limitato (BPP) può essere simulato in tempo subesponenziale per infinite lunghezze di input sotto ipotesi più deboli.

• "P=BPP se E richiede circuiti esponenziali: derandomizzazione del lemma XOR" (scritto in collaborazione con Russell Impagliazzo)
  Questo articolo introduce un generatore pseudo-casuale più forte con compromessi essenzialmente ottimali tra durezza e casualità.

Per Wigderson, 67 anni, il piacere di scoprire connessioni sorprendenti è stato un impulso trainante fin dalla tenera età.

"Ho sempre amato la matematica fin dalla prima infanzia", ha detto Wigderson. "Mio padre mi interessava ai puzzle e cose del genere."

Wigderson si è laureato al Technion (Istituto di tecnologia) israeliano e ha conseguito un master e un dottorato in scienze informatiche presso l'Università di Princeton. Un discorso commovente sulle sue esperienze è stato offerto nel discorso di accettazione di Wigderson l'anno scorso quando ha ricevuto un dottorato onorario dal Technion.

"Mi interessa davvero formalizzare i modelli computazionali", ha detto Wigderson riguardo a ciò che attira il suo interesse, "ad esempio, se qualche protocollo crittografico è sicuro o il tempo di esecuzione di qualche algoritmo è così e così.

"Il fatto che si tratti di questa nozione fondamentale, ma in realtà è un campo matematico, è per me molto prezioso."

Tra i risultati di cui è più orgoglioso, ha affermato Wigderson, c'è il suo lavoro nel portare avanti quelle che vengono chiamate "prove a conoscenza zero", dove le informazioni possono essere mantenute segrete ma due controparti possono comunque raggiungere un'intesa. "Diciamo che so qualcosa, so chi vincerà le elezioni, e tu non mi credi, e sto cercando di convincerti [che lo faccio davvero]. C'è un modo per convincerti senza dirtelo tutto quello che non sapevi già."

In effetti, questo stato di cose è la radice della crittografia a chiave pubblica, dove ciascuna parte mantiene nascosta la propria chiave privata ma è in grado di convincere l'altra, ad esempio, di aver firmato in modo autorevole un contratto elettronico. "È un'idea totalmente paradossale", ha detto Wigderson riguardo a tali prove a conoscenza zero. "Questo è il genere di cose che ti lascia a bocca aperta al pensiero che qualcosa del genere possa esistere."

Gli equilibri intellettuali di Wigderson si dilettano con un acuto senso del significato sottostante. La questione di quali problemi siano effettivamente difficili, ad esempio, ha una grande posta in gioco per la società.

Come formulata negli anni '70, la frase "P=NP?", chiede se un problema la cui soluzione può essere verificata potrebbe anche, in definitiva, essere risolto da un'equazione tempo-polinomiale - risolto in modo efficiente. Se così fosse, allora si potrebbe probabilmente costruire un computer in grado di risolvere in tempi pratici alcuni dei problemi apparentemente irrisolvibili del mondo.

"È una delle domande intellettuali più fondamentali mai poste", ha affermato Wigderson di P=NP. La sua congettura personale, che è consenso nel suo campo, è che P non è uguale a NP, il che significa che alcuni problemi non possono essere risolti in modo efficiente.

"Se tutti hanno torto e P è uguale a NP, le conseguenze sono sorprendenti", ha affermato Wigderson. "Praticamente qualsiasi problema tu voglia risolvere, puoi risolverlo in modo efficiente: qualsiasi cosa; potresti curare il cancro."

Tuttavia, "Se P non è uguale a NP, le implicazioni per cose oltre la nostra portata sono piuttosto significative", ha affermato Wigderson. Per prima cosa, significherebbe che alcuni elementi del pensiero umano, come la creatività, potrebbero essere fuori dalla portata dei computer perché non c’è modo di simulare in modo efficiente l’euristica, il senso umano delle cose che entrano, ad esempio, nella creazione artistica. .

Ma il bicchiere è mezzo pieno, in un altro senso: se i problemi NP non possono essere risolti in modo efficiente, significa che la crittografia - l’intera base dell’economia moderna - è al sicuro da eventuali tentativi di cracking, ha osservato Wigderson.

Se P sia uguale o meno a NP è una questione aperta. "Speravo di vedere qualcuno dimostrarlo durante la mia vita, ora ne dubito", ha detto Wigderson.

Né il computer quantistico è la risposta facile a questa impasse. "Pensate a un computer quantistico: questo non esiste", ha detto Wigderson. "Non sappiamo se esisterà mai" - anche se è intensamente teorizzato da IBM, Google e altri.

Se P=NP è un problema aperto, lo è anche la domanda del momento: cosa può fare o non fare l'intelligenza artificiale, comprese le macchine di "intelligenza artificiale generale", per eguagliare il pensiero umano? Certamente, l’idea che tutto nell’universo è computabile implica che l’intelligenza artificiale dovrebbe essere in grado di raggiungere una certa misura delle capacità umane.

"Noi siamo carbonio e loro silicio, quindi il materiale è diverso, ma le difficoltà sono a livello psicologico, non operativo", è il punto di vista di Wigderson. L'intelligenza artificiale ha già dimostrato che "può risolvere molti problemi che prima non sapevamo come risolvere", ha affermato Wigderson. Conosce "alcuni eminenti matematici che stanno iniziando a utilizzare questi dispositivi come collaboratori" nella dimostrazione di teoremi e simili.

"Ciò che è più interessante per me è ciò che non possono fare", ha detto. "Quali sono i limiti di questo tipo di computer?" Uno di questi limiti è la relativa scarsità di dati necessari per addestrare i modelli di intelligenza artificiale per alcuni problemi.

"Ad esempio, progettare una nuova teoria matematica come la relatività, o Maxwell [le equazioni di Maxwell] - per queste, ci sono molti meno esempi, giusto? Quindi, penso che questo tipo di svolta teorica sarà più difficile per queste macchine perché non c'è non ci sono così tanti dati."

Considerate le molteplici implicazioni del fatto che P sia uguale o meno a NP, Wigderson si accontenta di lasciare che sia una nuova generazione a aprire la strada.

"Mi sto divertendo con i postdoc dell'istituto, e sono tutti brillanti, e sto collaborando con alcuni di loro, e sto imparando dai più giovani", ha detto. "È molto bello essere in questa situazione circondato da giovani che ti permettono di imparare."