Łatwo brzmiący problem daje liczby zbyt duże dla naszego Wszechświata | Magazyn Quanta

Nieczęsto zdarza się, że pięciolatki potrafią zrozumieć zagadnienia z pogranicza informatyki, ale może się to zdarzyć. Załóżmy na przykład, że przedszkolanka o imieniu Alicja ma dwa jabłka, ale woli pomarańcze. Na szczęście jej koledzy z klasy opracowali zdrowy system handlu owocami ze ściśle egzekwowanymi kursami wymiany: powiedzmy, zrezygnuj z jabłka, a dostaniesz banana. Czy Alicja może wykonać serię transakcji, zbierając i rozładowując banany lub melony, co doprowadzi ją do jej ulubionego owocu?

Brzmi to dość prosto. „Możesz pójść do szkoły podstawowej i powiedzieć to dzieciom” – powiedziała Christopha Haase’a, informatyk na Uniwersytecie Oksfordzkim. „Ludzie pomyślą: «To musi być łatwe»”.

Jednak problem matematyczny leżący u podstaw dylematu Alicji — zwany problemem osiągalności dla systemów dodawania wektorów — jest zaskakująco subtelny. Chociaż niektóre przypadki można łatwo rozwiązać, informatycy przez prawie pół wieku starali się uzyskać wszechstronne zrozumienie problemu. Teraz, w wyniku serii przełomowych odkryć dokonanych w ciągu ostatnich kilku lat, dokładnie ustalili, jak złożony może być ten problem.

Okazuje się, że ten dziecinny problem jest absurdalnie, wręcz karykaturalnie złożony – tak skomplikowany, jak praktycznie wszystkie inne słynne trudne problemy obliczeniowe wyglądać jak, cóż, dziecinna zabawa. Spróbuj określić ilościowo wysiłek wymagany do rozwiązania tego problemu, a wkrótce będziesz miał do czynienia z liczbami tak dużymi, że nawet policzenie ich cyfr sprawi, że sięgniesz po liczby, o których nigdy nie słyszałeś. Takie liczby często zachęcają do porównań ze skalą wszechświata, ale nawet te analogie są niewystarczające. „To nie byłoby sprawiedliwe” – powiedział Georg Zetzsche, informatyk w Instytucie Systemów Oprogramowania Maxa Plancka w Kaiserslautern w Niemczech. „Wszechświat jest taki mały.”

W zasięgu ręki?

Pozbawiony istoty problem osiągalności dotyczy obiektów matematycznych zwanych wektorami, które są uporządkowanymi listami liczb. Wpisy na tych listach nazywane są komponentami, a liczba komponentów wektora nazywana jest jego wymiarowością. Na przykład zapasy owoców Alicji można opisać czterowymiarowym wektorem (a, b, c, d), którego elementy reprezentują liczbę jabłek, bananów, melonów i pomarańczy, jakie ona ma w danym momencie.

System dodawania wektorów (VAS) to zbiór wektorów reprezentujących możliwe przejścia między stanami w systemie. Dla Alicji wektor przejściowy (-1, -1, 1, 0) reprezentowałby wymianę jabłka i banana na melon. Problem osiągalności VAS pyta, czy istnieje jakakolwiek kombinacja dozwolonych przejść, która może przenieść Cię z określonego stanu początkowego do określonego stanu docelowego — lub, mówiąc matematycznie, czy istnieje jakakolwiek suma wektorów przejścia, która przekształca wektor początkowy w wektor docelowy. Jest tylko jeden haczyk: żaden składnik wektora opisującego stan systemu nie może nigdy spaść poniżej zera.

„To bardzo naturalne ograniczenie modelu rzeczywistości” – powiedział Wojciech Czerwiński, informatyk na Uniwersytecie Warszawskim. „Nie możesz mieć ujemnej liczby jabłek.”

W niektórych systemach łatwo jest określić, czy wektor docelowy jest osiągalny. Ale nie zawsze tak jest. Informatyków najbardziej interesują proste systemy dodawania wektorów, w których nie jest oczywiste, jak trudno jest określić osiągalność. Aby zbadać te przypadki, badacze zaczynają od zdefiniowania liczby, która określa ilościowo rozmiar danego systemu. Liczba ta, reprezentowana przez n, obejmuje liczbę wymiarów, liczbę przejść i inne czynniki. Następnie pytają, jak szybko może wzrosnąć trudność problemu osiągalności n rośnie.

