Wyobraź sobie, że starasz się zrozumieć samą naturę obliczeń. Jesteś głęboko na pustyni, z dala od wszelkich ścieżek i tajemniczy wiadomości są wyryte w pniach drzew wokół ciebie – BPP, AC⁰[m], Σ₂P, YACC i setki innych. Glify próbują ci coś powiedzieć, ale od czego zacząć? Nie możesz nawet utrzymać ich wszystkich prosto.

Niewielu badaczy dokonało tyle, co Russella Impagliazzo przebić się przez ten pozorny chaos. Przez 40 lat Impagliazzo stał na czele teorii złożoności obliczeniowej, czyli badania wewnętrznej trudności różnych problemów. Najsłynniejsze pytanie otwarte w tej dziedzinie, zwane problemem P kontra NP, dotyczy tego, czy wiele pozornie trudnych problemów obliczeniowych jest w rzeczywistości łatwych — przy użyciu odpowiedniego algorytmu. Odpowiedź miałaby daleko idące konsekwencje dla nauki i bezpieczeństwa współczesnej kryptografii.

W latach 1980. i 1990. Impagliazzo odegrało wiodącą rolę w ujednoliceniu teoretyczne podstawy kryptografii. W 1995 roku przedstawił znaczenie tych nowych osiągnięć w kultowym artykule, w którym przeformułowano możliwe rozwiązania problemu P w porównaniu z NP oraz kilka powiązanych problemów w języku pięć hipotetycznych światów moglibyśmy zamieszkać, kapryśnie nazwane Algorithmica, Heuristica, Pessiland, Minicrypt i Cryptomania. Pięć światów Impagliazzo zainspirowało całe pokolenie badaczy i nadal wyznacza kierunki badań w kwitnącej poddziedzinie: meta-złożoność.

A to nie jedyne światy, które wymyślił. Impagliazzo przez całe życie był miłośnikiem gier RPG, takich jak Dungeons and Dragons, i uwielbia wymyślać nowe zestawy zasad i nowe ustawienia do odkrycia. Ten sam duch zabawy ożywia jego 30-letnią praktykę w komedii improwizacyjnej.

Impagliazzo wykonał także fundamentalną pracę, wyjaśniając podstawową rolę losowości w obliczeniach. Pod koniec lat siedemdziesiątych informatycy odkryli, że czasami przyczyną może być przypadkowość ulepszyć algorytmy do rozwiązywania problemów z natury deterministycznych — odkrycie sprzeczne z intuicją, które przez lata wprawiało badaczy w zakłopotanie. Praca Impagliazzo z teoretykiem złożoności Aviego Wigdersona i inni badacze w latach 1990. wykazali, że jeśli pewne problemy obliczeniowe są rzeczywiście zasadniczo trudne, to zawsze możliwe do konwersji algorytmów wykorzystujących losowość na deterministyczne. I odwrotnie, udowodnienie, że losowość można wyeliminować z dowolnego algorytmu również by udowodnił że istnieją naprawdę trudne problemy.

Quanta rozmawiał z Impagliazzo o różnicy między trudnymi problemami a trudnymi łamigłówkami, konsultowaniu się z wyroczniami i matematycznymi lekcjami komedii improwizowanej. Wywiad został skrócony i zredagowany dla przejrzystości.

Kiedy po raz pierwszy zainteresowałeś się matematyką?

Zainteresowałem się matematyką, jeszcze zanim tak naprawdę wiedziałem, co to jest. W trzeciej klasie zaczęły mi się pogarszać oceny z matematyki, bo mieliśmy uczyć się na pamięć tabliczki mnożenia, a ja odmówiłam. Moja mama powiedziała: „Ale Russell, kochasz matematykę, dlaczego tego nie robisz?” A ja odpowiedziałem: „To nie jest matematyka, to zapamiętywanie. Prawdziwa matematyka nie wymaga zapamiętywania.” Jedyne, czego się wówczas nauczyłem, to arytmetyki, więc nie jestem pewien, skąd wziąłem pogląd, że matematyka dotyczy pojęć abstrakcyjnych.

