Problem sprzed 50 lat, który wymyka się informatyce teoretycznej

Rozwiązanie problemu P vs NP może odblokować niezliczone problemy obliczeniowe — lub sprawić, że będą one na zawsze poza zasięgiem.

Problem drzewa Steinera: Połącz zbiór punktów za pomocą odcinków linii o minimalnej długości całkowitej. Derek Brahney

za pomocą

• Siobhan Roberts strona archiwum

27 października 2021

jeden. W poniedziałek, 19 lipca 2021 r., w środku kolejnej dziwnej pandemii lata, czołowy informatyk w dziedzinie teorii złożoności zamieścił na Twitterze wiadomość służb publicznych o problemie administracyjnym w czasopiśmie. Wylogował się z bardzo obciążonym

Wesołego poniedziałku.

Ta historia była częścią naszego wydania z listopada 2021 r.

• Zobacz resztę numeru
• Subskrybuj

W równoległym wszechświecie mógł to być naprawdę bardzo szczęśliwy poniedziałek. Dowód pojawił się online w cenionym czasopiśmie ACM Transactions on Computational Theory, które zajmuje się wybitnymi oryginalnymi badaniami badającymi granice wykonalnych obliczeń. Wynik rzekomo rozwiązał problem wszystkich problemów — Święty Graal informatyki teoretycznej, wart milion dolarów nagrody i sławę dorównującą na zawsze Arystotelesowi.

Ten cenny problem – znany jako P versus NP – jest uważany za najważniejszy w teoretycznej informatyce i matematyce i jest całkowicie poza zasięgiem. Odpowiada na pytania kluczowe dla obietnicy, ograniczeń i ambicji obliczeń, zadając:

Dlaczego niektóre problemy są trudniejsze niż inne?

Jakie problemy mogą realnie rozwiązać komputery?

Ile czasu to zajmie?

I jest to misja z dużymi filozoficznymi i praktycznymi korzyściami.

Spójrz, to pytanie P kontra NP, co mogę powiedzieć? Scott Aaronson, informatyk z University of Texas w Austin, napisał w swoim pamiętnik pomysłów , Obliczenia kwantowe od czasów Demokryta . Ludzie lubią opisywać to jako „prawdopodobnie główny nierozwiązany problem informatyki teoretycznej”. To komiczne niedopowiedzenie. P vs NP to jedno z najgłębszych pytań, jakie ludzie kiedykolwiek zadawali.

Jeden ze sposobów myślenia o bohaterach tej historii jest następujący:

P reprezentuje problemy, które komputer może z łatwością rozwiązać.

NP reprezentuje problemy, które po rozwiązaniu są łatwe do sprawdzenia – jak puzzle lub Sudoku. Wiele problemów związanych z NP odpowiada niektórym z najbardziej upartych i pilnych problemów, z jakimi boryka się społeczeństwo.

Pytanie za milion dolarów postawione przez P vs. NP brzmi: czy te dwie klasy problemów są jednym i tym samym? To znaczy, czy problemy, które wydają się tak trudne, można faktycznie rozwiązać za pomocą algorytmu w rozsądnym czasie, jeśli tylko uda się znaleźć właściwy, diabelsko szybki algorytm? Jeśli tak, wiele trudnych problemów można nagle rozwiązać. A ich algorytmiczne rozwiązania mogą spowodować zmiany społeczne o utopijnych proporcjach — w medycynie i inżynierii i ekonomii, biologii i ekologii, neuronauce i naukach społecznych, przemyśle, sztuce, a nawet polityce i nie tylko.

Czasami klasyfikacje ewoluują — trudne problemy okazują się łatwe, gdy badacze znajdują skuteczniejsze rozwiązania. Na przykład sprawdzanie, czy liczba jest liczbą pierwszą, należy do klasy NP od połowy lat siedemdziesiątych. Ale w 2002 roku trzech informatyków z indyjskiego Instytutu Technologii Kanpur opracowało bezwarunkowy dowód i sprytny algorytm, który ostatecznie potwierdził, że problem dotyczy również P.

Jeśli Wszystko trudne problemy mogłyby zostać przekształcone za pomocą takich algorytmicznych sztuczek, konsekwencje dla społeczeństwa – dla ludzkości i naszej planety – byłyby ogromne.