Aby odpowiedzieć na to pytanie, badacze stosują dwa uzupełniające się podejścia. Najpierw szukają przykładów szczególnie trudnych systemów dodawania wektorów, w których określenie osiągalności wymaga minimalnego wysiłku. Te minimalne poziomy nazywane są „dolnymi granicami” ze względu na złożoność problemu – mówią badaczom: „Najtrudniejsze systemy dla danego n są co najmniej tak trudne.

Po drugie, badacze próbują ustalić „górne granice” — granice tego, jak trudna może być osiągalność, nawet w najbardziej diabolicznych systemach. Mówią one: „Najtrudniejsze przypadki dla danego n są co najwyżej tak trudne. Aby dokładnie określić, jak trudna jest osiągalność w najtrudniejszych systemach, badacze próbują przesuwać dolne granice w górę i górne w dół, aż się spotkają.

Rzeczy koszmarów

Systemy dodawania wektorów mają długą historię. Od lat sześćdziesiątych XX wieku informatycy używają ich do modelowania programów, które dzielą obliczenia na wiele małych części i jednocześnie nad nimi pracują. Ten rodzaj „przetwarzania współbieżnego” jest obecnie wszechobecny, lecz badacze wciąż nie w pełni rozumieją jego matematyczne podstawy.

W 1976 roku informatyk Richarda Liptona zrobił pierwszy krok w kierunku zrozumienia złożoności problemu osiągalności VAS. Opracował procedurę konstruowania systemów, w której najszybszym sposobem ustalenia, czy jeden stan jest osiągalny z drugiego, jest odwzorowanie sekwencji przejść między nimi. To pozwoliło mu wykorzystać długość najkrótszej ścieżki między dwoma starannie wybranymi stanami jako miarę trudności problemu osiągalności.

Zatem Liptona okazały potrafił skonstruować system rozmiarów n w którym najkrótsza ścieżka między dwoma stanami obejmowała więcej niż przejścia $latex 2^{2^n}$. Oznaczało to odpowiednią podwójną wykładniczą dolną granicę wysiłku wymaganego do określenia osiągalności w jego systemach. To było zaskakujące odkrycie — podwójny wykładniczy wzrost to koszmar informatyków. Rzeczywiście, badacze często wzbraniają się nawet przed zwykłym wykładniczym wzrostem, który blednie w porównaniu: $latex {2^5}= 32$, ale $latex 2^{2^5}$ to ponad 4 miliardy.

Większość badaczy uważała, że ​​Lipton wymyślił najbardziej złożone możliwe systemy dodawania wektorów, co oznaczało, że podniósł dolną granicę tak wysoko, jak to było możliwe. W takim przypadku brakowałoby jedynie górnej granicy — to znaczy dowodu na to, że nie może istnieć system, w którym określenie osiągalności byłoby jeszcze trudniejsze. Ale nikt nie wiedział, jak to udowodnić. Informatyk Ernst Mayr był najbliżej, gdy on okazały w 1981 r., że w zasadzie zawsze można określić osiągalność w dowolnym systemie dodawania wektorów. Jednak jego dowód nie określił ilościowo górnej granicy tego, jak trudny może być problem. Była podłoga, ale nie było widać sufitu.

„Z pewnością myślałem o tym od czasu do czasu” – powiedziała Lipton. „Ale po pewnym czasie się poddałem i z tego, co widziałem, przez około 40 lat nikt nie zrobił żadnego postępu”.

W 2015 roku informatycy Jerome Leroux i Sylvaina Schmitza w końcu ustalone ilościową górną granicę – tak wysoki, że badacze przyjęli, że to dopiero pierwszy krok, który można zepchnąć w dół, aby osiągnąć dolną granicę Liptona.

Ale tak się nie stało. W 2019 roku badacze odkryli dolną granicę znacznie wyższą niż w przypadku Liptona, co wywróciło do góry nogami obiegowe opinie. Problem osiągalności VAS był znacznie bardziej złożony, niż ktokolwiek przewidywał.

