Delta mi!

Jakiś czas temu koleżanki i koledzy z redakcji Delty poprosili mnie, żebym opisał, czym zajmuję się naukowo, i przedstawił pewien ciekawy wynik, który udało mi się wraz ze współpracownikami niedawno uzyskać. Pisząc ten tekst, postaram się przybliżyć tę właśnie dziedzinę, która mi osobiście wydaje się interesująca chyba dlatego, że rozważa problemy o bardzo prostym sformułowaniu geometrycznym, a mimo to jest w niej więcej znaków zapytania niż odpowiedzi. Badania często okazują się ciekawą kombinatoryką, popartą jednak zwykle geometrycznymi intuicjami. Wiele fundamentalnych pytań otwartych można sformułować bardzo szybko, jedno z nich przybliżę na końcu tego tekstu.

Jak dobrze wiemy, żyjemy w wyjątkowym okresie w dziejach, w którym dostęp do informacji jest niesłychanie łatwy, i w zasadzie z roku na rok ułatwienia w tym zakresie zwiększają się. Z pewnością tym bardziej zwiększą się one w bieżącym roku - 2020. Podobnie jest z ilością danych, zbieramy ich coraz więcej. Gromadzimy olbrzymie ilości zdjęć, muzyki, filmów, ale również i innych danych, takich jak teksty, wszelkiego rodzaju informacje o ruchu w sieci itd. Przykładowo w ciągu każdej minuty na serwis YouTube wrzucanych jest około 500 godzin filmów. Powstała nawet dziedzina badań zajmująca się analizą dużych danych, zwana z angielska Big Data...

... Uważam, że jednostronnicowy dowód Sergeya Sevastianova jest wyjątkowy. Pál Erdős często odwoływał się do Księgi, w której Bóg trzyma wszystkie najelegantsze dowody. Zainspirowani tym matematycy, Aigner i Ziegler, wydali znakomitą książkę Dowody z Księgi, którą wszystkim szczerze polecam. Dowód Sevastianova mógłby również trafić do tej Księgi. Mimo że ja i moi koledzy rozumiemy każdy krok tego dowodu z osobna, to nie wiemy, skąd bierze się taki sposób rozumowania, niespotykany nigdzie indziej w naszej dziedzinie. Wierzę, że zrozumienie idei ukrytych w tym dowodzie może przyczynić się do kolejnych ciekawych wyników. Kto wie, może ktoś z Czytelników pomoże?

"No dobrze, ale jakie to ma zastosowanie?" - to pytanie słyszałem wiele razy podczas rozmów ze znajomymi, którym próbowałem wytłumaczyć, czym się zajmuję. I z pewnością podobne pytania słyszą setki tysięcy naukowców na całym świecie. Nie lubimy tych pytań, bo - powiedzmy to sobie szczerze - sami czasem nie umiemy powiedzieć, czy nasza praca w ogóle ma sens. Można zapytać szerzej - czy w ogóle nauki teoretyczne mają sens? Czy nie można byłoby wykorzystać możliwości setek tysięcy wykształconych i inteligentnych osób dużo lepiej niż do dłubania przez całe życie w jakichś egzotycznych pytaniach - wydumanych i niespecjalnie związanych z funkcjonowaniem innych ludzi?

Jak mierzyć trudność problemów? Trudność albo, inaczej mówiąc, ich skomplikowanie, złożoność. To nie jest łatwe pytanie. Aby móc na nie chociaż nieco sensownie odpowiedzieć, skupimy się tu na tzw. problemach decyzyjnych, czyli takich, na które odpowiedź zawsze brzmi "tak" lub "nie". Żeby określić, jak złożone są te problemy, przyjmuje się zasadę, że problem jest tak trudny, jak jego najlepsze rozwiązanie. Innymi słowy mówimy, że złożoność problemu jest równa złożoności najlepszego algorytmu, który go rozwiązuje.

Żeby przedstawić problem otwarty, o którym chcemy opowiedzieć, przypomnimy intuicję stojącą za pojęciem automatu skończonego, które zresztą niedawno pojawiło się w migawce informatycznej w Delcie 5/2018.