Po pierwsze, systemy szyfrowania, z których większość opiera się na problemach NP, zostałyby złamane. Musielibyśmy znaleźć zupełnie inne podejście do wysyłania bezpiecznej komunikacji. Fałdowanie białek, 50-letnie wielkie wyzwanie w biologii, stałoby się bardziej wykonalne, odblokowując nowo odkryte zdolności do projektowania leków, które leczą lub leczą choroby i odkrywają enzymy rozkładające odpady przemysłowe. Oznaczałoby to również znalezienie optymalnych rozwiązań codziennych trudnych problemów, takich jak zaplanowanie podróży, aby dotrzeć do wszystkich miejsc przy minimalnym nakładzie jazdy lub rozmieszczenie gości weselnych tak, aby tylko przyjaciele dzielili ten sam stół.

Od momentu powstania problemu P kontra NP 50 lat temu — wyłonionego z przełomowego skrzyżowania logiki matematycznej i technologii obliczeń elektronicznych — badacze na całym świecie podejmowali herkulesowe próby rozwiązania. Niektórzy informatycy sugerowali, że wysiłki te można lepiej porównać do wysiłków Syzyfa, który pracował bez rozwiązania. Ale podczas gdy tym, którzy jako pierwsi zbadali problem, kończy się czas, aby znaleźć rozwiązanie, nowsze pokolenia szczęśliwie podejmują tę misję.

Dla Manuela Sabina, informatyka, który właśnie kończy doktorat na Uniwersytecie Kalifornijskim w Berkeley, urok polega na badaniu niemożliwości problemów, na które nie poznasz odpowiedzi, dopóki słońce nie pochłonie ziemi. Poszukiwania mogą być donkiszotyczne, ale Sabin żałowałby, że nie rzucił się na te wiatraki.

Timothy Gowers, matematyk z Uniwersytetu Cambridge, nazywa to jedną z moich osobistych chorób matematycznych. Przegrał lato 2013 roku z pogonią, po tym, jak poprosił uczniów o wypracowanie na ten temat na teście. Jak opowiadał na swoim blogu: Po zaznaczeniu esejów w czerwcu, pomyślałem, że po prostu spędzę godzinę lub dwie na ponownym rozmyślaniu o problemie, a ta godzina lub dwie przypadkowo zamieniły się w około trzy miesiące.

Problem komiwojażera: znajdź najkrótszą możliwą trasę, która raz odwiedza każde miasto, a ostatecznie wraca do miasta pochodzenia.

DEREK BRAHNEY

Poszukiwania zaskoczyły nawet informatyka z Uniwersytetu Toronto, Stephena Cooka, który sformułował problem i zapoczątkował dziedzinę złożoności obliczeniowej w przełomowym artykule w 1971 roku. Za tę pracę zdobył nagrodę Turinga, odpowiednik Nagrody Nobla w informatyce. Ale nie miał szczęścia w znalezieniu rozwiązania. Cook mówi, że nigdy nie miał dobrych pomysłów – to po prostu zbyt trudne.

dwa. Michael Sipser, informatyk z MIT, szacuje, że spędził nad tym problemem nawet dekadę. Zainteresował się nim na studiach w latach 70. i założył się ze swoim kolegą, Lenem Adlemanem, o uncję złota, że ​​problem zostanie rozwiązany do końca wieku (zapłacił Sipser).

W latach 80. osiągnął niezły wynik, rozwiązując pewną wersję problemu z ograniczonym modelem obliczeniowym – prowadząc do ekscytującego okresu w tej dziedzinie z kilkoma pięknymi wynikami, dającymi powody do nadziei, że rozwiązanie może nie być zbyt odległe.

Sipser wciąż od czasu do czasu wraca do problemu i jest niezłomnym ambasadorem, wygłaszającym niezliczone prelekcje na ten temat.

Sposób, w jaki przybliża się do przystępnego wyjaśnienia P vs. NP, polega na podstawowym problemie mnożenia: 7 × 13 = ?

Odpowiedź, 91, można łatwo obliczyć w głowie. Chociaż mnożenie większych liczb nie jest tak łatwe, nadal komputerowi zajęłoby to praktycznie nie ma czasu.

Ale odwrócenie tych problemów to inna sprawa. Rozważmy na przykład znalezienie dwóch 97-cyfrowych liczb pierwszych, które po mnożeniu dają bardzo dużą liczbę:

5003588856 0437213507 310 7418240490 7930037346 0228427275 4572016194 8823206440 5180815045 5634682967 1723286782 4379162728 3803341547 1073108501 9195485290 0733772482 2783525742 3864540146 9173660247 7652346609