Wieża Mocy

Szokujący wynik 2019 roku wyrósł z porażki. W 2018 roku Czerwiński obalił przypuszczenie Leroux i Filipa Mazowieckiego, informatyka obecnie na Uniwersytecie Warszawskim, co pomogłoby w poczynieniu postępów w powiązanym problemie. W trakcie kolejnych dyskusji badacze natknęli się na nowy, obiecujący sposób konstruowania wyjątkowo złożonych systemów dodawania wektorów, co mogłoby oznaczać nową dolną granicę problemu osiągalności VAS, w przypadku którego postęp tak długo pozostawał w martwym punkcie.

„W mojej głowie wszystko łączyło się z osiągalnością VAS” – wspomina Czerwiński. Podczas semestru o niewielkim obciążeniu dydaktycznym postanowił skupić się wyłącznie na tym problemie, wraz z Leroux, Mazowieckim i dwoma innymi badaczami — Sławomira Lasoty Uniwersytetu Warszawskiego i Ranko Lazić Uniwersytetu w Warwick.

Po kilku miesiącach ich wysiłki opłaciły się. Czerwińskiego i jego współpracowników wykazać że mogliby skonstruować systemy dodawania wektorów, w których najkrótsza droga między dwoma stanami była powiązana z rozmiarem układu za pomocą operacji matematycznej zwanej tetracją, która sprawia, że ​​nawet koszmarny podwójny wzrost wykładniczy wydaje się oswojony.

Tetracja jest prostym rozszerzeniem wzoru łączącego najbardziej znane operacje matematyczne, zaczynając od dodawania. Dodaj razem n kopii liczby, a wynik jest równoważny pomnożeniu tej liczby przez n. Jeśli pomnożysz przez siebie n kopie liczby, co jest równoznaczne z potęgowaniem lub podniesieniem liczby do nmoc. Tetracja, często reprezentowana przez parę strzałek skierowanych w górę, to kolejny krok w tej sekwencji: Tetracja liczby przez n oznacza to wyolbrzymianie n razy, aby stworzyć wieżę mocy n wysokie na piętra.

Trudno pojąć, jak szybko tetracja wymyka się spod kontroli: $latex 2 uparrowuparrow 3$ lub $latex 2^{2^2}$ to 16, $latex 2 uparrowuparrow 4$ to nieco ponad 65,000 2, a $latex 5 uparrowuparrow 20,000$ to liczba składająca się z prawie 2 6 cyfr. Fizycznie niemożliwe jest zapisanie wszystkich cyfr $latex XNUMX uparrowuparrow XNUMX $ – to obowiązek życia w tak małym wszechświecie.

W swoim przełomowym wyniku Czerwiński i jego współpracownicy udowodnili, że istnieją systemy dodawania wektorów wielkości n gdzie najlepszym sposobem określenia osiągalności jest wyznaczenie ścieżki obejmującej więcej niż przejścia $latex 2 uparrowuparrow n$, co oznacza nową dolną granicę, która przyćmiewa Liptona. Jednak choć tetracja była zawrotna, nie było to jeszcze ostatnie słowo na temat złożoności problemu.

Do Quinquagintilliona i nie tylko 

Zaledwie kilka miesięcy po szokującej nowej dolnej granicy złożoności osiągalności VAS, Leroux i Schmitz zepchnięty górnej granicy, którą ustalili trzy lata wcześniej, ale nie dotarli aż do tetracji. Zamiast tego udowodnili, że złożoność problemu osiągalności nie może rosnąć szybciej niż matematyczna potworność zwana funkcją Ackermanna.

Aby zrozumieć tę funkcję, dojdź do ponurego wniosku wzoru użytego do zdefiniowania tetracji. Następna operacja w sekwencji, zwana pentacją, reprezentuje powtarzającą się tetrację; po niej następuje kolejna operacja (hexacja) w celu powtórzenia pentacji i tak dalej.

