"Problem NP-zupełny" - oto jeden z ważnych terminów jaki dotyczy algorytmów ⚠️. Zapraszam do środka po wyjaśnienia i nie uciekać mi od tego, tylko dlatego, że nazwa może śmiesznie brzmieć 😄!
PROBLEM NP-ZUPEŁNY WYMAGA SPRYTU, ABY DAŁO SIĘ GO ROZWIĄZAĆ W ROZSĄDNYM CZASIE
Celem zrozumienia tego terminu, musimy wpierw wytłumaczyć sobie serię innych pojęć z nim związanych 😧.
TERMINOLOGIA
Problem NP-zupełny dotyczy takich tematów, jak 👇:
- problem decyzyjny,
- klasa złożoności,
- klasa NP.
To nie jest artykuł na pełne wyjaśnienie wszystkich tych pojęć razem wziętych, zatem każdy z nich tylko pobieżnie wytłumaczę ℹ️.
PROBLEM DECYZYJNY
Każdy algorytm, to przepis na jakiś problem 🙂. W nauce o algorytmach przoduje określenie "problem decyzyjny" (ang. decision problem), czyli tak sformułowany problem, na który możemy odpowiedzieć "tak" lub "nie" ✅❌. Przykłady takich sformułowań, to 👇:
- Czy działanie arytmetyczne: "3 + 3", równa się 6?
- Czy dla zadanych liczb, ich suma jest parzysta?
- Czy dla zadanego grafu, istnieje ścieżka od węzła początkowego do węzła końcowego?
W każdym z tych przykładów, można udzielić odpowiedzi "tak" albo "nie". Na tym to polega 😄!
KLASA ZŁOŻONOŚCI
A teraz czym jest klasa złożoności (ang. complexity class) 😲. To jest zbiór problemów decyzyjnych "pogrupowanych" w pewną złożoność czasową (tylko czasową) ⌚. Najważniejszym kryterium przy klasyfikacji jest czas - nie mierzymy według pamięci czy jakiejkolwiek innej metryki ℹ️.
Jest kilka różnych klas złożoności znanych w algorytmice, natomiast są 2 najbardziej podstawowe, o których powinno się mieć jakieś pojęcie 👇:
- P,
- NP.
Wiem, że terminy są nietypowe, jednak zaraz się dowiesz o co chodzi w tym zapisie 💡.
Teraz pytanie co mają problemy decyzyjne do klas złożoności 🤔. Najprościej pisząc, chodzi o ustalenie "stopnia trudności" wyznaczenia rozwiązania danego problemu 📶. Jak miałeś(-aś) okazję zauważyć na podawanych przeze mnie przykładach, nie wszystkie problemy da się rozwiązać w prosty sposób 😦. Na przykład takie algorytmy, jak 👇:
są możliwe do rozwiązania w racjonalnym czasie ("racjonalnym", czyli ich złożoność czasowa jest do zaakceptowania ✔️). Ale już takie problemy, jak:
wymagały obejścia w postaci algorytmu wyznaczającego rozwiązanie przybliżone z powodu wykładniczej złożoności czasowej ⚠️. A ona z kolei powstaje w wyniku konieczności sprawdzenia wszystkich dostępnych możliwości celem "wskazania palcem" na "to jedyne" 🫵. Także problem NP-zupełny można łatwo rozpoznać po wykładniczym wzroście czasu potrzebnego na jego rozwiązanie ℹ️.
Po to są te klasy złożoności 🚀! Każdy problem jest przydzielony do jakiejś klasy, a ich przynależność zależy właśnie od tego "stopnia trudności" 🚥.
"Granicą" stawianą pomiędzy tymi klasami, jest wielomian 🔥. Podstawą uklasyfikowania danego problemu decyzyjnego do takiej czy innej klasy, jest ustalenie czy jest możliwe wyznaczenie jego rozwiązania w czasie wielomianowym ‼️. To jest bardzo ważne zdanie, które stanowi "clue" dzisiejszego tematu 🔔!
Poniższe złożoności czasowe (podane w notacji dużego O):
O(n), O(n*log(n)), O(n2)
są jak najbardziej złożonościami wielomianowymi 👍. Natomiast poniższe notacje:
O(n!), O(2n), O(nn)
reprezentują złożoność "pozawielomianową", przy czym traktuj to określenie jako duży skrót myślowy ⚠️!
KLASA NP
Zostało nam ostatnie pojęcie do rozwikłania, czyli "NP". Nawet nie myśl o "na przykład", bo nie o to idzie 😆. "NP" to skrót od określenia "non-deterministic polynomial time", czyli "czas niedeterministyczny wielomianowy" 🤯.
Powiedzieliśmy sobie, że fundamentalnym czynnikiem oceny danego problemu do jakiej klasy go przydzielić jest to, czy jego złożoność czasowa jest wielomianowa ℹ️. Klasa NP jest dla tych problemów, których nie da się rozwiązać w czasie wielomianowym ❌. Jest to możliwe jedynie przy użyciu niedeterministycznej maszyny Turinga - modelu, który w teorii posiadałby możliwość kopiowania się na tyle sztuk, ile wynika z mocy zbioru aktualnie dostępnych możliwości (przejść) w danej iteracji 😱.
Deterministyczna odmiana tej maszyny jest w stanie wykonywać tylko jeden rozkaz w tym samym czasie. Niedeterministyczna maszyna Turinga pozwalałaby na "rozchodzenie się" wielu kopii maszyny zależnie od liczby przejść, do których ona zmierza (piszę w trybie przypuszczającym, bo to jest tylko model teoretyczny!) ⏩. To właśnie oznacza "non-deterministic" 💡! Gdyby to było realne, to powstawałoby tyle maszyn Turinga, do ilu wszystkich możliwych stanów mogłaby ona przejść, co skutecznie sprowadziłoby złożoności wykładnicze do postaci wielomianowej 👍.
Maszyna Turinga była pierwszym w historii krokiem w stronę algorytmiki i rozwiązywania problemów algorytmicznych. Dlatego odgrywa cholernie istotną rolę w klasach złożoności 🔥!
To tyle teorii o tych 3 pojęciach 🙂. Możemy przejść do najważniejszej części 🔍!
NP-ZUPEŁNOŚĆ
Teraz co oznacza "NP-zupełność" (ang. NP-completeness) 💯. To jest własność problemu decyzyjnego, który spełnia jednocześnie 2 warunki 👇:
- należy do klasy NP,
- jest NP-trudny (jego rozwiązanie jest co najmniej tak trudne, jak rozwiązanie każdego problemu z klasy NP).
NP-trudność to osobna własność "stojąca" obok NP-zupełności ℹ️. Można pomyśleć, że są ze sobą "spokrewnione", jednak to nieprawda ⛔! Pamiętaj: każdy problem NP-zupełny jest jednocześnie NP-trudny, lecz nie każdy problem NP-trudny, jest NP-zupełny 😱! O NP-trudności napiszę odrębny artykuł 📰.
Także podsumowując całą teorię 😅:
- klasa NP to taki zbiór problemów decyzyjnych, których rozwiązanie jest możliwe w czasie wielomianowym tylko przy użyciu niedeterministycznej maszyny Turinga,
- problem NP-zupełny to problem decyzyjny należący do klasy NP, którego rozwiązanie jest co najmniej tak trudne, jak rozwiązanie każdego problemu z klasy NP.
No, to wszystko wyjaśnione 😅!
SPOSOBY ROZWIĄZYWANIA PROBLEMÓW NP-ZUPEŁNYCH
W przypadku takich problemów, użycie algorytmu dokładnego odpada (tzw. "brutalny" typu "brute-force") ❌. Zdecydowanie lepiej przesiąść się wtedy na aproksymację (i ewentualną zachłanność) 💡. Problem NP-zupełny przestanie być takim dylematem dopiero, gdy wejdą komputery kwantowe 😉.
 |
Problem NP-zupełny należy do klasy problemów decyzyjnych NP i jednocześnie jest problemem NP-trudnym.
Koniec 🎬! Trochę Cię obciążyłem skomplikowanymi tłumaczeniami i terminami, jednak tam, gdzie wkracza matematyka, tam musi być dokładność 🎯. I tak starałem się pokazać o co chodzi bez wchodzenia w enigmatyczne symbole, zwłaszcza z myślą o osobach, które chcą zdać 😊.