Badacz opracowuje nowe narzędzie do zrozumienia trudnych i pozornie nierozwiązywalnych problemów obliczeniowych

Pomysł, że niektóre problemy obliczeniowe w matematyce i informatyce mogą być trudne, nie powinien być zaskoczeniem. W rzeczywistości istnieje cała klasa problemów, których matematyczne rozwiązanie uważa się za niemożliwe. Poniżej tej kategorii znajduje się kilka „łatwiejszych” problemów, które nie są dobrze rozumiane – a mogą być również niemożliwe.

David Jamarnik, profesor badań operacyjnych w MIT Sloan School of Management oraz w Instytucie Danych, Systemów i Społeczeństwa, skupia swoją uwagę na tej drugiej kategorii mniej zbadanych problemów, które są bardziej istotne dla codziennego świata, ponieważ dotyczą Losowy— integralna cecha systemów naturalnych. Wraz z kolegami opracowali potężne narzędzie do analizy tych problemów, zwane właściwością nakładającej się luki (ang. OGP). Gamarnik opisał nową metodologię w niedawnym artykule badawczym w: Materiały Narodowej Akademii Nauk.

P NP

Pięćdziesiąt lat temu sformułowano najsłynniejszy problem informatyki teoretycznej. P ≠ NP pyta, czy istnieją problemy związane z ogromnymi zbiorami danych, których odpowiedź można stosunkowo szybko zweryfikować, ale których rozwiązanie – nawet przy pracy na najszybszych dostępnych komputerach – zajęłoby absurdalnie dużo czasu.

Hipoteza P ≠ NP pozostaje nieudowodniona, jednak większość informatyków uważa, że ​​wiele znanych problemów – w tym na przykład problem komiwojażera – należy do tej niemożliwie trudnej kategorii. Wyzwaniem w przykładzie sprzedawcy jest znalezienie najkrótszej trasy, pod względem odległości lub czasu, przez N różnych miast. Zadanie jest łatwe w zarządzaniu, gdy N = 4, ponieważ istnieje tylko sześć możliwych ścieżek do rozważenia. Ale w 30 miastach jest ich ponad 10³⁰ możliwych sposobów, a od tego momentu liczby rosną wykładniczo. Największa trudność polega na zaprojektowaniu pliku algorytm Rozwiązuje problem szybko we wszystkich przypadkach, dla wszystkich liczb całkowitych N., informatycy są przekonani, w oparciu o teorię złożoności obliczeniowej, że nie ma takiego algorytmu, potwierdzającego, że P ≠ NP.

Istnieje wiele innych przykładów takich trudnych do rozwiązania problemów. Załóżmy na przykład, że masz ogromną tabelę liczb z tysiącami wierszy i tysiącami kolumn. Czy potrafisz znaleźć, ze wszystkich możliwych kombinacji, dokładny układ dziesięciu wierszy i 10 kolumn, tak aby ich sto wpisów miało najwyższą możliwą do osiągnięcia sumę? „Nazywamy je zadaniami optymalizacyjnymi, ponieważ zawsze próbujesz znaleźć największe lub najlepsze — największą sumę liczb, najlepszą trasę przez miasta itp.” — mówi Jamarnik.

Informatycy od dawna zdali sobie sprawę, że nie da się stworzyć szybkiego algorytmu, który we wszystkich przypadkach rozwiąże problemy tak skutecznie, jak saga komiwojażera. „Prawdopodobnie taka rzecz byłaby niemożliwa z dobrze rozumianych powodów” – zauważa Jamarnik. „Ale w prawdziwym życiu natura nie generuje problemów z wrogiej perspektywy. Nie próbuje frustrować cię precyzyjnie wybranym, najtrudniejszym problemem, jaki można sobie wyobrazić”. W rzeczywistości ludzie zwykle napotykają problemy w bardziej przypadkowych i mniej zarządzanych okolicznościach i są to problemy, które ma rozwiązać Partnerstwo Otwartego Rządu.

Szczyty i doliny

Aby zrozumieć, o co chodzi w Partnerstwie Otwartego Rządu, pomocne może być najpierw zobaczenie, jak powstał ten pomysł. Od lat 70. fizycy badali szkło spinowe – materiały, które mają właściwości zarówno cieczy, jak i ciał stałych, które mają niezwykłe właściwości magnetyczne. Badania nad szkłami spinowymi dały początek ogólnej teorii złożonych systemów związanych z problemami fizyki, matematyki, informatyki, materiałoznawstwa i innych dziedzin. (Dzięki tej pracy Giorgio Baresi otrzymał Nagrodę Nobla w dziedzinie fizyki w 2021 r.)