Ten problem faktoryzacji był częścią wyzwania oceniającego trudność złamania kluczy RSA używanych w kryptografii. Sipser wyjaśnia, że ​​rozwiązanie tego problemu zajęło 80 procesorom pięć miesięcy pracy ciągłej — co daje około 33 lata pracy przy użyciu tylko jednego procesora. Faktoring jest trudnym problemem, ponieważ wszystkie obecne metody szukają odpowiedzi za pomocą brutalnej siły, sprawdzając astronomiczną liczbę możliwości jedna po drugiej. Nawet dla komputera jest to powolny proces.

Interesujące pytanie brzmi: czy naprawdę musisz szukać? mówi Sipser. A może istnieje jakiś sposób rozwiązania problemu faktoryzacji, który szybko przybliża odpowiedź bez wyszukiwania? Nie znamy odpowiedzi na to pytanie.

Pytania takie jak to trafiają w sedno złożoności obliczeniowej — pola pełnego potwornych problemów, które badacze próbują zrozumieć. Aaronson stworzył Complexity Zoo, internetowy katalog z 545 klasami problemów (i liczonymi). Każdy z nich jest klasyfikowany według jego złożoności lub trudności oraz zasobów — czasu, pamięci, energii — niezbędnych do znalezienia rozwiązania. P i NP to główne atrakcje.

Naukowy traf chciał, że sowiecki matematyk Leonid Levin doszedł mniej więcej w tym samym czasie do wyniku równoważnego z Cookiem.

P to klasa, od której wszystko się zaczęło. Jest to klasa problemów, które komputer może rozwiązać w rozsądnym czasie. Dokładniej, problemy P to te, dla których czas potrzebny na znalezienie rozwiązania można opisać za pomocą funkcji wielomianowej, takiej jak n ^2. W algorytmach wielomianowych, n jest wielkością wkładu, a wzrost w stosunku do tego wkładu następuje w rozsądnym tempie (w tym przypadku do potęgi dwójki).

W przeciwieństwie do tego, niektóre trudne problemy NP mogą być rozwiązane tylko przez algorytmy z czasem działania zdefiniowanym przez funkcję wykładniczą, taką jak 2^n – wytwarzając wykładnicze tempo wzrostu (jak w przypadku rozprzestrzeniania się covid). NP, jak opisuje to Aaronson, jest klasą zawiedzionych nadziei i próżnych marzeń. Szybko jednak wyjaśnia powszechne błędne przekonanie: nie wszystkie problemy z NP są trudne. Klasa NP w rzeczywistości zawiera klasę P — ponieważ problemy z łatwymi rozwiązaniami są oczywiście również łatwe do sprawdzenia.

Trudniejsze problemy NP często mają doniosłe zastosowania praktyczne. W przypadku tych problemów wyczerpujące brutalne poszukiwanie rozwiązania prawdopodobnie trwałoby przez niepraktycznie długi czas — czas geologiczny — przed uzyskaniem odpowiedzi. Jeśli algorytm wyszukiwania brute-force jest najlepszym możliwym algorytmem, to P nie jest równe NP.

A wśród cognoscenti to najwyraźniej konsensus, który niektórzy bardziej przyrównują do wierzeń religijnych: P ≠ NP. Większość pozwala tylko na odrobinę nadziei, że okaże się, że coś przeciwnego się sprawdzi. Dałbym mu od 2 do 3% szansy, że P równa się NP, mówi Aaronson. To są kursy, które obstawiam.

Opublikowany w lipcu wynik był tego dowodem. Ale był to tylko najnowszy z długiej tradycji dowodów, które nie zdają egzaminu. W ciągu jednego dnia od publikacji, zgodnie z wydarzeniami godnymi Monty Pythona, artykuł został usunięty z internetowego czasopisma; potem wydawało się, że pojawił się na krótko, zanim zniknął na stałe. Była to najnowsza wersja artykułu, który autor przesłał ponad 60 razy na serwer preprintów arXiv w ciągu ostatniej dekady. Redaktor naczelny czasopisma wyjaśnił na Twitterze, że wynik został odrzucony, ale w przypadku błędu ludzkiego, pismo zmieniło się w jakiś sposób z odrzucenia na akceptację, a dowód trafił do publikacji.

3. Na początku sierpnia, kiedy spotkałem Steve'a Cooka w jego biurze na kampusie, nie widział ani nie słyszał o tym najnowszym snafu dowodu na P vs. NP. Teraz miał 81 lat i dopiero niedawno przeszedł na emeryturę, ponieważ zawodziła mu się pamięć. To dlatego mamy tutaj Jamesa, powiedział – jego syn James, 36 lat, również informatyk, dołączył do nas podczas mojej wizyty. Steve był w trakcie sprzątania swojego biura. Na środku pokoju stał gigantyczny kosz na śmieci, zapełniony starymi, pożółkłymi numerami „Journal of Symbolic Logic”, stosem super grubych książek telefonicznych z Toronto czekających w pobliżu.

