Takimi problemami – choć nie dosłownie – zajmuje się dr hab. Wojciech Czerwiński, prof. ucz., z Uniwersytetu Warszawskiego, laureat dwóch prestiżowych grantów Europejskiej Rady ds. Badań Naukowych. W rozmowie z Serwisem Naukowym UW opowiada o sieciach Petriego, czyli matematycznych modelach układów, w których wiele rzeczy dzieje się naraz, i tłumaczy, jak z prostego pytania o działanie systemu rodzi się problem tak trudny, że w grę wchodzą liczby, które przestają mieścić się w głowie.
Serwis Naukowy Uniwersytetu Warszawskiego: Sześć lat temu otrzymał Pan prestiżowy grant Europejskiej Rady ds. Badań Naukowych (ang. ERC – European Research Council), czyli ERC Starting Grant. Pana badania dotyczyły systemów nieskończenie stanowych. Czym jest ta dziedzina informatyki i nad czym Pan szczególnie pracował?
Prof. Wojciech Czerwiński: – Moje badania należą do dziedziny informatyki teoretycznej, która nazywa się teorią automatów. Automat to model obliczeń, czyli matematyczny, abstrakcyjny opis sposobu, w jaki system coś liczy.
Znanym przykładem jest maszyna Turinga. To podstawowy model używany do badania możliwości i ograniczeń algorytmów. Krótko mówiąc, maszyna Turinga jest modelem tego, czym jest program.
Można oczywiście dalej drążyć i zapytać, co to takiego ten „model”. Najprościej rzecz ujmując, to uproszczony opis rzeczywistości, zjawiska albo systemu. W fizyce tworzy się modele Wszechświata czy też modele działania atomu. Nie są to idealne, dokładne opisy, ale pomagają w przybliżony sposób zrozumieć, jak działa atom, galaktyka, albo na przykład zjawiska pogodowe czy dziedziczenie cech w genetyce.
Podobnie informatycy konstruują modele tego, co może zrobić program. A jeśli pewne rzeczy dzieją się równolegle, a nie w jakiejś kolejności, to modelem takiego systemu jest sieć Petriego.
To pojęcie pojawia się wiele razy w kontekście Pana pierwszego grantu ERC. Sieci Petriego były też w tytule jednego z Pana nagrodzonych artykułów. Czym właściwie są?
– Sieć Petriego to model systemu, w którym zjawiska dzieją się równolegle, a nie po kolei. Tak jest na przykład w programach współbieżnych.
Matematycznie stan takiego układu opisujemy za pomocą wielowymiarowego wektora. Każda jego współrzędna mówi, ile elementów o danej cesze znajduje się w systemie w danym momencie. Ponieważ rzeczy dzieją się równolegle, to przy jednym ruchu możemy zmienić więcej niż jedną współrzędną, ale w określony sposób.
Carl Adam Petri zainspirował się reakcjami chemicznymi. Chciał opisywać reakcje, które zachodzą równolegle, a nie jako kaskada zdarzeń.
Ale to nie jest ten Petri od szalki Petriego?
– Nie, to zbieżność nazwisk. Petri od sieci był XX-wiecznym informatykiem, a właściwie matematykiem. Zmarł w 2010 roku. Petri od szalek był XIX-wiecznym chemikiem i zmarł w 1921 roku. Choć ciekawostką jest, że Petri informatyk podobno zaczynał właśnie w laboratorium chemicznym.
W Pana badaniach współrzędne wspomnianego wektora to programy działające równolegle?
– Dokładnie. Mamy pewną liczbę programów pierwszego typu – opisuje to pierwsza współrzędna wektora. Liczbę programów drugiego typu opisuje druga współrzędna, i tak dalej. Te programy działają równolegle i mogą się ze sobą komunikować. I to jest model nieskończenie stanowy, bo konfiguracji może być dowolnie wiele.
Problem, który rozważałem, dotyczył tego, czy z danego stanu początkowego, przy zdefiniowanych przejściach, da się dojść do zadanego stanu. To właśnie jest problem osiągalności.
Sformułowanie jest proste. Od lat 80. XX wieku wiadomo było, że problem osiągalności jest rozstrzygalny, ale przez prawie pół wieku nie znano jego dokładnej złożoności. Innymi słowy: nie było wiadomo, jak szybko i z wykorzystaniem jakich zasobów pamięciowych można rozwiązać problem osiągalności – dojścia do żądanego stanu.
I tu dochodzimy do spektakularnego wyniku z pierwszego grantu ERC, dotyczącego złożoności obliczeniowej problemu osiągalności. Co udało się ustalić?
– Na początku znane były dolne i górne ograniczenia tej złożoności obliczeniowej. Dolnym ograniczeniem była wykładnicza pamięć. Oznacza to, że liczba potrzebnych komórek pamięci rośnie wykładniczo wraz z rozmiarem danych wejściowych. Górną granicą była tak zwana złożoność Ackermannowska. Jest potworna – olbrzymia.
Pierwszy duży wynik polegał na przesunięciu dolnej granicy na tak zwaną „wieżę dwójek”. Zwykle przez wieżę dwójek rozumie się 2 do 2 do 2 do … do 2, i tak n razy. To już jest straszna złożoność, a Ackermann jest jeszcze większy.
Drugi wynik to ponowne przesunięcie tej dolnej granicy – z „wieży dwójek” właśnie na Ackermanna. W ten sposób udowodniliśmy, że złożoność obliczeniowa problemu osiągalności jest Ackermannowska.
Dlaczego warto zajmować się tak „niepraktycznymi” pytaniami? Dlaczego ważne jest rozróżnienie na przykład między złożonością Ackermannowską a pamięcią wykładniczą?
– To jest tak naprawdę pytanie matematyczne. Chcieliśmy zrozumieć, jakie struktury rządzą algorytmem. Wiedza o jego złożoności dużo mówi nam o jego naturze. Prowokuje też do tego, żeby nadać odpowiednie pojęcia odpowiednim zjawiskom i zrozumieć, co dzieje się „w środku”.
To brzmi bardzo matematycznie, a nie informatycznie.
– Tak. Ludzie kojarzą informatykę i złożoność obliczeniową z tym, że przeciętny Kowalski otwiera komputer i coś mu tam działa szybko albo wolno. My patrzymy na rzeczy dość abstrakcyjne, które są piękne same w sobie. Nie wszystko musi mieć natychmiastową aplikację.
Można zatem powiedzieć, że zajmuje się Pan królową nauk w świecie jej młodszej siostry, informatyki.
– Tak, informatyka teoretyczna to właściwie matematyka. Matematyka obliczeń, matematyka procesów. Z jakiegoś powodu klasyfikuje się ją jako informatykę. Podobnie jest z logiką informatyczną. Przecież logika była działem matematyki, który z czasem przesunął się do informatyki.
W tym roku otrzymał Pan kolejny grant ERC, tym razem Consolidator Grant, na kontynuowanie badań nad osiągalnością. Projekt nosi tytuł POLARIS. Skąd ta nazwa?
– Lubię oglądać gwiazdy. Można też powiedzieć, że w pracy naukowej zajmuję się „nawigowaniem” z jednego stanu do innego. Polaris, czyli Gwiazda Polarna, od wieków pomagała w orientacji, stąd nazwa.
Jako ciekawostkę powiem, że Gwiazda Polarna nie zawsze była tak dokładnym punktem odniesienia jak dziś. Starożytni żeglarze musieli używać jakiejś innej gwiazdy do ustalenia kierunku północnego. To wynik tego, że przez powolną zmianę położenia osi obrotu Ziemi północny biegun niebieski przesuwa się na tle gwiazd. Dlatego kilka tysięcy lat temu najbliżej niego była inna gwiazda, i tak naprawdę ta inna gwiazda wskazywała północ.
W projekcie POLARIS kontynuuje Pan badania nad osiągalnością?
– Tak, bo ustalenie złożoności ogólnej nie kończy tematu. Naturalne jest pytanie o przypadki szczególne, przykładowo o wymiar 3.
Chcemy też tym razem zrozumieć, jak „zorganizowana” jest przestrzeń stanów, jakie są ukryte struktury w nieskończonych grafach i dlaczego problem osiągalności ma aż tak gigantyczną złożoność.
Grant ERC to prestiż, a równocześnie duże wsparcie finansowe. Na UW od kilku lat można zdobywać finansowanie dla różnych przedsięwzięć naukowych także w ramach programu IDUB – „Inicjatywa Doskonałości–Uczelnia Badawcza”. Skorzystał Pan z tego rodzaju funduszy?
– Ja jestem zatrudniony w grancie europejskim, ale w moim zespole był Henry Sinclair-Banks, post-doc z University of Warwick, który dzięki IDUBowi zorganizował warsztaty SAMSA.
Takie warsztaty o bardziej zawężonej tematyce to bardzo cenna rzecz. Konferencje zbierają naukowców z szerszej tematyki, więc służą ogólnemu zrozumieniu, co dzieje się w danej dziedzinie, ale to właśnie na warsztatach łatwiej spotkać badaczy zajmujących się podobnymi problemami i dzięki temu nawiązać naukową współpracę.
Henry był w Warszawie na post-docu ponad rok, napisaliśmy razem kilka prac, m.in. o problemie osiągalności w VASSach z dodatkowymi licznikami całkowitoliczbowymi lub o problemie osiągalności w pewnych klasach VASSów o bardzo szczególnej strukturze.
VASS to właściwie sieć Petriego, można o nim myśleć jako o specyficznej postaci sieci Petriego, która jest właściwie równoważna ogólnej postaci.
Dziękujemy za rozmowę.
Uczelnia Badawcza, czyli 5 pytań do… to cykl wywiadów z badaczkami i badaczami UW, którzy realizowali swoje projekty w ramach programu IDUB – „Inicjatywa Doskonałości – Uczelnia Badawcza”.