A co z informatyką? Części tej dziedziny są bardzo abstrakcyjne, ale nie są tym, z czym większość ludzi spotyka się po raz pierwszy.

W szkole średniej miałem kurs programowania w języku BASIC, ale naprawdę ciężko było mi cokolwiek zrobić. Programy trzeba było przenieść na taśmy papierowe, które trzeba było przepuszczać przez ten bardzo stary komputer, który często ulegał awariom i rozdzierał papier na pół. Więc pomyślałem, że informatyka jest strasznie nudna.

Zamierzałem studiować logikę. Jednak wiele koncepcji, gdy próbowało się je sformalizować, wiązało się z obliczeniami, a zwłaszcza ograniczeniami obliczeń. Pytania typu „Skąd wiemy, że rzeczy w matematyce są prawdziwe?” oraz „Jak rozumiemy trudność wykonywania matematyki?” doprowadziło do informatyki teoretycznej, a zwłaszcza teorii złożoności.

Niektóre z Twoich najsłynniejszych prac badają powiązania między kryptografią a teorią złożoności obliczeniowej. Dlaczego te dwie dziedziny są ze sobą powiązane?

Konfigurując system kryptograficzny, musisz rozróżnić legalnych użytkowników — osoby, którym chcesz przyznać dostęp — i wszystkich innych. Problemy trudne obliczeniowo pozwalają nam rozróżnić te grupy na podstawie ich wiedzy. Ale jeśli chcesz, aby znajomość odpowiedzi na problem była sposobem na rozróżnienie dwóch grup ludzi, nie możesz po prostu użyć żadnego trudnego problemu — potrzebujesz trudnej łamigłówki.

Jaka jest różnica między problemem a łamigłówką?

Ogólnie rzecz biorąc, osoba stwarzająca problem może nie znać odpowiedzi. Zagadka to problem zaprojektowany z myślą o odpowiedzi. Dlaczego więc potrzebujemy łamigłówki? Ponieważ musimy być w stanie ustalić, czy osoba, która rzekomo rozwiązała problem, faktycznie to zrobiła. Na co dzień używamy puzzli dla rozrywki, ale używamy ich także na lekcjach, aby sprawdzić, czy ludzie zrozumieli materiał. Tak właśnie dzieje się w kryptografii: używamy łamigłówek, aby sprawdzić czyjąś wiedzę.

Różnica między pięcioma światami polega na tym, jak odpowiadają na pytania: „Czy istnieją trudne problemy?” i „Czy są trudne łamigłówki?”

Jak te różne odpowiedzi mają się do siebie?

W pierwszym świecie Algorithmica żadne problemy nie są trudne. Nie musisz wiedzieć, jak ktoś zaprojektował Twój problem: zawsze możesz go rozwiązać. Heurystyka mówi: „No cóż, może kilka problemów jest trudnych”. Następnie docieramy do Pessilandu, gdzie wiele problemów jest trudnych, ale większość zagadek nie. Prawie każdy problem, który wymyślę i znam rozwiązanie, ty też będziesz w stanie go rozwiązać. Wszystkie te światy są złe dla kryptografii.

W Minicrypt mogę tworzyć łamigłówki, które znam, a które nadal stanowią dla Ciebie duże wyzwanie. I wreszcie Cryptomania to świat, w którym dwie osoby mogą stanąć w miejscu publicznym, gdzie podsłuchujący może słyszeć i wspólnie ułożyć puzzle, które wciąż są dla niego trudne.

Co skłoniło Cię do napisania artykułu o pięciu światach?

W tamtym czasie było wiadomo, że różne odpowiedzi na pytanie P i NP będą miały duży wpływ na to, jakiego rodzaju problemy możemy rozwiązać i na jakiego rodzaju bezpieczeństwo możemy liczyć, ale jakościowe rozróżnienie pomiędzy różnymi formami łatwości i twardość nie była zbyt wyraźna.

