problem P kontra NP
to co w takim razie, problem P kontra NP?
dla przypomnienia, status quo jest taki, że P≠NP.
p (czas wielomianowy) odnosi się do klasy problemów, które mogą być rozwiązane przez algorytm w czasie wielomianowym. Problemy w klasie P mogą wahać się od wszystkiego tak prostego jak mnożenie do znalezienia największej liczby na liście. Są stosunkowo „łatwiejszym” zestawem problemów.
NP (non-deterministyczny czas wielomianowy) odnosi się do klasy problemów, które mogą być rozwiązane w czasie wielomianowym przez komputer niedeterministyczny., Jest to zasadniczo inny sposób powiedzenia „Jeśli mam nieograniczoną moc obliczeniową (tj. tyle komputerów, ile potrzebuję), jestem w stanie rozwiązać każdy problem w co najwyżej wielomianowym czasie”. Bardziej intuicyjnie jednak odnosi się do klasy problemów, które obecnie nie mają możliwości znalezienia szybkiej (czas wielomianowy) odpowiedzi wystarczającej, ale mogą być szybko zweryfikowane (w czasie wielomianowym), jeśli jeden dostarcza rozwiązanie problemu. Termin zweryfikowany tutaj oznacza, że można sprawdzić, czy podane rozwiązanie jest rzeczywiście poprawne.
wyraźnie, na podstawie powyższej definicji, P ⊆ NP., Spójrzmy na przykład, aby zilustrować ten abstrakcyjny problem.
jednym z najczęstszych, ale skutecznych przykładów jest Sudoku. Biorąc pod uwagę nierozwiązaną siatkę Sudoku (na przykład 9 x 9), algorytm zajmie sporo czasu, aby ją rozwiązać. Jeśli jednak siatka 9 x 9 wzrośnie do siatki 100 x 100 lub 10 000 x 10 000, czas potrzebny na jej rozwiązanie zwiększy się wykładniczo, ponieważ sam problem staje się znacznie trudniejszy., Jednak biorąc pod uwagę rozwiązaną siatkę Sudoku (9 x 9), dość łatwo jest sprawdzić, czy dane rozwiązanie jest rzeczywiście poprawne, nawet jeśli rozmiar skaluje się do 10 000 na 10 000. Byłoby wolniej, ale czas na sprawdzenie rozwiązania wzrasta wolniej (wielomianowo).
istnieje wiele innych problemów NP, w tym problem Plecaka i problem podróżujących sprzedawców.są one podobne, ponieważ są trudne do rozwiązania, ale szybkie do zweryfikowania., Podstawowym problemem, który staramy się rozwiązać jest:
czy możliwość szybkiego rozpoznawania poprawnych odpowiedzi NP oznacza, że istnieje również szybki sposób ich znalezienia?
Jeśli tak (tj. P=NP), może to znacznie zmienić sposób patrzenia na te problemy NP, ponieważ oznacza to, że istnieje szybki sposób rozwiązania wszystkich tych problemów, tylko że nie byliśmy w stanie dowiedzieć się jeszcze jak.
jeśli to nie jest wystarczająco skomplikowane, urozmaicajmy to.,
wśród tych problemów NP istnieje król wszystkich problemów, które badacze nazywają np-problemami kompletnymi. Formalnie są one zbiorem problemów, z których każdy inny problem NP może być zredukowany (rozwiązany poniżej) w czasie wielomianowym i którego rozwiązanie może być jeszcze zweryfikowane w czasie wielomianowym. Oznacza to, że każdy problem NP może zostać przekształcony w problem np-kompletny.
nieformalnie są to „najtrudniejsze” problemy np., Jeśli więc jeden problem np-zupełny może być rozwiązany w czasie wielomianowym, to każdy problem np-zupełny może być rozwiązany w czasie wielomianowym, a każdy problem NP-zupełny może być rozwiązany w czasie wielomianowym (tj. P=NP). Najbardziej znanym przykładem może być problem podróżujących sprzedawców.
istnieje również zestaw problemów o nazwie np-Hard problems., Problemy te są co najmniej tak trudne jak problemy NP, ale bez warunku, który wymaga rozwiązania w czasie wielomianowym. Sugeruje to, że problemy np-Hard niekoniecznie muszą być częścią klasy NP. Przykładem może być rozwiązanie szachownicy – biorąc pod uwagę stan szachownicy, prawie niemożliwe jest stwierdzenie, czy dany ruch w danym stanie jest w rzeczywistości optymalnym ruchem. Formalnie nie istnieje algorytm czasu wielomianowego pozwalający zweryfikować rozwiązanie problemu np-Hard.,
jeśli połączymy je razem, problem np-zupełny oznacza, że jest np-twardy, ale problem np-twardy nie oznacza, że jest np-kompletny.
Definiowanie np-kompletności
problem L, jest np-kompletnością, jeśli:
- L jest np-twardym
- l należy do NP
poniższy schemat (skupienie na lewej stronie) powinien wyjaśnić sprawę.,
Wait, what does it mean by reducing A to B?
Reduction forms the crux of NP-Completeness.,
nieformalnie problem L1 można zredukować do innego problemu L2, jeśli:
- każda instancja L1 może być modelowana jako instancja L2
- rozwiązanie tego ostatniego zapewnia rozwiązanie dla pierwszego i odwrotnie
aby zrozumieć to intuicyjnie, można myśleć o tym w taki sposób:
Jeśli L1 jest redukowalny do L2, L1 musi być co najwyżej tak twardy jak L2. I odwrotnie, L2 musi być co najmniej tak twarde jak L1.
matematycznie jest to oznaczane jako: L1 ≤p L2 (odczytywane jako „L1 jest wielomianowo redukowalne do L2”).,
