Dla zdobywcy nagrody Turinga wszystko jest obliczeniami, a niektórych problemów nie da się rozwiązać

Pionierska praca Aviego Wigdersona nad losowością rozwinęła pogląd, że niektóre problemy mogą po prostu wykraczać poza możliwości nawet najpotężniejszych komputerów.

„To jedno z najbardziej podstawowych pytań intelektualnych, jakie kiedykolwiek zadano” - mówi Avi Wigderson, laureat nagrody Turinga ACM w 2024 r., odnosząc się do pytania P=NP. „Jeśli wszyscy się mylą i P równa się NP, ma to niesamowite konsekwencje”.

Stowarzyszenie na rzecz Maszyn Obliczeniowych (ACM) ogłosiło w środę, że przyznało tegoroczną nagrodę A.M. Nagrodę Turinga, często nazywaną Nagrodą Nobla w dziedzinie informatyki, przyznano informatykowi i matematykowi Avi Wigdersonowi z Institute for Advanced Study w Princeton w stanie New Jersey.

Wigdersona doceniono za zasadniczy wkład w rozwój tak zwanej teorii obliczeń, ze szczególnym wyróżnieniem w „przekształceniu naszego rozumienia roli losowości w obliczeniach” oraz za „dziesiątki lat intelektualnego przywództwa w dziedzinie informatyki teoretycznej” - stwierdziło ACM.

Nagroda, nazwana na cześć brytyjskiego matematyka i informatyka Alana M. Turinga, obejmuje nagrodę o wartości 1 miliona dolarów przy wsparciu finansowym Google.

Wigderson, profesor Herberta H. Maassa w Instytucie, przez dziesięciolecia wykazał się głębokim zrozumieniem obliczeń jako czegoś więcej niż tylko maszyn. Obliczenia to zjawisko występujące w całym wszechświecie.

„Obliczenia to naprawdę podstawowe pojęcie” - powiedział Wigderson w wywiadzie dla ZDNET. „To nie tylko algorytmy w komputerach: wszystko oblicza”.

„Kiedy widzisz na plaży muszlę z jakimś niezwykłym wzorem, który został obliczony w niezwykle prostych krokach: wyrosła z jednego ziarna, a lokalnie te ziarna obliczyły sąsiednie ziarna i zostały połączone - jest to naprawdę prosty proces, rozwijaj go, a otrzymasz niesamowite wzory.”

Te proste zasady lokalnych, stopniowych zmian - „które znamy bardzo dobrze” - powiedział Wigderson - „mogą stworzyć bardzo złożone zjawiska”. Przykładów obliczeniowych jest mnóstwo. Obliczenia mówią o tym, jak zapłodnione jajo staje się człowiekiem lub jak komórki ludzkie dzielą się przez całe życie. „Plotki też” - dodał Wigderson. „Kiedy mówisz coś, co ci powiedziano, lub na Facebooku - w sposób, w jaki ewoluują informacje, są to pytania obliczeniowe, które można ująć w kompletne modele obliczeniowe”.

Przyznanie Wigdersonowi nagrody Turinga jest szczególnie trafne, ponieważ jego dziedzina, teoria obliczeń, została zapoczątkowana przez Turinga w 1936 roku przełomowym artykułem Turinga „O liczbach obliczalnych z zastosowaniem do Entscheidungsproblem”.

Turing położył podwaliny pod niezwykle szeroką definicję obliczeń jako ewolucji środowiska poprzez lokalne, przyrostowe zmiany, gdzie „środowiskiem” mogą być ludzie, galaktyki, muszle na plaży, informacja lub dowolna liczba zjawisk.

Każde zjawisko naturalne, widziane przez pryzmat Turinga i rozwijane przez dziesięciolecia przez Wigdersona i współpracowników, jest obliczeniami. „Jak termity budują te zamki lub pszczoły, które w jakiś sposób wiedzą, gdzie iść i szukać miodu - w rzeczywistości ewoluują, by tworzyć, mimo że mają bardzo małe komórki mózgowe” - wyjaśnił Wigderson.