Zaledwie kilka lat wcześniej ukazał się bardzo wnikliwy artykuł, w którym przedstawiono rozróżnienia za pomocą wielu powiązanych ze sobą pytań i około 20 możliwych odpowiedzi. Jednym z powodów, dla których chciałem napisać artykuł o pięciu światach, był fakt, że w ciągu tych kilku lat poczyniliśmy ogromne postępy. Trudno byłoby znaleźć nazwy dla 20 możliwych światów.

Dlaczego więc przedstawiać to w ten sposób, jako różne światy o dziwacznych nazwach?

Zgodziłem się napisać ten artykuł na konferencję. Nie spałem do późna w nocy, próbując wymyślić, co powiem, i gdzieś około pierwszej w nocy kadrowanie różnych światów wydawało się dobrym pomysłem. A potem przeczytałem to następnego ranka i nadal wydawało mi się to w porządku – był to sposób na pokazanie, jak te pomysły faktycznie wpłyną na świat, bez wdawania się w szczegóły ilościowe. Najbardziej cieszę się z tej pracy, gdy słyszę od osób prowadzących badania nad złożonością, że to właśnie dzięki niej zainteresowali się tą dziedziną jako studenci.

Czy badacze wykluczyli którykolwiek z pięciu możliwych światów?

Właściwie dodajemy więcej – ludzie zaczęli o tym mówić Obfustopia jako świat jeszcze silniejszych narzędzi kryptograficznych. To trochę przygnębiające, że pod koniec lat 1980. poczyniliśmy tak duży postęp i od tego czasu nie wyeliminowaliśmy żadnego świata. Ale z drugiej strony wiemy dużo więcej o powiązaniach między światami i mamy znacznie wyraźniejszy obraz tego, jak wyglądałby każdy świat.

Hipotetyczne światy odgrywają także inną rolę w teorii złożoności, w dowodach zakładających istnienie „wyroczni”. Po pierwsze, czym właściwie jest wyrocznia?

Wyobraź sobie, że ktoś buduje genialne urządzenie, które może rozwiązać jakiś problem bez znajomości algorytmu rozwiązania tego problemu. To właśnie jest wyrocznia. Gdybyśmy mieli takie cudowne urządzenie i umieścili je w naszych komputerach, mogłoby się przesunąć tam, gdzie znajduje się granica między tym, co można obliczyć, a tym, czego nie można obliczyć.

Czy badacze uważają, że te magiczne pudełka mogą rzeczywiście istnieć?

Nie, prawdopodobnie ich nie ma. Na początku wyniki Oracle były nieco kontrowersyjne, ponieważ były hipotetyczne. Ale jednym ze sposobów, w jaki mogą być bardzo pouczające, jest użycie wyroczni do modelowania idealnej sytuacji. Załóżmy, że próbujesz pokazać, że A niekoniecznie implikuje B. Zaczynasz od ustawienia, w którym masz najbardziej ekstremalne A i pokazujesz, że to wciąż nie wystarczy, aby zagwarantować B. Jeśli możesz to wykazać, nawet jeśli wszystkie szanse są równe na twoją korzyść nadal nie możesz czegoś udowodnić, to naprawdę mocny dowód, który będzie trudny do udowodnienia.

Odkryłeś także powiązania między twardością obliczeniową a losowością. Jak działa to połączenie?

To tak naprawdę powiedzenie, że jeśli czegoś nie rozumiesz, może się to wydawać przypadkowe. Załóżmy, że powiem, że myślę o liczbie od jednego do tysiąca. Jeśli wybiorę liczbę losowo, masz szansę odgadnięcia jednej na tysiąc. A jeśli zapytam – za Monty Pythonem – „Jaka jest średnia prędkość lotu europejskiej jaskółki w milach na godzinę?” masz mniej więcej takie same szanse. Prawdopodobnie jedzie więcej niż jedną milę na godzinę i prawdopodobnie nie przekracza tysiąca mil na godzinę.

W rzeczywistości nie jest to przypadkowe — jest to pytanie, na które można odpowiedzieć deterministycznie. Moglibyśmy po prostu zmierzyć wszystkie latające jaskółki, ale jest to dość trudne do określenia przy ograniczonych zasobach, takich jak brak budżetu na pomiar prędkości połykania lub brak nieskończonej liczby jaskółek.