Funkcja Ackermanna, oznaczona jako $latex A(n)$, otrzymasz, gdy przejdziesz o jeden stopień w górę tej drabiny operacji z każdym przystankiem na osi liczbowej: $latex A(1) = 1 + 1$, $latex A (2) = 2 × 2$, $lateks A(3) = 3^3$, $lateks A(4)=4 uparrowuparrow 4=4^{4^{4^4}}$ i tak dalej. Liczba cyfr w $latex A(4)$ sama w sobie jest kolosalną liczbą równą w przybliżeniu 1 kwinkwagintylionowi — to kapryśna i rzadko potrzebna nazwa jedynki, po której następują 1 zera. „Nie martw się o Ackermanna z piątki” – poradził Javiera Esparza, informatyk na Uniwersytecie Technicznym w Monachium.

Wynik Leroux i Schmitza pozostawił dużą lukę między dolną i górną granicą – dokładna złożoność problemu osiągalności VAS może leżeć na dowolnym końcu zakresu lub gdziekolwiek pomiędzy. Czerwiński nie miał zamiaru dopuścić do utrzymania tej luki. „Kontynuowaliśmy pracę nad tym, ponieważ było jasne, że to najważniejsza rzecz, jaką kiedykolwiek zrobiliśmy w życiu” – powiedział.

Ostateczny przełom nastąpił w 2021 roku, kiedy Czerwiński doradzał studentowi drugiego roku studiów licencjackich Łukaszowi Orlikowskiemu. Przypisał Orlikowskiemu prosty wariant problemu, aby go przyspieszyć, a praca Orlikowskiego pomogła im obojgu opracować nową technikę, która miała zastosowanie również do ogólnego problemu osiągalności. To im na to pozwoliło podnieść dolną granicę zasadniczo — aż do górnej granicy Ackermanna Leroux i Schmitza. Pracując niezależnie, Leroux uzyskał równoważny wynik W tym samym czasie.

Wreszcie badacze określili prawdziwą złożoność problemu osiągalności. Dolna granica Czerwińskiego, Orlikowskiego i Leroux pokazała, że ​​istnieje ciąg coraz większych układów dodawania wektorów, w których najkrótsza droga między dwoma stanami rośnie proporcjonalnie do funkcji Ackermanna. Górna granica Leroux i Schmitza pokazała, że ​​problem osiągalności nie może być bardziej złożony – to niewielka pociecha dla każdego, kto liczy na nieomylną, praktyczną procedurę jego rozwiązania. To uderzająca ilustracja tego, jak subtelne mogą być pozornie proste problemy obliczeniowe.

Nigdy nie skończone

Naukowcy kontynuowali badanie problemu osiągalności VAS po określeniu jego dokładnej złożoności, ponieważ wiele wariantów tego pytania pozostaje bez odpowiedzi. Na przykład górna i dolna granica Ackermanna nie rozróżniają różnych sposobów zwiększania n, takie jak zwiększenie wymiarowości wektorów lub zwiększenie liczby dozwolonych przejść.

Ostatnio Czerwiński i jego współpracownicy to zrobili Postępy rozróżnienie tych odrębnych efektów poprzez badanie, jak szybko może wzrosnąć złożoność w wariantach systemów dodawania wektorów o stałej wymiarowości. Jednak pozostaje jeszcze wiele do zrobienia — nawet w trzech wymiarach, gdzie systemy dodawania wektorów są łatwe do wizualizacji, dokładna złożoność problemu osiągalności pozostaje nieznana.

„W pewnym sensie jest to dla nas po prostu wstyd” – stwierdził Mazowiecki.

Naukowcy mają nadzieję, że lepsze zrozumienie stosunkowo prostych przypadków pomoże im opracować nowe narzędzia do badania innych modeli obliczeń, które są bardziej skomplikowane niż systemy dodawania wektorów. Obecnie o tych bardziej wyszukanych modelach nie wiemy prawie nic.

„Postrzegam to jako część bardzo fundamentalnego dążenia do zrozumienia obliczalności” – powiedział Zetzsche.

Quanta przeprowadza serię ankiet, aby lepiej służyć naszym odbiorcom. Weź nasze ankieta dla czytelników informatyki i zostaniesz wpisany, aby wygrać za darmo Quanta towar.