Przez lata Cook widział wiele dowodów na rozwiązanie problemu P vs. NP. W 2000 roku, po tym, jak Clay Mathematics Institute uznał go za jeden z siedmiu nierozwiązanych problemów milenijnych (każdy wart milion dolarów nagrody), został zasypany wiadomościami od ludzi, którzy myśleli, że zwyciężyli. Wszystkie wyniki były błędne, jeśli nie po prostu fałszywe. Około połowa twierdziła, że ​​udowodniła, że ​​P równa się NP; druga połowa poszła w przeciwnym kierunku. Nie tak dawno temu jedna osoba twierdziła, że ​​udowodniła oba.

Cook w swoim artykule z 1971 r. przypuszczał, że P nie równa się NP (sformułował to używając innej terminologii powszechnej w tamtym czasie). Od tego czasu zainwestował znaczną, choć nieokreśloną ilość czasu, aby ustalić, czy tak jest. Nie pamiętam dobrze trudząc się, mówi, ale jego koledzy pamiętają, że za każdym razem, gdy wchodzili do działu w weekend, Steve był tam w swoim biurze.

O ile nie ściga się na żaglówkach, Cook nie jest kimś, kto się spieszy; lubi poświęcać czas na pomysł. A jego dawni uczniowie pamiętają wyraźny brak pychy. Informatyk Anna Lubiw z University of Waterloo mówi, że kiedy nauczał twierdzenia Cooka – części tego pionierskiego artykułu – nigdy nie odniósł się do niego w ten sposób i nigdy nie dał żadnych wskazówek, że to on to udowodnił. Maria Klawe, matematyk i informatyk oraz przewodnicząca Harvey Mudd College, mówi, że regularnie poprawiała Cooka, kiedy zgubił się w nauczaniu, dowody, które znał od podszewki: utknął i powiedział: „W porządku. Powiedz mi, jak wygląda dowód”. Cook był również znany ze skromności we wnioskach o granty i raportach dotyczących jego badań – przyznawał: Szczerze mówiąc, poczyniłem niewielkie postępy…

Powiązana historia

Ewolucja informatyki Obliczenie poziomów energii atomu helu w 1958 roku było znacznie trudniejsze niż obecnie. Ale porównanie metod wtedy i teraz ujawnia pewne sprzeczne z intuicją anomalie dotyczące wpływu informatyki.

Poczynił jednak postępy w rekrutacji Jamesa do podjęcia sprawy. Na początku James wykazywał zainteresowanie matematyką i informatyką — w wieku dziewięciu lat namawiał swojego tatę, aby nauczył go algebry Boole'a i logiki. Kilka lat temu, po zdobyciu doktoratu w Berkeley i odbyciu pracy w Google, rozpoczął pracę jako niezależny badacz, skupiając się na różnych projektach, niektóre z nich pośrednio związane z P vs. NP. I pomimo osiągnięć, James, który jest uderzająco podobny do swojego ojca, nie zraża się tym, że odziedziczył tak pozornie niekończące się poszukiwanie. Traktuje to jak każde matematyczne przedsięwzięcie: to zabawna łamigłówka. Musi być odpowiedź na te pytania, mówi. I to jest jak, daj spokój, ktoś musi to rozwiązać. Po prostu zajmijmy się tym. Kopę lat. To żenujące, że nie znamy jeszcze odpowiedzi.

Brak postępu nie powstrzymał tej społeczności szczęśliwych Syzyfów przed świętowaniem 50. rocznicy złożoności obliczeniowej. Uroczystości rozpoczęły się w 2019 roku, kiedy wielbiciele z całego świata zebrali się w Fields Institute for Research in Mathematical Sciences na Uniwersytecie w Toronto na sympozjum na cześć Cooka. Christos Papadimitriou, informatyk z Columbia University, który większość swojej kariery spędził pracując nad P vs. NP, otworzył wydarzenie publicznym wykładem, patrząc wstecz nie pół wieku, ale tysiąclecia.

