P ≠ NP? Szachowa zagadka sprowadzona do problemu za milion dolarów

Możliwość sprowadzenia znalezienia rozwiązania do sprawdzeniarozwiązania ma oczywiście kluczowe znaczenie dla informatyki –przede wszystkim w kryptografii, gdzie polegamy na tym, że pewneoperacje są trudne, ich wykonanie wymaga ogromnej mocyobliczeniowej. Ale nie tylko, problem P ≠ NP przewija się przezmaszynowe dowodzenie twierdzeń, a także badania operacyjne w ramachteorii decyzji, ma swoje ważne konsekwencje dla filozofii, a nawetbiologii. Dlatego też w 2000 roku Instytut Matematyczny Claya,fundacja, która za swój cel postawiła sobie rozwój wiedzymatematycznej, włączyła go na listę siedmiu problemów nagrodymillenijnej, za których rozwiązanie wyznaczono po milionie dolarównagrody.

Najbardziej zrozumiałe chyba dla laików objaśnienie P ≠ NP przedstawia sam Instytut Matematyczny Claya:

Załóżmy, że organizujesz nocleg dla 400 studentów. Wakademiku brakuje jednak miejsca dla wszystkich – jest tylko 100miejsc. W dodatku dziekan przygotował listę par skłóconych zesobą studentów i zażądał, by w twoim ostatecznym zestawieniu nieznalazła się żadna taka para. To właśnie jest przykładNP-zupełnego problemu: łatwo jest sprawdzić, czy dany zestaw stustudentów przygotowanych przez pomocnika jest satysfakcjonujący(tj. żadna para z jego listy nie pojawia się na liście dziekana),jednak zadanie wygenerowania takiej listy od podstaw jest tak trudne,że praktycznie niemożliwe. Liczba sposobów, na jakie można wybraćzgodnie z tymi wytycznymi 100 studentów z 400 kandydatów jestwiększa, niż liczba atomów we wszechświecie. Nie ma co liczyć nato, że powstanie komputer zdolny do siłowego rozwiązania problemu,tj. wygenerowania każdej możliwej kombinacji 100 studentów. Może jednak to tylko problem z wyobraźnią programistów? Czymożliwe jest dla tego problemu stworzenie algorytmu, któryrozwiązałby go w jakiś sprytny sposób (równoważny P-problem),szybko sprawdzając możliwe odpowiedzi? Jak do tej pory nikt niedowiódł, że to jest tak trudne, na jakie to wygląda, tj. że niema żadnej sensownej drogi wygenerowania odpowiedzi z pomocąkomputera.

Dwa tygodnie temu niemiecki informatyk, profesor NorbertBlum (bycie informatykiem oznacza tu pisanie książek w rodzajuEine Omega(n4/3) untere Schranke für die monotoneSchaltkreiskomplexität von n-te Grad Convolution) przedstawiłobiecującerozwiązanie problemu P ≠ NP. Nie pierwsze oczywiście – dowrześnia 2016 roku opublikowano 116prac, których wyniki są, delikatnie mówiąc, rozbieżne – 62prace dowodzą, że P = NP, 50 że P ≠ NP, jedna, że problem jestnierozstrzygalny, dwie, że jest niedowiedlny. Żadna z tych prac niewytrzymała próby czasu, w każdej dopatrzono się uchybień.

Z perspektywy teorii złożoności problemy P to klasa tych wszystkich problemów decyzyjnych, które mogą zostać rozwiązane przez deterministyczną maszynę Turinga (czytaj: komputer) w czasie wielomianowym (czytaj: szybko), zależnym od danych na wejściu. Problemy NP to klasa tych wszystkich problemów, których pozytywne rozwiązanie może zostać zweryfikowane w wielomianowym czasie po podaniu na wejściu odpowiedniej informacji.