Nagroda przyznawana jest Wigdersonowi szczególnie za jego wkład w zrozumienie roli, jaką losowość odgrywa w obliczeniach. Konwencjonalne komputery, od komputerów typu mainframe po iPhone'y, są „deterministyczne”; co oznacza, że postępują zgodnie z przewidywalnym schematem kroków. Jednak wiele z najbardziej intrygujących przykładów obliczeń w przyrodzie obejmuje elementy losowości, od muszli po stada szpaków zwane szmerami.

Wigderson i współpracownicy wykorzystali badanie losowości, aby lepiej zrozumieć, jakie problemy można, a jakich nie można obliczyć „efektywnie”. Na świecie istnieje wiele problemów - w nauce, matematyce i inżynierii - dla których nie są znane skuteczne algorytmy, czyli algorytmy, które mogą działać w „czasie wielomianowym”, a nie w czasie wykładniczym.

Na przykład rozkład na czynniki dużych liczb całkowitych na ich czynniki pierwsze nie wymaga znanego algorytmu, który można wykonać w czasie krótszym niż wykładniczy. Ale nie wystarczy znaleźć taki algorytm; informatycy i matematycy chcą udowodnić, wiedzieć na pewno, w ten czy inny sposób, czy może istnieć rozwiązanie takich „trudnych” problemów.

Trzy główne artykuły cytowane przez ACM tworzą sekwencję, postęp, powiedział Wigderson ZDNET.

„Pytanie brzmiało, jak potężna jest losowość w algorytmach” - powiedział Wigderson. Począwszy od lat osiemdziesiątych informatycy odkryli wiele sposobów wykorzystania losowości jako drogi do wydajnych algorytmów. „Wyglądało więc na to, że losowość ma ogromną moc”.

„Te prace miały na celu pokazanie, że losowość nie jest tak potężna” - powiedział. Zamiast tego Wigderson i współpracownicy opracowali generatory liczb pseudolosowych, które mogłyby rozwiązać niektóre trudne problemy w skuteczny i deterministyczny sposób.

„We wszystkich tych artykułach podejmujesz trudny problem i tworzysz generator pseudolosowy, który może deterministycznie generować bity, które wyglądają losowo, i możesz zastąpić losowe dane wejściowe algorytmem probabilistycznym [i stworzyć] algorytm deterministyczny”.

Wyeliminowanie losowości i zastąpienie jej podejściem deterministycznym zakończyło się pracą końcową z najbardziej wyrafinowanym generatorem pseudolosowym. Z tej lekcji zauważył Wigderson: „Moglibyśmy stwierdzić, że dowolny algorytm probabilistyczny działający w czasie wielomianowym można przekształcić w algorytm deterministyczny działający w czasie wielomianowym”.

Zaskakującym efektem ubocznym tych odkryć jest to, że jeśli uda się usunąć losowość z algorytmu, można udowodnić stopień trudności problemu — jest to uderzający sposób na rozstrzygnięcie kwestii, czy problem jest trudny, czy nie. .

„W jakiś sposób te dwa pojęcia [losowość i twardość], które są bardzo różne, są ze sobą ściśle powiązane” - powiedział Wigderson. „To prawie to samo. Usunięcie losowości z algorytmów probabilistycznych i udowodnienie stopnia trudności problemów obliczeniowych to w pewnym sensie podwójne problemy”.

Dla tych, którzy chcą głębiej zagłębić się w prace nad losowością, poniżej znajduje się lista artykułów. Możesz jednak po prostu przeczytać rozdział o losowości w obszernym tomie Wigdersona „Math and Computation”, który jest dostępny do bezpłatnego pobrania. Jeśli przejrzysz tę książkę, na następnym przyjęciu koktajlowym będziesz o głowę przewyższał większość ludzi.