Zaczął od opisania odwiecznych poszukiwań rozwiązań — przy użyciu narzędzi algebraicznych lub linijki i cyrkla, które uważał za podstawowe formy obliczeń. Opowieść Papadimitriou dotarła ostatecznie do Alana Turinga, brytyjskiego matematyka, którego artykuł z 1936 r. O liczbach obliczalnych sformalizował pojęcia algorytmu i obliczeń. Turing wykazał także — swoim pomysłem uniwersalnej maszyny liczącej — że nie ma mechanicznego sposobu (tj. wykonywanego przez maszynę) do udowodnienia prawdziwości lub fałszu twierdzeń matematycznych; brak systematycznego sposobu na odróżnienie tego, co można udowodnić od tego, czego nie można udowodnić.

Papadimitriou powiedział, że uważa pracę Turinga za akt urodzenia informatyki – a akt urodzenia mówi, że informatyka narodziła się z wyraźnym zrozumieniem własnych ograniczeń. Uważał, że informatyka jest jedyną znaną dziedziną dyskursu naukowego, która rodzi się z taką świadomością – w przeciwieństwie do innych nauk, które, tak jak my wszyscy, rozumieją swoje ograniczenia w późnym wieku średnim.

Niedługo po tym, jak idee Turinga (i podobne pomysły innych) znalazły zastosowanie w pierwszych komputerach, naukowcy zmierzyli się z pytaniami o nieodłączne możliwości i ograniczenia maszyn. We wczesnych latach pięćdziesiątych John von Neumann, węgiersko-amerykański pionier nowoczesnego komputera, przechwalał się algorytmem, że jest wielomianowy w porównaniu z wykładniczym operatorem, jak wspominał Papadimitriou – przechytrzył powolny algorytm szybkim. Był to początek nowej teorii: teorii złożoności obliczeniowej. Sednem tego było to, że tylko algorytmy wielomianowe są w jakimkolwiek sensie dobre, praktyczne lub warte rozwiązania problemu, podczas gdy algorytm wykładniczy, powiedział Papadimitriou, jest algorytmicznym odpowiednikiem śmierci.

Cook po raz pierwszy zaczął myśleć o złożoności w połowie lat sześćdziesiątych. Pracując nad swoim doktoratem na Harvardzie zastanawiał się, czy przy pewnych modelach obliczeniowych można udowodnić, że mnożenie jest trudniejsze niż dodawanie (pozostaje otwarty problem).

W 1967 roku, zgodnie z książką o Cooku, wydaną przez Association for Computing Machinery (ACM), podczas stażu podoktorskiego w Berkeley, sporządził notatki z kursu, które zawierały zalążek jego wielkiego wyniku. Opracował sformułowanie klas złożoności, które stały się znane jako P i NP, i zadał pytanie, czy P jest równe NP. (Mniej więcej w tym samym czasie inni, w tym informatyk Jack Edmonds, obecnie emerytowany z Uniwersytetu Waterloo, krążyli wokół tych samych pomysłów.)

Ale dziedzina informatyki dopiero się zaczynała, a dla większości naukowców i matematyków takie idee były nieznane, jeśli nie wręcz dziwne. Po czterech latach na wydziale matematyki w Berkeley, Cook był rozważany na stanowisko, ale nie zaoferowano mu stanowiska. Miał adwokatów na nowym uniwersyteckim wydziale informatyki, którzy lobbowali za przyznaniem mu stanowiska w ich szeregach, ale dziekan nie był skłonny przyznać etatu komuś, komu wybitni matematycy odmówili.

Większość teoretyków złożoności marzy o trochę mniejszych, wybierając zamiast tego podejścia pośrednie.

W 1970 roku Cook przeniósł się na Uniwersytet w Toronto. W następnym roku opublikował swój przełom. Przesłany na sympozjum ACM, które odbyło się w maju w Shaker Heights w stanie Ohio, artykuł zaostrzył pojęcie złożoności i zdefiniował sposób scharakteryzowania najtrudniejszych problemów w NP. Okazało się, w błysku algorytmicznej alchemii, że jeden problem, znany jako problem spełnialności (poszukiwanie rozwiązania formuły przy danym zbiorze ograniczeń), był w pewnym sensie najtrudniejszym problemem w NP i że wszystkie inne problemy NP można by do tego sprowadzić.

To było kluczowe twierdzenie: jeśli istnieje algorytm wielomianowy, który rozwiązuje problem spełnialności, to algorytm ten będzie służył jako klucz szkieletowy, odblokowujący rozwiązania wszystkich problemów w NP. A jeśli istnieje rozwiązanie wielomianowe dla wszystkich problemów w NP, to P = NP.

