"Det er en av de mest grunnleggende intellektuelle spørsmålene som noen gang er stilt," sier Avi Wigderson, mottaker av 2024 ACM Turing Award, angående spørsmålet om P = NP. "Hvis alle tar feil, og P er lik NP, får det fantastiske konsekvenser."
ACM
Association for Computing Machinery (ACM) kunngjorde onsdag at den har tildelt årets A.M. Turing-prisen, ofte referert til som Nobelprisen for databehandling, til informatiker og matematiker Avi Wigderson ved Princetons Institute for Advanced Study.
Wigderson ble anerkjent for grunnleggende bidrag som fremmet det som er kjent som Theory of Computation, med spesiell utmerkelse når det gjelder å “omforme vår forståelse av rollen til tilfeldighet i beregninger”," og “tiår med intellektuelt lederskap innen teoretisk informatikk”," sa ACM.
Også: Algoritmer vil snart styre livet ditt – og ødelegge det, hvis de trenes feil
Oppkalt etter den britiske matematikeren og informatikeren Alan M Turing, prisen kommer med en premie på 1 million dollar med økonomisk støtte fra Google.
Wigderson, Herbert H. Maass-professoren ved Princeton, har gjennom flere tiår demonstrert en dyp forståelse av beregning som mer enn bare maskiner. Beregning er et fenomen som finnes i hele universet.
"Beregning er en virkelig grunnleggende oppfatning," sa Wigderson i et intervju med ZDNET. "Det er ikke bare algoritmer i datamaskiner: alt beregnes."
"Når du ser et skjell på stranden, med et bemerkelsesverdig mønster, som ble beregnet ved hjelp av ekstremt enkle trinn: Det vokste fra ett korn, og lokalt beregnet disse kornene nabokorn, og ble koblet sammen — denne virkelig enkle prosessen, du utvikler det, og du får noen fantastiske mønstre."
Disse enkle reglene for lokal, inkrementell endring — “som vi kjenner veldig godt”," sa Wigderson – “kan skape veldig komplekse fenomener.” Beregningseksempler florerer. Beregning er hvordan det befruktede egget blir et menneske, eller hvordan menneskelige celler deler seg gjennom ens levetid. "Også sladder," la Wigderson til. "Når du forteller noe som ble fortalt til deg, eller på Facebook – måten informasjon utvikler seg på, er dette beregningsspørsmål som kan settes inn i komplette beregningsmodeller."
Å tildele Turing-prisen til Wigderson er spesielt passende fordi feltet hans, Theory of Computation, ble startet av Turing i 1936 med Turings landemerkepapir, “On Computable Numbers, With an Application to the Entscheidungsproblem”. ."
Turing la grunnlaget for den ekstremt brede definisjonen av beregning som en utvikling av et miljø via lokale, inkrementelle endringer, hvor “miljøet”; kan være mennesker, galakser, skjell på stranden, informasjon eller en rekke fenomener.
Også: Jack Dongarra, som gjorde superdatamaskiner brukbare, tildelte 2021 ACM Turing-prisen
Sett gjennom objektivet til Turing, som avansert over flere tiår av Wigderson og kolleger, er ethvert naturfenomen beregning. "Hvordan termitter bygger disse slottene, eller biene, som på en eller annen måte vet hvor de skal gå og lete etter honningen — de utvikler seg faktisk for å skape, selv om de har veldig små hjerneceller," forklarte Wigderson.
Prisen anerkjenner Wigderson spesifikt for hans bidrag til å forstå rollen tilfeldighet spiller i beregninger. Konvensjonelle datamaskiner, fra stormaskiner til iPhone, er “deterministiske”; betyr at de følger et forutsigbart mønster av trinn. Men mange av de mest spennende eksemplene på beregninger i naturen involverer elementer av tilfeldighet, fra skjell til flokken av stær kjent som murring.
Wigderson og medarbeidere brukte utforskningen av tilfeldighet for å fremme forståelsen av hvilke problemer som kan og ikke kan beregnes "effektivt." Det er mange problemer i verden — innen naturvitenskap, matematikk og ingeniørfag — som det ikke finnes noen kjente effektive algoritmer for, noe som betyr en algoritme som kan fungere i “polynomisk tid”," snarere enn eksponentiell tid.
Også: Alan Turings varige arv: 10 ideer utover Enigma
For eksempel har ikke faktorisering av store heltall til deres primfaktorer en kjent algoritme som kan kjøres på mindre enn eksponentiell tid. Men det er ikke nok å finne en slik algoritme; informatikere og matematikere ønsker å bevise, for å vite sikkert, på en eller annen måte, om det kan finnes en løsning for slike “harde”; problemer.
De tre hovedoppgavene som er sitert av ACM danner en sekvens, en progresjon, fortalte Wigderson til ZDNET.
"Spørsmålet var hvor kraftig er tilfeldighet i algoritmer," sa Wigderson. Fra åttitallet hadde informatikere funnet mange måter å bruke tilfeldighet som en vei til effektive algoritmer, "Og så det så ut som tilfeldighet er veldig kraftig."
"Disse verkene hadde som mål å vise at tilfeldighet ikke er så kraftig," han sa. I stedet utviklet Wigderson og kollegene pseudorandom-tallgeneratorer som kunne løse noen vanskelige problemer på en effektiv, deterministisk måte.
"I alle disse papirene tar du et vanskelig problem og du lager en pseudorandomgenerator som deterministisk kan generere biter som ser tilfeldige ut, og du kan erstatte tilfeldige innganger i en sannsynlighetsalgoritme [og måte] en deterministisk en."
Også: Berømte datavitere
Lukkingen av tilfeldigheten, og erstattet den med en deterministisk tilnærming, kulminerte i den endelige artikkelen med den mest sofistikerte pseudorandomgeneratoren. Leksjonen, bemerket Wigderson: "Vi kan konkludere med at enhver polynomisk-tids-probabilistisk algoritme kan gjøres til en polynom-tidsdeterministisk."
En overraskende bieffekt av disse oppdagelsene er at hvis du kan fjerne tilfeldighet fra en algoritme, kan du bevise hardheten til problemet – en slående bakdør måte å avgjøre spørsmålet om et problem er eller er ikke vanskelig.
“På en eller annen måte er disse to begrepene [tilfeldighet og hardhet], som er svært forskjellige, tett forbundet," sa Wigderson. “De er nesten det samme. Å fjerne tilfeldighet fra sannsynlighetsalgoritmer og bevise hardheten til beregningsproblemer er på en måte doble problemer."
For de som ønsker å gå dypere inn i arbeidet med tilfeldighet, er papirene listet opp nedenfor. Du kan imidlertid bare lese kapittelet om tilfeldighet i Wigdersons store volum, "Math and Computation," som er tilgjengelig som gratis nedlasting. Hvis du skumleser den boken, vil du være hode og skuldre over folk flest på ditt neste cocktailparty.
"Hardhet vs. tilfeldighet" (Medforfatter med Noam Nisan)
Blant andre funn introduserte denne artikkelen en ny type pseudorandomgenerator, og beviste at effektiv deterministisk simulering av randomiserte algoritmer er mulig under mye svakere forutsetninger enn tidligere kjent."BPP har subeksponentielle tidssimuleringer med mindre EXPTIME har publiserbare bevis" (Medforfatter med László Babai, Lance Fortnow og Noam Nisan)
Denne artikkelen brukte `hardness amplification'. for å demonstrere at bounded-error probabilistic polynomial time (BPP) kan simuleres i subeksponentiell tid for uendelig mange inngangslengder under svakere forutsetninger. "P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma" (Medforfatter med Russell Impagliazzo)
Denne artikkelen introduserer en sterkere pseudo-tilfeldig generator med i hovedsak optimal hardhet vs tilfeldighet avveininger.
For Wigderson, 67, var gleden ved å erte ut overraskende forbindelser en drivende impuls fra en tidlig alder .
Også: AI på seksti sekunder
"Jeg har alltid elsket matematikk fra tidlig barndom," sa Wigderson. "Pappa interesserte meg i gåter og sånt."
Wigderson ble uteksaminert fra Israels Technion (Institute of Technology) og oppnådde master- og doktorgrader i informatikk fra Princeton University. Et rørende foredrag om hans opplevelser tilbys i Wigdersons takketale i fjor da han mottok en æresdoktorgrad fra Technion.
"Jeg bryr meg virkelig om å formalisere beregningsmodeller," sa Wigderson om det som tiltrekker hans interesse, “som om en kryptografisk protokoll er sikker eller en algoritmes kjøretid er slik og slik.
"Det faktum at det omhandler denne grunnleggende forestillingen, men det er faktisk et matematisk felt, er for meg veldig verdifullt."
Også: Nvidia gir AI-superdatamaskin til studenter slik at de har samme kraft som store tekniske ingeniører
Blant prestasjonene som han er stoltest av, sa Wigderson, er arbeidet hans med å fremme det som kalles “null-kunnskapsbevis”, " hvor informasjon kan holdes hemmelig, men to motparter kan likevel komme til en forståelse. “La oss si at jeg vet noe, jeg vet hvem som vil vinne valget, og du tror meg ikke, og jeg prøver å overbevise deg [at jeg virkelig gjør det].” Det er en måte for meg å overbevise deg uten å fortelle deg noe du ikke allerede visste."
Faktisk er en slik tilstand roten til kryptografi med offentlig nøkkel, der hver part holder sin private nøkkel skjult, men er i stand til å overbevise den andre om at de autoritativt har signert en elektronisk kontrakt, for eksempel. “Det er en helt paradoksal forestilling,” sa Wigderson om slike null-kunnskapsbevis. "Dette er den typen ting som får deg til å tenke på at noe slikt kan eksistere."
Wigdersons intellekt balanserer glede med en skarp følelse av den underliggende betydningen. Spørsmålet om hvilke problemer som beviselig er vanskelige, har for eksempel store innsatser for samfunnet.
Også: AI kan ha 20 % sjanse for sansning om 10 år, sier filosof David Chalmers
Som formulert på 1970-tallet, spør setningen “Does P = NP?”, om et problem hvis løsning kan verifiseres også, til syvende og sist, kan løses med en polynom-tidsligning — løst effektivt. I så fall kan en datamaskin sannsynligvis bygges for å løse noen av verdens tilsynelatende uløselige problemer i praktiske tidsrom.
“Det er et av de mest grunnleggende intellektuelle spørsmålene som noen gang er stilt,” sa Wigderson av P = NP. Hans personlige formodning, som er konsensus på feltet hans, er at P ikke er lik NP, noe som betyr at noen problemer ikke kan løses effektivt.
"Hvis alle tar feil, og P er lik NP, får det fantastiske konsekvenser," sa Wigderson. "Nesten alle problemer du ønsker å løse, kan du løse effektivt — hva som helst; du kan kurere kreft."
Imidlertid, “Hvis P ikke er lik NP, er implikasjonene for ting utenfor vår rekkevidde ganske betydelige”," sa Wigderson. For det første vil det bety at noen elementer av menneskelig tanke, som kreativitet, godt kan være utenfor rekkevidde av datamaskiner fordi det ikke er noen måte å effektivt simulere heuristikken, den menneskelige følelsen av ting som går inn i, for eksempel, kunstnerisk skapelse.
Men glasset er halvfullt, i en annen forstand: Hvis NP-problemer ikke kan løses effektivt, betyr det at kryptografi – hele grunnlaget for den moderne økonomien – er trygt fra å bli sprakk, bemerket Wigderson .
Også: Den nye Turing-testen: Er du menneske?
Hvorvidt P er lik NP eller ikke er et åpent spørsmål. "Jeg håpet å se noen bevise det i min levetid, nå tviler jeg på det," sa Wigderson.
Kvantedatamaskinen er heller ikke det enkle svaret på den blindveien. “Tenk på en kvantedatamaskin: denne eksisterer ikke”," sa Wigderson. "Vi vet ikke om det noen gang vil eksistere" — selv om det er intenst teoretisert av IBM og Google og andre.
Hvis P = NP er et åpent problem, så er også øyeblikkets spørsmål: Hva kan AI – inkludert "kunstig generell intelligens" maskiner — gjøre eller ikke gjøre for å like menneskelig tanke? Visst, forestillingen om at alt i universet beregner innebærer AI bør være i stand til å oppnå et visst mål av menneskelig evne.
Også: AIs sanne mål er kanskje ikke lenger intelligens
“Vi er karbon, og de er silisium, så materialet er annerledes, men vanskelighetene er på et psykologisk nivå, ikke på det operasjonelle nivået,”" er Wigdersons syn. Allerede har AI demonstrert at den “kan løse mange problemer som vi ikke visste hvordan vi skulle løse før”," sa Wigderson. Han kjenner "noen fremtredende matematikere som begynner å bruke disse enhetene som samarbeidspartnere" i teorembevis og lignende.
“Det som er mer interessant for meg er hva de ikke kan gjøre,” han sa. "Hva er grensene for denne typen datamaskiner?" En av disse grensene er den relative mangelen på data som kreves for å trene AI-modeller for noen problemer.
Også: Kan generativ AI løse datavitenskapens største uløste problem?
"For eksempel , utforme en ny matematisk teori som relativitetsteori, eller Maxwell [Maxwells ligninger] — for disse er det mange færre eksempler, ikke sant? Så jeg tror at denne typen teoretiske gjennombrudd vil være vanskeligere for disse maskinene fordi det ikke er så mye data."
For de mange implikasjonene av at P tilsvarer eller ikke tilsvarer NP, er Wigderson fornøyd med å la en ny generasjon lede an.
"Jeg har det gøy med postdoktorene ved instituttet, og de er alle strålende, og jeg samarbeider med noen av dem, og bare lærer av de unge," han sa. “Det er veldig hyggelig å være i denne situasjonen omgitt av unge mennesker som får deg til å lære.”