• „Twardość a losowość” (współautorstwo z Noamem Nisanem)
  W artykule tym wprowadzono między innymi nowy typ generatora pseudolosowego i udowodniono, że wydajna deterministyczna symulacja losowych algorytmów jest możliwa przy znacznie słabszych założeniach niż wcześniej wiadomo.

• „BPP ma subwykładnicze symulacje czasu, chyba że EXPTIME ma dowody do publikacji” (współautor: László Babai, Lance Fortnow i Noam Nisan)
  W artykule wykorzystano „wzmocnienie twardości”, aby wykazać, że probabilistyczny czas wielomianowy (BPP) z ograniczonym błędem może symulować w czasie podwykładniczym dla nieskończenie wielu długości wejściowych przy słabszych założeniach.

• „P=BPP, jeśli E wymaga obwodów wykładniczych: derandomizacja lematu XOR” (współautorstwo z Russellem Impagliazzo)
  W artykule tym przedstawiono silniejszy generator pseudolosowy z zasadniczo optymalną twardością i kompromisami w zakresie losowości.

Dla 67-letniego Wigdersona radość z odkrywania zaskakujących powiązań była głównym impulsem od najmłodszych lat.

„Od wczesnego dzieciństwa zawsze kochałem matematykę” - powiedział Wigderson. „Mój tata interesował mnie łamigłówkami i innymi rzeczami”.

Wigderson jest absolwentem izraelskiego Technion (Instytutu Technologii) oraz uzyskała stopnie magisterskie i doktoranckie w dziedzinie informatyki na Uniwersytecie Princeton. Poruszająca opowieść o jego doświadczeniach pojawia się w przemówieniu Wigdersona, który przyjął go w zeszłym roku, gdy otrzymał doktorat honoris causa od Technion.

„Naprawdę zależy mi na sformalizowaniu modeli obliczeniowych” - powiedział Wigderson o tym, co przyciąga jego zainteresowanie - „na przykład, czy jakiś protokół kryptograficzny jest bezpieczny lub czas działania jakiegoś algorytmu jest taki a taki.

„Fakt, że zajmuje się tym podstawowym pojęciem, ale w rzeczywistości jest dziedziną matematyczną, jest dla mnie bardzo cenny”.

Do osiągnięć, z których jest najbardziej dumny, powiedział Wigderson, należy jego praca nad udoskonaleniem tak zwanych „dowodów wiedzy zerowej”, w ramach których informacje można zachować w tajemnicy, ale mimo to dwie strony mogą osiągnąć porozumienie. „Powiedzmy, że coś wiem, wiem, kto wygra wybory, a ty mi nie wierzysz, a ja próbuję cię przekonać [że naprawdę wiem]. Jest sposób, aby cię przekonać, nie mówiąc ci o tym wszystko, czego jeszcze nie wiedziałeś.”

W rzeczywistości taki stan rzeczy leży u podstaw kryptografii klucza publicznego, w której każda ze stron ukrywa swój klucz prywatny, ale jest w stanie przekonać drugą, że na przykład autorytatywnie podpisała umowę elektroniczną. „To całkowicie paradoksalny pogląd” - powiedział Wigderson o takich dowodach z wiedzą zerową. „To coś, co wprawia cię w osłupienie, gdy pomyślisz, że coś takiego może istnieć”.

Intelekt Wigdersona równoważy zachwyt z żywym poczuciem leżącego u jego podstaw znaczenia. Na przykład pytanie, które problemy są w sposób udowodniony trudne, ma ogromne znaczenie dla społeczeństwa.

Sformułowane w latach 70. XX wieku wyrażenie „Czy P=NP?” zadaje pytanie, czy problem, którego rozwiązanie można zweryfikować, mógłby ostatecznie zostać rozwiązany również za pomocą równania wielomianowego w czasie - rozwiązany efektywnie. Jeśli tak, to prawdopodobnie można by zbudować komputer, który rozwiązałby w praktycznym czasie niektóre z pozornie nierozwiązywalnych problemów świata.