Wśród informatyków twierdzenie Cooka jest ikoną. Leslie Valiant z Harvardu przypomniał na sympozjum w 2019 roku dokładnie, gdzie i kiedy po raz pierwszy o tym usłyszał. Po ukończeniu studiów licencjackich z matematyki rozpoczął doktorat z informatyki. Powiedział, że chociaż w tej raczkującej dziedzinie były kursy i stopnie naukowe, wydawało się to efemeryczne, być może pozbawione głębokiej treści intelektualnej. Powiedział, że było to poważne zmartwienie dla ludzi zajmujących się informatyką w tym czasie. Zapytali: „Czy to jest pole? Dokąd to zmierza?” Pewnego dnia Valiant natknął się na gazetę Cooka. Przeczytał to w nocy. Zostałem przemieniony, powiedział. W mgnieniu oka moje obawy związane z informatyką znacznie się zmniejszyły. Ten artykuł — dla mnie naprawdę zrobił to pole. Myślę, że to uczyniło informatykę – uczyniło z niej coś istotnego.

A potem, jak głosi historia, po twierdzeniu Cooka nadszedł potop.

W 1972 r. Dick Karp, informatyk z Berkeley, po przeczytaniu ezoterycznej pracy Cooka, wykazał, że wiele klasycznych problemów obliczeniowych, z którymi był dobrze zaznajomiony – w zasadzie każdy problem, którego nie potrafił rozwiązać, zaczerpnięty z programowania matematycznego, badania operacyjne, teoria grafów, kombinatoryka i logika obliczeniowa — posiadały tę samą właściwość transformacyjną, którą Cook odkrył w przypadku problemu spełnialności. Łącznie Karp znalazł 21 problemów, w tym problem z plecakiem (poszukiwanie optymalnego sposobu na spakowanie ograniczonej przestrzeni najcenniejszymi przedmiotami), problem komiwojażera (znalezienie najkrótszej możliwej trasy, która raz odwiedza każde miasto i wraca do miasta pochodzenia) oraz problem drzewa Steinera (dążenie do optymalnego połączenia zbioru punktów z odcinkami liniowymi o minimalnej długości całkowitej).

Karp wykazał, że wszystkie te szczególne problemy są równoważne, co z kolei pokazało, że wzorzec zidentyfikowany przez Cooka nie był odosobnionym zjawiskiem, ale raczej metodologią klasyfikacyjną o zaskakującej sile i zasięgu. Był to swego rodzaju papierek lakmusowy, identyfikujący klasę problemów, które stały się znane jako problemy NP-zupełne: rozwiązanie każdego rozwiązałoby je wszystkie.

Papadimitriou myśli o NP-zupełności jako o wszechstronnym narzędziu. Jeśli nie możesz rozwiązać problemu, spróbuj udowodnić, że jest on NP-zupełny, ponieważ może zaoszczędzi ci to dużo czasu – powiedział podczas publicznego wykładu – możesz zrezygnować z dokładnego rozwiązania i przejść do rozwiązania przybliżenia lub zamiast tego odmiana problemu.

W wielkim rozciągnięciu historii Papadimitriou widzi fenomen NP-zupełności i poszukiwanie P kontra NP jako przeznaczenie informatyki. Ponieważ naukowy zbieg okoliczności sprawił, że sowiecki matematyk Leonid Levin mniej więcej w tym samym czasie zbliżył się do wyniku równoważnego z Cookiem. Levin, obecnie na Uniwersytecie w Bostonie, wykonywał swoją pracę za żelazną kurtyną. Po zwróceniu na nie szerszej uwagi (wyemigrował do Ameryki w 1978), wynik stał się znany jako twierdzenie Cooka-Levina.

A w kolejnej kodzie, mniej więcej dekadę później, w archiwach Princeton austriackiego logika Kurta Gödla odkryto zagubiony list. W 1956 roku napisał do von Neumanna z pytaniem, czy problem logiczny – który we współczesnym języku nazwalibyśmy NP-zupełnym – można rozwiązać w czasie wielomianowym. Ocenił, że miałoby to największe konsekwencje.

Problem kliki: Wyszukaj kliki na wykresie, takie jak pewien podzbiór znajomych w sieci społecznościowej.

DEREK BRAHNEY

Cztery. Podczas gdy pół wieku pracy nie przyniosło niczego bliskiego rozwiązania, niektóre wyniki przynajmniej pobudzają wyobraźnię: artykuł z 2004 r. twierdził, że dowód na P = NP przy użyciu baniek mydlanych jako mechanizmu obliczeń analogowych (błona mydlana, oczywiście wyrównanie w konfiguracji o minimalnej energii rozwiązuje w pewien sposób problem NP-zupełnego drzewa Steinera).

