Problem komiwojażera — P kontra NP

Co się właśnie stało?

Komiwojażer musi odwiedzić wszystkie n miast dokładnie raz i wrócić do punktu startu, szukając najkrótszej możliwej trasy. Zwiększyliśmy liczbę miast z 6 do 15, a liczba możliwych tras do sprawdzenia eksplodowała z 60 do ponad 43 589 145 600.

Model: ile jest wszystkich tras?

Trasa to permutacja n miast, ale punkt startowy jest dowolny (dzielimy przez n), a trasa przebyta w obu kierunkach ma tę samą długość (dzielimy przez 2). Zostaje:

Dla n = 5 to tylko 12 tras — łatwo sprawdzić wszystkie ręcznie. Dla n = 10 to już 181 440 tras. Dla n = 15 to ponad 43 589 145 600 (43,6 miliarda) tras. A dla n = 20 to ponad 60 kwadrylionów — więcej, niż najszybszy komputer świata zdołałby sprawdzić przez wieki.

P kontra NP — jedno z najważniejszych pytań matematyki

Problem komiwojażera to klasyczny przykład problemu NP-trudnego: rozwiązanie (konkretną trasę) łatwo sprawdzić — wystarczy zsumować odcinki i porównać z limitem X. Ale nie znamy żadnego szybkiego (wielomianowego) sposobu, by taką najkrótszą trasę znaleźć dla dużych n — jedyna pewna metoda to sprawdzenie (niemal) wszystkich (n-1)!/2 możliwości. Stephen Cook sformalizował to pytanie w 1971 r.: czy każdy problem, którego rozwiązanie da się szybko zweryfikować (klasa NP), da się też szybko znaleźć (klasa P)? To pytanie „P kontra NP" pozostaje nierozwiązane — Instytut Matematyczny Claya umieścił je w 2000 r. na liście 7 „Problemów Milenijnych", oferując milion dolarów za dowód. Większość informatyków podejrzewa, że P ≠ NP, ale nikt tego nie udowodnił.

Co to znaczy w praktyce?

To nie tylko akademicka ciekawostka. Bezpieczeństwo współczesnej kryptografii (w tym szyfrowania RSA, które chroni Twoje hasła i transakcje online) opiera się na założeniu, że pewne problemy są łatwe do zweryfikowania, ale trudne do rozwiązania. Gdyby ktoś udowodnił, że P = NP, i wskazał szybki algorytm — większość dzisiejszej kryptografii przestałaby być bezpieczna.

Po co Ci to na maturze:

Silnia (n-1)! i dzielenie przez symetrie (kierunek, punkt startu) to standardowy chwyt kombinatoryczny z rozszerzenia matematyki — te same zasady liczenia permutacji z ograniczeniami pojawiają się w zadaniach o ustawianiu osób w rzędzie czy przy okrągłym stole.

Zapamiętaj: liczba tras komiwojażera wynosi dokładnie (n-1)!/2, niezależnie od tego, jak miasta są rozmieszczone na mapie — i rośnie silniowo, czyli szybciej niż jakakolwiek funkcja wielomianowa lub wykładnicza. To dlatego problem komiwojażera jest NP-trudny, a pytanie „P kontra NP" wciąż czeka na rozwiązanie.