Wyobraź sobie szachownicę. Umieść na niej dwie wrogie królowe tak, aby nie mogły się wzajemnie atakować. Łatwe? Dobrze, teraz powtórz ten proces, dodając jeszcze sześć królowych. Skomplikowane, ale możliwe. Na koniec rozszerz problem na plansze o dowolnym rozmiarze, z dowolną liczbą z góry określonych królowych. Tak zwany „problem tysiąca królowych” to nic innego jak odosobniony przykład mający wyjaśnić znacznie bardziej złożone zadanie, „P versus NP”, do tego stopnia, że Instytut Matematyczny Claya oferuje milion dolarów za pierwszą pozytywną demonstrację.
Istnieje bardzo interesujący konkurs, który nazywają „Siedmioma Problemami Milenijnymi”. Zapoczątkowany w roku 2000 przez Instytut Matematyczny Claya, jego celem jest znalezienie odpowiedzi na siedem klasycznych problemów, które opierały się rozwiązaniu przez lata. Jak dotąd jedynym problemem, który otrzymał właściwą demonstrację, jest „Hipoteza Poincarégo”, opracowana przez rosyjskiego matematyka Grigorija Perelmana.
Instytut nie zawahał się zaoferować mu miliona dolarów za jego pracę, ale Perelman odmówił, mówiąc, że jego wkład nie był większy niż wkład matematyka Richarda S. Hamiltona, który wcześniej zaproponował rozwiązanie. Kolejnym wielkim problemem, który instytut pragnie zobaczyć rozwiązany, jest słynne „P versus NP”, a aby spróbować go zrozumieć, najczęściej sięga się po szachownicę:
Nie pomogło? Nie martw się, na początku mnie też niewiele to dało. „P versus NP” jest bardziej skomplikowane niż rzucanie parą królowych na szachownicę, a jego reputacja jako problemu niemożliwego jest w pełni zasłużona. W bardzo luźnych słowach (i mówię „luźnych” z całą powagą) możemy powiedzieć, że problemy oznaczone jako P są łatwe do rozwiązania i zweryfikowania za pomocą algorytmów, w „czasie wielomianowym”.
Z drugiej strony, problemy NP są łatwe do zweryfikowania, czy ich rozwiązanie jest poprawne, czy nie, podczas gdy dojście do niego wymaga wiele czasu i wysiłku, z zauważalną utratą wydajności. Dobrymi przykładami problemów NP są łamigłówki, Sudoku, a nawet Saper. A co by było, gdybyś znalazł klucz do rozwiązania problemu NP w czasie wielomianowym, z dużą wydajnością?
Jeśli ci się to uda, udowodnisz, że nie ma różnic między N i NP (N = NP), co spowoduje, że Instytut Claya (a nie Uniwersytet St. Andrews, jak powtarzano do znudzenia) rzuci w twoją stronę milion dolarów, prawdopodobnie w ślad za nim pójdzie Nagroda Nobla oraz nienawiść ekspertów kryptografii na całym świecie. Większość ekspertów skłania się ku N ≠ NP, a prawdę mówiąc, wiele rzeczy od tego zależy (wspomniane wcześniej szyfrowanie jest jedną z nich). Ale jeśli mimo wszystko spróbujesz... powodzenia. Będziesz go potrzebować.