„To jedno z najbardziej podstawowych pytań intelektualnych, jakie kiedykolwiek zadano” - powiedział Wigderson z P=NP. Jego osobiste przypuszczenie, będące konsensusem w jego dziedzinie, jest takie, że P nie równa się NP, co oznacza, że niektórych problemów nie da się skutecznie rozwiązać.

„Jeśli wszyscy się mylą i P równa się NP, ma to niesamowite konsekwencje” - powiedział Wigderson. „Praktycznie każdy problem, który chcesz rozwiązać, możesz rozwiązać skutecznie - wszystko; możesz wyleczyć raka”.

Jednakże „Jeśli P nie równa się NP, konsekwencje dla rzeczy poza naszym zasięgiem są dość znaczące” - powiedział Wigderson. Po pierwsze oznaczałoby to, że niektóre elementy ludzkiego myślenia, takie jak kreatywność, mogą znajdować się poza zasięgiem komputerów, ponieważ nie ma sposobu, aby skutecznie symulować heurystyki, ludzkie poczucie rzeczy, które są wykorzystywane na przykład w twórczości artystycznej .

Ale w innym sensie szklanka jest do połowy pełna: jeśli problemów NP nie można skutecznie rozwiązać, oznacza to, że kryptografia - cała podstawa współczesnej gospodarki - jest zabezpieczona przed złamaniem, zauważył Wigderson.

To, czy P jest równe NP, czy nie, jest kwestią otwartą. „Miałem nadzieję, że ktoś to udowodni za mojego życia, ale teraz w to wątpię” - powiedział Wigderson.

Komputer kwantowy nie jest też łatwą odpowiedzią na ten impas. „Pomyśl o komputerze kwantowym: taki nie istnieje” - powiedział Wigderson. „Nie wiemy, czy kiedykolwiek będzie istnieć” - mimo że IBM, Google i inni intensywnie teoretyzują na ten temat.

Jeśli P=NP jest problemem otwartym, aktualne jest także pytanie: co sztuczna inteligencja - w tym maszyny „ogólnej sztucznej inteligencji” - może zrobić, aby dorównać ludzkim myślom? Z pewnością pogląd, że wszystko we wszechświecie wykonuje obliczenia, sugeruje, że sztuczna inteligencja powinna być w stanie osiągnąć pewną miarę ludzkich możliwości.

„My jesteśmy węglem, a oni krzemem, więc materiał jest inny, ale trudności wynikają z poziomu psychologicznego, a nie operacyjnego” - uważa Wigderson. Sztuczna inteligencja już pokazała, że „może rozwiązać wiele problemów, których wcześniej nie wiedzieliśmy, jak rozwiązać” - powiedział Wigderson. Zna „kilku wybitnych matematyków, którzy zaczynają używać tych urządzeń jako współpracownicy” przy dowodzeniu twierdzeń i tym podobnych.

„Bardziej interesujące jest dla mnie to, czego nie mogą zrobić” - powiedział. „Jakie są ograniczenia tego typu komputerów?” Jednym z tych ograniczeń jest względny niedobór danych wymaganych do uczenia modeli sztucznej inteligencji w przypadku niektórych problemów.

„Na przykład projektowanie nowej teorii matematycznej, takiej jak teoria względności lub Maxwell [równania Maxwella] - przykładów na to jest znacznie mniej, prawda? Myślę więc, że tego typu teoretyczny przełom będzie trudniejszy dla tych maszyn, ponieważ nie ma nie za dużo danych.”

Biorąc pod uwagę wiele konsekwencji tego, że P jest równe lub nierówne NP, Wigderson zadowala się pozostawieniem przewodnictwa nowemu pokoleniu.

„Bawię się z postdoktorami w instytucie i wszyscy są wspaniali. Z niektórymi z nich współpracuję i po prostu uczę się od młodych” - powiedział. „Bardzo miło jest być w takiej sytuacji otoczonej młodymi ludźmi, którzy pozwalają się uczyć”.