W dzisiejszych czasach jest to rzadki ptak informatyka — na przykład Ron Fagin, współpracownik IBM — który zajmuje się tym problemem. W latach 70. stworzył twierdzenie Fagina, które charakteryzowało klasę NP pod względem logiki matematycznej. I rozwiązał problem więcej niż raz, ale wyniki nigdy nie trwały dłużej niż kilka dni, zanim znalazł błąd. Fagin niedawno otrzymał fundusze na projekt P vs. NP z programu IBM Exploratory Challenges wspierającego badania przygód. Wyjaśniając, dlaczego się tego trzyma, lubi cytować Theodore'a Roosevelta, który powiedział, że o wiele lepiej odważyć się na potężne rzeczy, niż zaliczać się do tych, którzy żyją w szarym zmierzchu, który nie zna ani zwycięstwa, ani porażki.

Jednak większość teoretyków złożoności marzy o nieco mniejszych rozmiarach, wybierając zamiast tego podejścia pośrednie — przechylanie problemu, przekształcanie go lub przeformułowywanie, eksplorowanie powiązanych środowisk i dalsze zmniejszanie arsenału narzędzi, które można by zastosować w jego walce (wiele z nich jest obecnie znanych jako bezużyteczne). ).

Ryan Williams, informatyk z MIT, stara się naświetlić problem zarówno od góry, jak i od dołu, badając naturę górnych i dolnych granic podstawowych problemów obliczeniowych. Najprościej mówiąc, górne ograniczenie to określone twierdzenie matematyczne, że istnieje konkretny algorytm, który rozwiązuje konkretny problem bez przekraczania pewnej ilości zasobów (czasu, pamięci, energii). Dolna granica jest niematerialnym przeciwieństwem: jest to ogólne twierdzenie o niemożliwości, pokazujące, że taki algorytm nie istnieje powszechnie. Jednym z celów badań Williamsa jest uczynienie dolnych granic konstruktywnymi i konkretnymi — matematycznymi obiektami o cechach możliwych do opisania. Uważa, że ​​bardziej konstruktywne podejścia do dolnych granic są dokładnie tym, czego brakuje w obecnych podejściach w teorii złożoności.

Williams ustalił prawdopodobieństwo, że P ≠ NP na dość umiarkowanym poziomie 80%. Ale ostatnio niektórzy badacze w tej dziedzinie wyrażają wątpliwości co do nawet tego poziomu pewności. Coraz bardziej zaczynam się zastanawiać, czy P równa się NP, mówi Toniann Pitassi, informatyk z University of Toronto i były doktorant Cooka. Jej podejście do okrążania problemu polega na badaniu zarówno pomniejszonych, jak i powiększonych analogów, twardszych i łatwiejszych modeli. Czasami uogólnienie pytania sprawia, że ​​staje się jaśniejsze, mówi. Ale ogólnie rzecz biorąc, nie osiągnęła jasności: większość ludzi uważa, że ​​P nie równa się NP. I nie wiem. Może to tylko ja, ale czuję, że coraz mniej jasne jest, że to prawda.

Z historycznego punktu widzenia, zauważa Pitassi, zaskakujące wyniki czasami pojawiały się znikąd – pozorne niemożliwości udowodnione przez inteligentnych projektantów algorytmów. To samo może się stać z P vs NP, może za 50 lat lub za sto lat. Jeden z najważniejszych wyników w całej teorii złożoności został osiągnięty na przykład przez Davida Barringtona z University of Massachusetts, Amherst, w 1989 roku. Istotą tego (dla naszych celów) jest to, że opracował sprytny algorytm, który postanowiłem zrobić coś, co pozornie powinno wymagać nieograniczonej ilości pamięci, ale w rzeczywistości używało zdumiewająco małej ilości — zaledwie pięć bitów informacji, które wystarczyły do ​​określenia liczby od jednego do 32 (włącznie) lub dwuliterowego słowa.

Nowszy i powiązany wynik z 2014 roku zaskoczył Jamesa Cooka. Czerpiąc z twierdzenia Barringtona, wykorzystuje pamięć w cudownie dziwny sposób. Jak zasugerował w tytule artykułu Harry Buhrman z Uniwersytetu Amsterdamskiego i jego współpracownicy, chodzi o komputery z pełną pamięcią. James może wyrecytować wstępny akapit artykułu praktycznie dosłownie:

