- Moderator
- #221
- 8 902
- 25 806
P ≠ NP? Szachowa zagadka sprowadzona do problemu za milion dolarów
03.09.2017 23:17
Lista nierozwiązanych problemów matematyki liczy setki pozycji, a poczesne wśród nich miejsce zajmuje problem P ≠ NP, czyli znalezienie odpowiedzi na pytanie, czy dla każdego zagadnienia, dla którego możliwa jest szybka weryfikacja rozwiązania, możliwe jest również szybkie znalezienie tego rozwiązania. Ostatnie miesiące okazały się bardzo interesujące w tym temacie, przez chwilę pojawiła się nawet perspektywa zgarnięcia millenijnej nagrody – miliona dolarów – za poprawne rozwiązanie. A jednak chyba nic z tego. Coraz bardziej wygląda na to, że P ≠ NP pozostanie problemem, który matematycznymi metodami jest niemożliwy do rozstrzygnięcia, w którym uczeni mogą co najwyżej wygłaszać swoje deklaracje wiary.
Na siłę nie ma czasu?
Możliwość sprowadzenia znalezienia rozwiązania do sprawdzenia rozwiązania ma oczywiście kluczowe znaczenie dla informatyki – przede wszystkim w kryptografii, gdzie polegamy na tym, że pewne operacje są trudne, ich wykonanie wymaga ogromnej mocy obliczeniowej. Ale nie tylko, problem P ≠ NP przewija się przez maszynowe dowodzenie twierdzeń, a także badania operacyjne w ramach teorii decyzji, ma swoje ważne konsekwencje dla filozofii, a nawet biologii. Dlatego też w 2000 roku Instytut Matematyczny Claya, fundacja, która za swój cel postawiła sobie rozwój wiedzy matematycznej, włączyła go na listę siedmiu problemów nagrody millenijnej, za których rozwiązanie wyznaczono po milionie dolarów nagrody.
Najbardziej zrozumiałe chyba dla laików objaśnienie P ≠ NP przedstawia sam Instytut Matematyczny Claya:
Może jednak to tylko problem z wyobraźnią programistów? Czy możliwe jest dla tego problemu stworzenie algorytmu, który rozwiązałby go w jakiś sprytny sposób (równoważny P-problem), szybko sprawdzając możliwe odpowiedzi? Jak do tej pory nikt nie dowiódł, że to jest tak trudne, na jakie to wygląda, tj. że nie ma żadnej sensownej drogi wygenerowania odpowiedzi z pomocą komputera.
Sprzeczne dowody – co miesiąc inny wynik
Dwa tygodnie temu niemiecki informatyk, profesor Norbert Blum (bycie informatykiem oznacza tu pisanie książek w rodzaju Eine Omega(n4/3) untere Schranke für die monotone Schaltkreiskomplexität von n-te Grad Convolution) przedstawił obiecujące rozwiązanie problemu P ≠ NP. Nie pierwsze oczywiście – do września 2016 roku opublikowano 116 prac, których wyniki są, delikatnie mówiąc, rozbieżne – 62 prace dowodzą, że P = NP, 50 że P ≠ NP, jedna, że problem jest nierozstrzygalny, dwie, że jest niedowiedlny. Żadna z tych prac nie wytrzymała próby czasu, w każdej dopatrzono się uchybień.
Tym razem atak na ten twardy do zgryzienia orzech przeprowadzono uogólniając pewne rezultaty z zakresu teorii złożoności, dotyczącej złożoności obwodów – gdzie funkcje boole’owskie są klasyfikowane zgodnie z rozmiarem obwodów z bramek logicznych, które je wyliczają. Uogólnienie przełożyło rozstrzygnięcia dla obwodów monotonicznych (złożonych tylko z bramek AND i OR) tak by dział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łoby słuszne, to P ≠ NP.
Krytyka przyszła bardzo szybko, jak ktoś czuje się dobry z algebry i teorii złożoności, może zapoznać się z dyskusją na łamach Stack Exchange. Wystarczyła, by Blum przyznał, że dowód jest niepoprawny. Ekspert od informatyki kwantowej z Teksasu, Scott Aaronson, który gotów był postawić 200 tys. dolarów na niepoprawność tego dowodu, napisał na swoim blogu:
Na próżno szukam właściwego sposobu nauczenia świata nerdów, by mniej się ekscytowali takimi twierdzeniami, by reagowali tak jak eksperci – „o nie, tylko nie kolejny” – co nie oznacza, że znasz błąd, lub że nawet wiesz, że jest tu błąd, lecz po prostu znasz historię problemu.
By pomóc nie dość należycie wykształconym nerdom, profesor Aaronson 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 nie udowodniono.
Złam łamigłówkę, złam szyfr
To oczywiście żart, ale wyniki nie przestają napływać. Niekiedy bardzo osobliwe. Dopiero co w Journal of Artificial Intelligence Research, Ian P. Gent, Christopher Jefferson i Peter Nightingale opublikowali artykuł pt. Complexity of n-Queens Completion, dotyczący klasycznego szachowo-matematycznego problemu n królowych. Rzuca on wyzwanie programistom: kto znajdzie rozwiązanie tej prostej szachowej zagadki, jednocześnie rozwiązać ma problem, za którego rozwiązanie czeka milion dolarów.
Zadanie jest proste do wyjaśnienia: na szachownicy o wymiarach n×n musimy umieścić n królowych tak, by żadna z nich nie atakowała innej – tj. były na różnych liniach, kolumnach i przekątnych. Istnieją siłowe rozwiązania dla n<20 (za wyjątkiem n=2 i n=3), ale gdy n robi się większe, złożoność problemu zaczyna być zabójcza dla najpotężniejszych superkomputery. Dla normalnej szachownicy 8×8 mamy 4 426 165 368 możliwych ustawień ośmiu królowych, ale tylko 92 możliwe rozwiązania. Dlatego też problem n królowych jest używany powszechnie jako benchmark sztucznych inteligencji,
Praca wspomnianych autorów ma wykazać, że problem n królowych i 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 o liczbę (np. ile podzbiorów na danej liście liczb całkowitych sumuje się do zera?).
Udowodnienie, że tradycyjna szachowa zagadka jest problemem NP-zupełnym jest o tyle istotne, że dowolny problem NP-zupełny może zostać zreformułowany jako inny problem NP-zupełny. Stworzenie programu, który by szybko (w czasie wielomianowym, a nie wykładniczym) rozwiązywał tę zagadkę szachową byłoby więc w praktyce szybkim złamaniem szyfru RSA, w którym zakłada się, że problem podziału dowolnej liczby na czynniki pierwsze nie jest problemem 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.
03.09.2017 23:17
Lista nierozwiązanych problemów matematyki liczy setki pozycji, a poczesne wśród nich miejsce zajmuje problem P ≠ NP, czyli znalezienie odpowiedzi na pytanie, czy dla każdego zagadnienia, dla którego możliwa jest szybka weryfikacja rozwiązania, możliwe jest również szybkie znalezienie tego rozwiązania. Ostatnie miesiące okazały się bardzo interesujące w tym temacie, przez chwilę pojawiła się nawet perspektywa zgarnięcia millenijnej nagrody – miliona dolarów – za poprawne rozwiązanie. A jednak chyba nic z tego. Coraz bardziej wygląda na to, że P ≠ NP pozostanie problemem, który matematycznymi metodami jest niemożliwy do rozstrzygnięcia, w którym uczeni mogą co najwyżej wygłaszać swoje deklaracje wiary.
Na siłę nie ma czasu?
Możliwość sprowadzenia znalezienia rozwiązania do sprawdzenia rozwiązania ma oczywiście kluczowe znaczenie dla informatyki – przede wszystkim w kryptografii, gdzie polegamy na tym, że pewne operacje są trudne, ich wykonanie wymaga ogromnej mocy obliczeniowej. Ale nie tylko, problem P ≠ NP przewija się przez maszynowe dowodzenie twierdzeń, a także badania operacyjne w ramach teorii decyzji, ma swoje ważne konsekwencje dla filozofii, a nawet biologii. Dlatego też w 2000 roku Instytut Matematyczny Claya, fundacja, która za swój cel postawiła sobie rozwój wiedzy matematycznej, włączyła go na listę siedmiu problemów nagrody millenijnej, za których rozwiązanie wyznaczono po milionie dolarów nagrody.
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. W akademiku brakuje jednak miejsca dla wszystkich – jest tylko 100 miejsc. W dodatku dziekan przygotował listę par skłóconych ze sobą studentów i zażądał, by w twoim ostatecznym zestawieniu nie znalazła się żadna taka para. To właśnie jest przykład NP-zupełnego problemu: łatwo jest sprawdzić, czy dany zestaw stu studentó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 jest większa, niż liczba atomów we wszechświecie. Nie ma co liczyć na to, ż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? Czy możliwe jest dla tego problemu stworzenie algorytmu, który rozwiązałby go w jakiś sprytny sposób (równoważny P-problem), szybko sprawdzając możliwe odpowiedzi? Jak do tej pory nikt nie dowiódł, że to jest tak trudne, na jakie to wygląda, tj. że nie ma żadnej sensownej drogi wygenerowania odpowiedzi z pomocą komputera.
Sprzeczne dowody – co miesiąc inny wynik
Dwa tygodnie temu niemiecki informatyk, profesor Norbert Blum (bycie informatykiem oznacza tu pisanie książek w rodzaju Eine Omega(n4/3) untere Schranke für die monotone Schaltkreiskomplexität von n-te Grad Convolution) przedstawił obiecujące rozwiązanie problemu P ≠ NP. Nie pierwsze oczywiście – do września 2016 roku opublikowano 116 prac, których wyniki są, delikatnie mówiąc, rozbieżne – 62 prace dowodzą, że P = NP, 50 że P ≠ NP, jedna, że problem jest nierozstrzygalny, dwie, że jest niedowiedlny. Żadna z tych prac nie wytrzymał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 przeprowadzono uogólniając pewne rezultaty z zakresu teorii złożoności, dotyczącej złożoności obwodów – gdzie funkcje boole’owskie są klasyfikowane zgodnie z rozmiarem obwodów z bramek logicznych, które je wyliczają. Uogólnienie przełożyło rozstrzygnięcia dla obwodów monotonicznych (złożonych tylko z bramek AND i OR) tak by dział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łoby słuszne, to P ≠ NP.
Krytyka przyszła bardzo szybko, jak ktoś czuje się dobry z algebry i teorii złożoności, może zapoznać się z dyskusją na łamach Stack Exchange. Wystarczyła, by Blum przyznał, że dowód jest niepoprawny. Ekspert od informatyki kwantowej z Teksasu, Scott Aaronson, który gotów był postawić 200 tys. dolarów na niepoprawność tego dowodu, napisał na swoim blogu:
Na próżno szukam właściwego sposobu nauczenia świata nerdów, by mniej się ekscytowali takimi twierdzeniami, by reagowali tak jak eksperci – „o nie, tylko nie kolejny” – co nie oznacza, że znasz błąd, lub że nawet wiesz, że jest tu błąd, lecz po prostu znasz historię problemu.
By pomóc nie dość należycie wykształconym nerdom, profesor Aaronson 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 nie udowodniono.
Złam łamigłówkę, złam szyfr
To oczywiście żart, ale wyniki nie przestają napływać. Niekiedy bardzo osobliwe. Dopiero co w Journal of Artificial Intelligence Research, Ian P. Gent, Christopher Jefferson i Peter Nightingale opublikowali artykuł pt. Complexity of n-Queens Completion, dotyczący klasycznego szachowo-matematycznego problemu n królowych. Rzuca on wyzwanie programistom: kto znajdzie rozwiązanie tej prostej szachowej zagadki, jednocześnie rozwiązać ma problem, za którego rozwiązanie czeka milion dolarów.
Zadanie jest proste do wyjaśnienia: na szachownicy o wymiarach n×n musimy umieścić n królowych tak, by żadna z nich nie atakowała innej – tj. były na różnych liniach, kolumnach i przekątnych. Istnieją siłowe rozwiązania dla n<20 (za wyjątkiem n=2 i n=3), ale gdy n robi się większe, złożoność problemu zaczyna być zabójcza dla najpotężniejszych superkomputery. Dla normalnej szachownicy 8×8 mamy 4 426 165 368 możliwych ustawień ośmiu królowych, ale tylko 92 możliwe rozwiązania. Dlatego też problem n królowych jest używany powszechnie jako benchmark sztucznych inteligencji,
Praca wspomnianych autorów ma wykazać, że problem n królowych i 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 o liczbę (np. ile podzbiorów na danej liście liczb całkowitych sumuje się do zera?).
Udowodnienie, że tradycyjna szachowa zagadka jest problemem NP-zupełnym jest o tyle istotne, że dowolny problem NP-zupełny może zostać zreformułowany jako inny problem NP-zupełny. Stworzenie programu, który by szybko (w czasie wielomianowym, a nie wykładniczym) rozwiązywał tę zagadkę szachową byłoby więc w praktyce szybkim złamaniem szyfru RSA, w którym zakłada się, że problem podziału dowolnej liczby na czynniki pierwsze nie jest problemem 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.