Wniosek jest taki, że trudne problemy, których rozwiązań nie znamy, mogą stanowić źródło liczb „pseudolosowych”, które wyglądają na losowe.

A skoro mowa o Monty Pythonie, wiem, że zajmujesz się komedią improwizowaną już od dłuższego czasu – jak to się zaczęło?

Zacząłem jako adiunkt w San Diego w 1991 roku. Mniej więcej w 94 roku pomyślałem: „Naprawdę nie mam zbyt wiele życia poza wydziałem”. Dostałem więc darmowy tygodnik i przejrzałem listę klubów i zajęć. Wyeliminowałem wszystko z wyjątkiem komedii improwizowanej – myślałem, że przynajmniej będzie prawdopodobne, że poradzę sobie w tym. Poznałem moją żonę na zajęciach dla początkujących.

Co o tym myślała?

Mówi, że byłem naprawdę okropny. Kiedy jesteś logikiem, jesteś wyszkolony, aby zawsze myśleć o niuansach każdego słowa. Nie chcesz powiedzieć czegoś niewłaściwego. Impro jest świetne, ponieważ odwraca tę sytuację: nie chodzi o to, żeby powiedzieć coś idealnego, ale o to, żeby coś szybko wymyślić. To było przeciwieństwo reszty mojego życia.

Moja obecna żona zrobiła sobie przerwę od zajęć i kiedy wróciła rok później, udało mi się jej zaimponować. To było 30 lat temu. Nadal chodzę na te same zajęcia z tym samym instruktorem.

Czy improwizacja zmieniła sposób, w jaki podchodzisz do swoich badań?

Dobrą praktyką jest to, by nie być przesadnie krytycznym w stosunku do każdej myśli, jaką masz. Jest to szczególnie pomocne we współpracy. Pracując z innymi ludźmi, zwykłem mówić takie rzeczy: „Ale ten pomysł nie zadziała z następującego powodu. To nie jest dosłownie prawda.” W improwizacji zawsze należy akceptować to, co mówi partner. Myślę, że to dobre podejście, zwłaszcza gdy prowadzisz badania ze studentami: nie lekceważ czegoś, co mówią tylko dlatego, że wiesz, że jest to błędne. Jest wiele dobrych pomysłów, które nie są w 100% poprawne.

Jak co?

Kiedy próbujesz wyczuć problem, pomocne jest rozpoczęcie od upraszczających założeń. Założenia te zwykle nie są prawdziwe, ale mogą pomóc w opracowaniu planu działania. Powiedz: „Gdybym miał słonia, mógłbym przedostać się przez góry. Oczywiście, że nie mam słonia. Ale gdybym tak zrobił, oto jak bym to zrobił. I wtedy zdajesz sobie sprawę: „No cóż, może nie potrzebuję słonia do tego kroku. Muł byłby w porządku.

A co z Twoją miłością do gier RPG – czy wpłynęło to w ogóle na Twoją pracę?

Być może nie miało to wpływu na wszystkie moje badania, ale z pewnością miało wpływ na moją pracę o pięciu światach. Zawsze ogólnie interesowałem się fantasy i science fiction oraz wymyślaniem różnych możliwych światów – jak by wyglądały, gdyby wszystko było inne?

Dlaczego gry RPG są tak fascynującym sposobem na odkrywanie hipotetycznych światów?

Ludzie, którzy interesują się fikcją spekulatywną, zawsze wymyślali światy. Tolkien jest z tego najbardziej znany i miał tak ogromną wyobraźnię, że wydawało się, że jego świat rzeczywiście żyje. Dla tych z nas, którzy nie mają tyle wyobraźni, najlepszym sposobem na osiągnięcie tego jest zaproszenie ludzi do swojego otoczenia i gry jest na to sposób. Teraz to nie tylko mój świat. Być może zaczęło się tak, jak to sobie wyobrażałem, ale tak jak w przypadku każdej współpracy, dzięki wkładowi wszystkich innych, ewoluowało to znacznie dalej.