Dziś modeluje się prawie wszystko. Przykładowo prognozę pogody tworzy się na podstawie modelu atmosfery. Przestrzeń nad ziemią dzieli się na prostopadłościany szerokości kilku kilometrów, wysokości kilkudziesięciu, może kilkuset metrów; w każdym z nich ustala się, jaka jest temperatura, wilgotność, ciśnienie, prędkość wiatru, jego kierunek i jeszcze wiele innych parametrów. Taki opis sytuacji to stan modelu. Ponadto opierając się na prawach fizyki, ustala się, jak ten stan będzie ewoluował w czasie. To, oczywiście, będzie przybliżenie sytuacji rzeczywistej. Na przykład, liczymy, w jakim stanie model będzie za 12 godzin, dobę, dwie. Często takie obliczenia wymagają wielkiej mocy obliczeniowej, szczególnie jeśli chcemy zrobić to dokładnie, jak np. w przypadku prognozy ICM (meteo.pl).

Wielu Czytelników z pewnością zna grę Dobble. Zestaw do gry składa się z wielu okrągłych kart, na każdej z nich jest 8 różnych rysunków. Każde dwie karty zawierają dokładnie jeden wspólny symbol. Gra, w skrócie, polega na tym, żeby jak najszybciej dostrzec ten wspólny symbol.

Każdy chyba, nawet zupełnie nieznający się na informatyce, zgodzi się, że lepiej, żeby programy działały szybko niż wolno. Tylko co to znaczy szybko?

W 1994 roku Peter Shor, pracujący wówczas w Bell Labs w New Jersey, pokazał, jak przy użyciu hipotetycznego komputera kwantowego rozłożyć w czasie wielomianowym dowolną liczbę naturalną na czynniki pierwsze. W tamtym czasie algorytmy kwantowe dopiero raczkowały. To właśnie odkrycie Shora spowodowało wielki rozwój tej dziedziny. Społeczność informatyków zrozumiała, że gdyby udało się zbudować komputer kwantowy rozsądnej wielkości, to świat stałby się istotnie inny. Nie jest bowiem znany żaden algorytm dla problemu faktoryzacji, czyli rozkładu na dzielniki pierwsze, który działa w czasie wielomianowym na komputerze klasycznym. Co więcej, nawet nie znaleziono algorytmu losowego, który z dużym prawdopodobieństwem w zazwyczaj niedługim czasie faktoryzuje liczbę: nie jest po prostu znana zupełnie żadna rozsądna heurystyka...

24 maja 2000 roku Instytut Matematyczny Claya ogłosił listę siedmiu Problemów Milenijnych, czyli zagadnień, które zostały uznane za najważniejsze otwarte problemy matematyczne opierające się rozwiązaniom od lat. Wśród nich był jeden problem zaliczany do informatyki teoretycznej, o którym wielu Czytelników zapewne słyszało. Chodzi oczywiście o tytułowy problem: "Czy P=NP"? Jest on powszechnie uznawany za najważniejsze pytanie informatyki teoretycznej.

Wydaje się, że postęp naszej cywilizacji dokonuje się głównie w ten sposób, że coś nowego umiemy, my, ludzie, skonstruować czy dokonać. Przykłady można mnożyć, podróżując poprzez wieki, widzimy: rozpalanie ognia, budowę koła, wytapianie brązu i żelaza, budowę murów warownych, wynalazek prochu, leczenie nowych chorób, udoskonalenie druku, budowę statków dalekomorskich, wreszcie wynalazki maszyny parowej, radia, ostatnio tranzystory i następujące po nich komputery, energia jądrowa, czy wynalazek wielkiej światowej sieci łączności - Internetu.

O trudnym problemie, który ma jednozdaniowe rozwiązanie...

W dzisiejszym świecie cyfrowym mamy do czynienia z olbrzymią ilością danych, wielu Czytelników słyszało zapewne modne ostatnio hasło "Big Data". I trzeba sobie z tym radzić, a problemy mogą pojawiać się w nieoczekiwanych miejscach. Przyzwyczajeni jesteśmy do myślenia, że programy mają pewne dane na wejściu i te dane są tam na stałe, program może je w dowolnym momencie przeczytać. Czasami jednak nie do końca przystaje to do rzeczywistości...