Wyobraź sobie następujący scenariusz. Chcesz wykonać obliczenia, które wymagają więcej pamięci niż obecnie dostępna na komputerze. Jednym ze sposobów radzenia sobie z tym problemem jest zainstalowanie nowego dysku twardego. Okazuje się, że masz dysk twardy, ale jest on pełen danych, zdjęć, filmów, plików itp. Nie potrzebujesz w tej chwili dostępu do tych danych, ale też nie chcesz ich usuwać. Czy możesz użyć dysku twardego do obliczeń, prawdopodobnie zmieniając tymczasowo jego zawartość, gwarantując, że po zakończeniu obliczeń dysk twardy powróci do pierwotnego stanu ze wszystkimi nienaruszonymi danymi?

Odpowiedź, sprzeczna z intuicją, brzmi: tak.

James myśli o tym jako o pożyczonej pamięci. Po tym, jak ogarnął szok wywołany tym rezultatem, dobrze się bawił, zastanawiając się, jak zastosować go do konkretnego problemu – wznowienia tego, co przerwał jego tata.

Kilkadziesiąt lat temu Steve Cook zajął się innymi powiązanymi problemami w teorii złożoności. Z jednym problemem wysunął przypuszczenie dotyczące ilości pamięci, jakiej algorytm będzie potrzebował do rozwiązania problemu — doprowadzenie go do absolutnego minimum. W 2019 roku James wraz z Ianem Mertzem, jednym z doktorantów Pitassiego, zastosowali poetycką ideę pożyczania pamięci i udowodnili, że potrzeba jeszcze mniej pamięci. Wynik nie poszedł aż do obalenia przypuszczeń jego taty, ale mimo wszystko jest to pewien postęp w zadaniu o wielkiej złożoności.

A problemy z teorią złożoności, zauważa James, czasami wywołują efekt domina – jeśli w jednym krytycznym kącie znajduje się dowód, wszystkie domina upadną. Przełomowe wyniki, te najważniejsze, pochodzą z długiej linii pracy wielu różnych ludzi, dokonujących stopniowego postępu i ustanawiających powiązania między różnymi pytaniami, aż w końcu pojawia się duży wynik.

Wspomina również o pewnym zastrzeżeniu: podczas gdy naprawdę diabelsko szybki algorytm P = NP byłby wstrząsający, istnieje również scenariusz, w którym P = NP może być rozczarowaniem. Może się okazać, że algorytm P zdolny do rozwiązania problemu NP-zupełnego ma skalę czasową, powiedzmy, n ^100. Technicznie to mieści się w P: jest to wielomian, mówi James. Ale n ^100 jest nadal bardzo niepraktyczne — oznaczałoby to, że jakiekolwiek poważne problemy byłyby nadal poza zasięgiem ludzkiej skali czasu.

To znaczy oczywiście przy założeniu, że w pierwszej kolejności możemy znaleźć algorytm. Donald Knuth, algorytmista ze Stanford, w ostatnich latach zmienił zdanie — przekręcił bit. Jego intuicja jest taka, że ​​P rzeczywiście równa się NP, ale prawdopodobnie nigdy nie będziemy w stanie wykorzystać tego faktu, praktycznie mówiąc – ponieważ tak naprawdę nie poznamy żadnego z algorytmów, które akurat działają. Wyjaśnia, że ​​istnieje oszałamiająca liczba algorytmów, ale większość z nich jest poza naszym zasięgiem. Tak więc, podczas gdy niektórzy badacze mogą upierać się, że żaden algorytm P = NP nie istnieje, Knuth twierdzi, że jest bardziej prawdopodobne, że żaden algorytm wielomianowy nigdy nie zostanie ucieleśniony – w rzeczywistości napisany jako program – przez zwykłych śmiertelników.

Dla Papadimitriou każda odpowiedź mogłaby ugasić trwającą całe życie obsesję. Uważa, że ​​problem P vs. NP należy do sfery fundamentalnych naukowych zagadek, takich jak pochodzenie życia i unifikacja pól sił natury. Powiedział, że jest to rodzaj głębokiej, konsekwentnej zagadki, konkretnej, ale uniwersalnej, która nadaje sens nie tylko nauce, ale i samemu życiu człowieka.

Wyobraź sobie, że mamy szczęście i jesteśmy w stanie wycisnąć kolejne kilka tysięcy lat z tej planety, wbrew przeciwnościom losu i pomimo dziwactw, powiedział. I nie rozwiązujemy tych problemów. Jaki jest sens?!