Tym razem atak na ten twardy do zgryzienia orzech przeprowadzonouogólniając pewne rezultaty z zakresu teorii złożoności,dotyczącej złożoności obwodów – gdzie funkcje boole’owskiesą klasyfikowane zgodnie z rozmiarem obwodów z bramek logicznych,które je wyliczają. Uogólnienie przełożyło rozstrzygnięcia dlaobwodów monotonicznych (złożonych tylko z bramek AND i OR) tak bydziałało to także dla ogólnych obwodów (niemonotonicznych),złożonych z bramek AND, OR i NOT. Jeśli uogólnienie byłobysłuszne, to P ≠ NP.

Krytyka przyszła bardzo szybko, jak ktoś czuje się dobry zalgebry i teorii złożoności, może zapoznać się z dyskusją nałamach StackExchange. Wystarczyła, by Blum przyznał,że dowód jest niepoprawny. Ekspert od informatyki kwantowej zTeksasu, Scott Aaronson, który gotów był postawić 200 tys.dolarów na niepoprawność tego dowodu, napisał na swoimblogu:

Na próżno szukam właściwego sposobu nauczenia świata nerdów,by mniej się ekscytowali takimi twierdzeniami, by reagowali tak jakeksperci – „o nie, tylko nie kolejny” – co nie oznacza, żeznasz błąd, lub że nawet wiesz, że jest tu błąd, lecz po prostuznasz historię problemu.

By pomóc nie dość należycie wykształconym nerdom, profesorAaronson uruchomił więc stronę haspvsnpbeensolved.com,gdzie można podać adres URL artykułu do sprawdzenia, by dowiedziećsię (po konsultacji z kwantowymi wyroczniami, że nie, niczego nieudowodniono.

To oczywiście żart, ale wyniki nie przestają napływać.Niekiedy bardzo osobliwe. Dopiero co w Journal of ArtificialIntelligence Research, Ian P. Gent, Christopher Jefferson i PeterNightingale opublikowali artykułpt. Complexity of n-Queens Completion, dotyczący klasycznegoszachowo-matematycznego problemu n królowych. Rzuca on wyzwanieprogramistom: kto znajdzie rozwiązanie tej prostej szachowejzagadki, jednocześnie rozwiązać ma problem, za któregorozwiązanie czeka milion dolarów.

Zadanie jest proste do wyjaśnienia: na szachownicy o wymiarachn×n musimy umieścić n królowych tak, by żadna z nich nieatakowała innej – tj. były na różnych liniach, kolumnach iprzekątnych. Istnieją siłowe rozwiązania dla n<20 (zawyjątkiem n=2 i n=3), ale gdy n robi się większe, złożonośćproblemu zaczyna być zabójcza dla najpotężniejszychsuperkomputery. Dla normalnej szachownicy 8×8 mamy 4 426 165 368możliwych ustawień ośmiu królowych, ale tylko 92 możliwerozwiązania. Dlatego też problem n królowych jest używanypowszechnie jako benchmark sztucznych inteligencji,

Praca wspomnianych autorów ma wykazać, że problem n królowychi pokrewne problemy są zarazem problemami NP-zupełnymi jak i#P-zupełnymi, to jest takimi, które należą do klasy złożoności#P – obejmującej funkcje pytające nie tyle o istnienie, co oliczbę (np. ile podzbiorów na danej liście liczb całkowitychsumuje się do zera?).

Udowodnienie, że tradycyjna szachowa zagadka jest problememNP-zupełnym jest o tyle istotne, że dowolny problem NP-zupełnymoże zostać zreformułowany jako inny problem NP-zupełny.Stworzenie programu, który by szybko (w czasie wielomianowym, a niewykładniczym) rozwiązywał tę zagadkę szachową byłoby więc wpraktyce szybkim złamaniem szyfru RSA, w którym zakłada się, żeproblem podziału dowolnej liczby na czynniki pierwsze nie jestproblemem wielomianowym.

Póki co relacja miedzy złożonością P i NP pozostaje kwestią wyznania wiary matematyków. W 2012 roku przeprowadzono w tej społeczności sondaż. Odpowiedziało 151 osób, 83% uznało, że P ≠ NP, 12% uznało że P=NP, 3% uznało że dowiedzenie tego jest niemożliwe, 5% uznało, że nie wie lub nie chce rozwiązania tego problemu.