Jak szybko zarobić 1 milion $?

Perspektywa zarabiania niezłych pieniędzy jest motorem napędowym wielu adeptów programowania. Jednak nauka programowania jest czasochłonna - oprócz samego języka musimy poznać również zagadnienia z tym związane, takie jak np. frameworki, struktury danych, algorytmy, czy też bazy danych. W tym artykule pokażę inny sposób, dzięki któremu można zarobić w krótkim czasie milion dolarów. Wystarczy tylko rozwiązać pewien problem.

Od teraz, mówiąc problem będziemy mieli na myśli problem decyzyjny, czyli taki, którego wyjściem jest TRUE lub FALSE.

Problemy rozwiązywalne w czasie wielomianowym

Pięknie by było, jakby wszystkie problemy były łatwo rozwiązywalne. Ale co to właściwie oznacza “łatwo rozwiązywalne”? Mając do dyspozycji złożoności czasowe algorytmu możemy powiedzieć, że problem jest taki, jeśli posiada algorytm rozwiązujący go w czasie co najwyżej wielomianowym, czyli istnieje taka liczba naturalna c, że algorytm jest O(n^c). Oczywiście, jeśli c jest duże (np. 1000) to już przy stosunkowo małym rozmiarze danych przestaje być szybko obliczalny. Jednak praktyka pokazuje, że takie problemy są marginalne i większość problemów, jeśli jest wielomianowa, to istnieje taki algorytm je rozwiązujący, taki, że c jest stosunkowo małe. Wygodnie jest zdefiniować zbiór P jako zbiór wszystkich takich problemów, które są rozwiązywalne w czasie wielomianowym.

Weryfikowalność w czasie wielomianowym

Istnieją jednak problemy, dla których nie znamy rozwiązującego je algorytmu wielomianowego. Jednak dla części z takich problemów znamy algorytmy takie, że mając certyfikat o długości wielomianowej, jesteśmy w stanie sprawdzić jego poprawność w czasie wielomianowym. Czym może być taki certyfikat? Załóżmy, że chcemy zweryfikować rozwiązanie problemu SUBSET-SUM, czyli takiego, że na wejściu dostajemy zbiór liczb całkowitych dodatnich S oraz dodatnią liczbę całkowitą t, i chcemy sprawdzić, czy istnieje taki podzbiór S, że suma jego elementów wynosi t. Naszym certyfikatem będzie wtedy ten szukany podzbiór, którego długość jest oczywiście mniejsza od wejścia (zbioru S), zatem jest wielomianowa. A zsumować elementy możemy liniowo, następnie porównanie z liczbą t to koszt stały. Zatem problem SUBSET-SUM posiada algorytm wielomianowy taki, że mając certyfikat o długości wielomianowej jest w stanie go zweryfikować w czasie wielomianowym. O takich problemach mówimy, że należą do zbioru NP. Oczywiście P zawiera się w NP: skoro możemy rozwiązać problem w czasie wielomianowym to tym bardziej możemy go zweryfikować w czasie wielomianowym.

Najtrudniejsze problemy w NP

Mówimy, że istnieje redukcja z problemu X do problemu Y jeśli istnieje algorytm A działający w czasie wielomianowym przekształcający instancje problemu X w instancje problemu Y w taki sposób, że dla każdej instancji x problemu X: X(x) == TRUE wtedy i tylko wtedy, gdy Y(A(x)) = TRUE. Intuicyjnie wtedy problem Y jest conajmniej tak samo trudny jak X. Okazuje się, że w zbiorze NP istnieją takie problemy, że z dowolnego problemu z NP istnieje do nich redukcja. Jeśli dodatkowo te problemy są w NP, to mówimy o takich problemach, że są NP-zupełne.

Przykładowe problemy NP-zupełne

W zbiorze tym jest wiele ciekawych problemów, np:

  • czy w danym grafie G istnieje cykl Hamiltona (IS-HAMILTONIAN)
  • SUBSET-SUM
  • czy dana formuła logiczna jest spełnialna (SAT)
  • czy dla danego zbioru liczb całkowitych dodatnich S istnieje jego podział na dwa podzbiory taki, że suma ich elementów jest równa (SET-PARTITION)
  • SUPER-MARIO-BROS
  • czy dany graf G zawiera klikę o k wierzchołkach (CLIQUE)

Pierwszy został dowiedziony SAT - pokazano, że z dowolnego problemu z NP istnieje redukcja do SAT oraz że SAT jest w NP. Jest to trudne. Jednak wiedząc już, że dany problem X jest NP-zupełny, aby pokazać NP-zupełność innego problemu Y, musimy tylko pokazać, że Y jest w NP oraz, że istnieje redukcja z X do Y. To czasami jest łatwe, np. pokażmy, że SUBSET-SUM jest NP-zupełny zakładając, że SET-PARTITION jest NP-zupełny:

  1. Oczywiście SUBSET-SUM jest w NP, jak już wyżej pokazaliśmy.
  2. Weźmy dowolną instancje problemu SET-PARTITION, czyli dowolny zbiór liczb całkowitych dodatnich S. Aby przekształcić go w instancje problemu SUBSET-SUM, wystarczy S zostawić takie, jakie jest oraz obliczyć t jako sumę elementów z S podzieloną na 2. Łatwo sprawdzić, że taka redukcja rzeczywiście jest redukcją: wykonuje się ona oczywiście w czasie wielomianowym; jeśli istnieje podział zbioru S na dwa podzbiory o równej sumie elementów, to po naszym przeształceniu oczywiście SUBSET-SUM(A(S))==TRUE, ponieważ oba z podzbiorów z podziału spełniają SUBSET-SUM(A(S)); jeśli nie istnieje taki podział S, to oczywiście nie istnieje taki podzbiór S sumujący się do t, co jest kontrapozycją implikacji lewostronnej.

Dlaczego problemy NP-zupełne są tak ważne?

Okazuje się, że jeśli którykolwiek z problemów NP-zupełnych jest rozwiązywalny w czasie wielomianowym, to wszystkie problemy z NP są rozwiązywalne w czasie wielomianowym, zatem P=NP. Dlaczego? Niech Y będzie problemem NP-zupełnym rozwiązywalnym w czasie wielomianowym, czyli jest O(n^c) dla pewnego c. Wiemy, że z dowolnego problemu X z NP istnieje redukcja wielomianowa (O(n^d) dla pewnego d) do Y. Zatem składając redukcje X->Y z rozwiązaniem Y dostajemy złożoność O(n^(d*c)), czyli wielomianową. Dodatkowo jeśli którykolwiek z problemów z NP nie jest rozwiązywalny w czasie wielomianowym, to żaden nie jest, czyli P!=NP. Aby to pokazać, wystarczy zauważyć, że to stwierdzenie jest kontrapozycją stwierdzenia pierwszego.

Jak zarobić milion dolarów?

Problem, czy P=NP jest jednym z problemów milenijnych, a za rozwiązanie dowolnego z nich jest nagroda miliona dolarów. Wystarczy więc tylko pokazać, że dowolny z problemów NP-zupełnych jest rozwiązywalny w czasie wielomianowym, lub że nie jest. Nie brzmi to jak problem na tyle trudny, że nikt do tej pory nie był w stanie go rozwiązać. Może ty spróbujesz?