W informatyce losowość jest bardzo przydatna. Często bardzo ułatwia rozumowania, pozwala na piękne i klarowne argumenty używające, na przykład, metody probabilistycznej. Nieraz łatwo znaleźć algorytm używający losowości (randomizowany) i działający szybko, podczas gdy znalezienie szybkiego algorytmu deterministycznego jest trudne lub w ogóle takiego nie znamy. Z losowością jest jednak pewien problem...

Czy już naprawdę nawet w Delcie musi być o seksie? Sytuacja wygląda trochę jak rozprawa "Słoń a Polska", przy czym w XIX wieku niektórym wszystko kojarzyło się ze sprawą polską, a teraz z czymś nieco innym. Zaniepokojonych Czytelników spieszymy uspokoić, że rzeczy nie mają się aż tak źle, bo artykuł naprawdę dotyczy rozmnażania płciowego i informatyki.

Mam pewien sekret, może lepiej nawet powiedzieć: tajemnicę. Nie mogę sobie pozwolić, żeby ktoś ją poznał. Sprawa jest poważna, ujawnię ją dopiero za pewien czas, gdy tylko Świat będzie na to gotowy. Może to rozwiązanie pewnego ważnego problemu matematycznego, zresztą, nie będę dzwonił kluczami do tajemnic. W każdym razie nie mogę sobie również pozwolić, żeby na wypadek mojej śmierci ta informacja przepadła bezpowrotnie. Co robić?

Czy każdy problem da się rozwiązać? Pesymiści odpowiedzą, że nie - życie nie jest łatwe. A optymiści? Być może niektórzy powiedzą, że przy odpowiednim podejściu tak. Nie będziemy jednak z nimi dyskutować, bo Czytelnicy Delty dobrze wiedzą, że nie chodzi nam tutaj przecież o życiowe problemy. Trzeba więc sprecyzować pytanie: co uważamy za problem i czym miałoby być jego rozwiązanie?

Najwytrwalsi Czytelnicy Delty mogą znać tę zagadkę. Pojawia się ona w wielu wariantach, my zajmiemy się wersją błotną.

"W takich Niemczech to mają dobre drogi, a w Polsce... No cóż, średni czas potrzebny na przejazd np. z Warszawy do Rzeszowa jest stanowczo za długi." Wielu Czytelników zapewne zgodzi się z tym stwierdzeniem lub doda, że jest zbyt eufemistyczne, inni zaś powiedzą, że przecież nie jest znowu aż tak źle. Z kolei ktoś może konstruktywnie zaproponować, żeby zamiast zastanawiać się, jak jest, zastanowić się, co zrobić, by było lepiej.

Algorytm to sposób rozwiązania pewnego problemu. Informatyka i matematyka od dawna badają różnego rodzaju problemy, szukając dla nich algorytmów, najczęściej możliwie szybkich. My jednak tym razem postąpimy wręcz przeciwnie: zajmiemy się algorytmami wyjątkowo wolnymi.

Chyba wszyscy lubimy liczby pierwsze. Szczególne wrażenie robią te naprawdę duże, wydają się skrywać w sobie jakąś nadzwyczajną tajemnicę: dlaczego akurat one stały się swego rodzaju wybrańcami spośród innych liczb i mają tak niezwykłe właściwości?

Bolek i Lolek zdecydowali się zagrać w ryzykowną grę. Mają do dyspozycji czekoladę, podzieloną na małe kwadratowe kawałki. Nie jest to jednak zwyczajna czekolada – jej lewy dolny kwadrat jest zatruty. Ruch polega na wybraniu jednego niezjedzonego jeszcze kawałka oraz zjedzeniu go wraz ze wszystkimi znajdującymi się wyżej lub bardziej na prawo od niego (czyli podczas wykonywania ruchu trzeba zjeść przynajmniej jeden kawałek czekolady).