Jednym z mylących problemów, z jakimi borykali się fizycy, jest próba przewidzenia stanu energetycznego, w szczególności konfiguracji o najniższej energii, różnych wirujących struktur szklanych. Sytuacja jest czasami przedstawiana w „krajobrazu” niezliczonych górskich szczytów oddzielonych dolinami, gdzie celem jest zlokalizowanie najwyższego szczytu. W tym przypadku najwyższy szczyt w rzeczywistości reprezentuje stan o najniższej energii (chociaż można zamiast tego odwrócić obraz i poszukać najgłębszej dziury). Okazuje się, że jest to problem optymalizacyjny podobny w formie do dylematu komiwojażera, Jamarnik wyjaśnia: „Masz ten ogromny zestaw gór i wydaje się, że jedynym sposobem na znalezienie wyższych jest wspinanie się na każdą z nich” – absurdalny obowiązek podobny do znalezienia igły w stogu siana.

Fizycy pokazali, że można uprościć ten obraz i zrobić krok w kierunku rozwiązania, wycinając góry na określoną z góry wysokość i ignorując wszystko poniżej tego poziomu odcięcia. Następnie pozostawisz grupę widocznych szczytów nad jednolitą warstwą chmur, przy czym każdy punkt w tych szczytach reprezentuje potencjalne rozwiązanie pierwotnego problemu.

W artykule badawczym z 2014 r. Jamarnik i współpracownicy zauważają coś, co wcześniej przeoczono. W niektórych przypadkach zdali sobie sprawę, że średnica każdego piku byłaby znacznie mniejsza niż odległości między różnymi pikami. Tak więc, gdyby wybrać dowolne dwa punkty na tym rozległym krajobrazie – to znaczy dwa możliwe „rozwiązania” – byłyby one albo bardzo blisko (jeśli pochodziły z tego samego szczytu), albo bardzo daleko od siebie (jeśli zostały zaczerpnięte z różnych szczytów). . Innymi słowy, w tych odległościach będzie charakterystyczna „luka” – mała lub duża, ale nic pomiędzy. Jamarnik i współpracownicy zasugerowali, że system w tym przypadku charakteryzuje się OGP.

„Odkryliśmy, że wszystkie znane problemy o trudnym obliczeniowo losowym charakterze mają pewną wersję tej własności” – tzn. średnica góry w schematycznym modelu jest znacznie mniejsza niż odległość między górami – zapewnia Jamarnik. „To zapewnia dokładniejszy pomiar odporności algorytmu”.

Odkrywanie tajników złożoności algorytmów

Pojawienie się OGP może pomóc naukowcom ocenić trudność tworzenia szybkich algorytmów do rozwiązywania konkretnych problemów. To już umożliwiło im „matematycznie [and] Zdecydowanie wykluczył dużą klasę algorytmów jako potencjalnych konkurentów” – mówi Jamarnik. W szczególności nauczyliśmy się, że stabilne algorytmy – te, których dane wyjściowe niewiele się zmienią, jeśli dane wejściowe zmienią się tylko nieznacznie – nie rozwiążą tego rodzaju problemu optymalizacji. „Ten negatywny wynik dotyczy nie tylko klasycznych komputerów, ale także komputerów kwantowych, a konkretnie tak zwanych „algorytmów optymalizacji aproksymacji kwantowej” (QAOA), co do których niektórzy badacze mieli nadzieję, że rozwiążą te same problemy optymalizacyjne. Teraz, biorąc pod uwagę wyniki Jamarnika i W wyniku ustaleń współautorów nadzieje te są osłabiane przez świadomość, że aby algorytmy typu QAOA powiodły się, potrzeba będzie wielu warstw operacji, co może być technicznie trudne.

„To, czy to dobra, czy zła wiadomość, zależy od twojego punktu widzenia” – mówi. „Myślę, że to dobra wiadomość w tym sensie, że pomaga nam odkryć sekrety złożoności algorytmicznej i poszerza naszą wiedzę o tym, co jest w sferze prawdopodobieństwa, a co nie. To zła wiadomość w tym sensie, że mówi nam, że te problemy są trudne, nawet jeśli natura je wytwarza, a nawet jeśli są generowane losowo”. Dodaje, że wiadomość nie jest naprawdę zaskakująca. „Wielu z nas spodziewało się tego przez cały czas, ale teraz mamy znacznie solidniejszą podstawę do wysuwania tego twierdzenia”.

To wciąż pozostawia naukowcom lata świetlne od udowodnienia, że ​​nie ma szybkich algorytmów, które mogłyby rozwiązać te problemy optymalizacji w losowych ustawieniach. Posiadanie takich dowodów dałoby ostateczną odpowiedź na problem P NP. Mówi: „Jeśli możemy udowodnić, że nie możemy mieć algorytmu, który działa przez większość czasu, to mówi nam, że zdecydowanie nie możemy mieć algorytmu, który działa przez cały czas”.

Przewidywanie, jak długo zajmie rozwiązanie problemu PNP, wydaje się samo w sobie problemem nierozwiązywalnym. Prawdopodobnie będzie wiele szczytów do zdobycia i dolin do przebycia, zanim badacze uzyskają jaśniejszą perspektywę sytuacji.