pisaliśmy o wydajnych algorytmach do rozwiązywania złożonych problemów, takich jak najkrótsza ścieżka, Wykres Eulera, Minimalne drzewo rozpinania itp. To były historie sukcesu projektantów algorytmów. W tym poście omówiono historie niepowodzeń informatyki.
czy wszystkie problemy obliczeniowe można rozwiązać za pomocą komputera? Istnieją problemy obliczeniowe, których algorytmy nie mogą rozwiązać nawet w nieograniczonym czasie. Na przykład problem z zatrzymaniem Turinga (biorąc pod uwagę program i dane wejściowe, czy program ostatecznie zatrzyma się, gdy zostanie uruchomiony z tym wejściem, czy będzie działał na zawsze). Alan Turing udowodnił, że ogólny algorytm rozwiązywania problemu zatrzymania dla wszystkich możliwych par program-wejście nie może istnieć. Kluczową częścią dowodu jest to, że maszyna Turinga została użyta jako matematyczna definicja komputera i programu (Problem zatrzymania Źródła).
Status np Complete problems to kolejna historia niepowodzenia, np complete problems to problemy, których status jest nieznany. Żaden algorytm czasu wielomianowego nie został jeszcze Odkryty dla żadnego pełnego problemu np, ani nikt nie był jeszcze w stanie udowodnić, że żaden algorytm czasu wielomianowego nie istnieje dla żadnego z nich. Interesujące jest to, że jeśli którykolwiek z np zupełnych problemów może być rozwiązany w czasie wielomianowym, to wszystkie z nich mogą być rozwiązane.
czym są problemy NP, P, NP-kompletne i np-trudne?
P to zbiór problemów, które można rozwiązać za pomocą deterministycznej maszyny Turinga w czasie wielomianowym .
NP jest zbiorem problemów decyzyjnych, które mogą być rozwiązane przez niedeterministyczną maszynę Turinga w czasie wielomianowym. P jest podzbiorem NP (każdy problem, który może być rozwiązany przez maszynę deterministyczną w czasie wielomianowym, może być również rozwiązany przez maszynę niedeterministyczną w czasie wielomianowym).
nieformalnie, NP jest zbiorem problemów decyzyjnych, które mogą być rozwiązane przez czas wielomianowy za pomocą „algorytmu Szczęścia”, magicznego algorytmu, który zawsze dokonuje słusznego odgadnięcia pomiędzy danym zbiorem wyborów (źródło Ref 1).
NP-problemy kompletne są najtrudniejszymi problemami w zestawie NP. Problem decyzyjny L jest np-kompletny, jeśli:
1) L jest w NP (dowolne rozwiązanie problemów np-zupełnych można szybko zweryfikować, ale nie ma skutecznego rozwiązania).
2) Każdy problem w NP jest redukowany do L w czasie wielomianowym (redukcja jest zdefiniowana poniżej).
problem jest np-Hard jeśli podąża za właściwością 2 wspomnianą powyżej, nie musi podążać za właściwością 1. Dlatego np-komplet jest również podzbiorem np-Hard set.
problemy decyzyjne a optymalizacyjne
np-kompletność dotyczy sfery problemów decyzyjnych. Został on tak skonfigurowany, ponieważ łatwiej jest porównać trudność problemów decyzyjnych niż problemów optymalizacyjnych. W rzeczywistości jednak możliwość rozwiązania problemu decyzyjnego w czasie wielomianowym często pozwala nam rozwiązać odpowiedni problem optymalizacji w czasie wielomianowym (używając wielomianowej liczby wywołań do problemu decyzyjnego). Tak więc omawianie trudności problemów decyzyjnych jest często naprawdę równoważne z omawianiem trudności problemów optymalizacyjnych. (Źródło Nr 2).
na przykład rozważ problem pokrywania wierzchołków (biorąc pod uwagę wykres, znajdź zestaw wierzchołków o minimalnej wielkości, który obejmuje wszystkie krawędzie). Jest to problem optymalizacji. Odpowiadający problem decyzyjny polega na tym, że biorąc pod uwagę nieregulowany Wykres G i k, czy istnieje pokrycie wierzchołkowe o rozmiarze k?
Co To jest redukcja?
niech L1 i L2 będą dwoma problemami decyzyjnymi. Załóżmy, że algorytm A2 rozwiązuje L2. Oznacza to, że jeśli Y jest wejściem dla L2, to algorytm A2 odpowie Tak lub nie w zależności od tego, czy y należy do L2, czy nie.
chodzi o to, aby znaleźć transformację z L1 do L2, aby algorytm A2 mógł być częścią algorytmu A1 do rozwiązania L1.
redukcja uczenia się w ogóle jest bardzo ważna. Na przykład, jeśli mamy funkcje biblioteczne, aby rozwiązać pewien problem i jeśli możemy zredukować nowy problem do jednego z rozwiązanych problemów, oszczędzamy dużo czasu. Rozważmy przykład problemu, w którym musimy znaleźć minimalną ścieżkę produktu w danym wykresie kierowanym, gdzie iloczyn ścieżki jest mnożeniem ciężarów krawędzi wzdłuż ścieżki. Jeśli mamy Kod algorytmu Dijkstry, aby znaleźć najkrótszą ścieżkę, możemy wziąć dziennik wszystkich wag i użyć algorytmu Dijkstry, aby znaleźć minimalną ścieżkę produktu, zamiast pisać nowy kod dla tego nowego problemu.
Jak udowodnić, że dany problem jest np kompletny?
z definicji np-complete wynika, że nie można udowodnić, że problem L jest np-Complete. Z definicji, wymaga od nas, aby pokazać, że każdy problem w NP jest wielomianem czasu redukowanego do L. na szczęście istnieje alternatywny sposób, aby to udowodnić. Chodzi o to, aby wziąć znany np-kompletny problem i zmniejszyć go do L. Jeśli redukcja czasu wielomianu jest możliwa, możemy udowodnić, że L jest np-zupełne przez przechodniość redukcji (jeśli problem np-zupełny jest redukowalny do L w czasie wielomianowym, to wszystkie problemy są redukowalne do L w czasie wielomianowym).
Jaki był pierwszy problem udowodniony jako np-kompletny?
musi być jakiś pierwszy problem np-zupełny udowodniony przez definicję np-zupełnych problemów. SAT (Boolean satisfiability problem) to pierwszy np-kompletny problem udowodniony przez Cooka (Zobacz książkę CLRS dla dowodu).
wiedza o NP-kompletności jest zawsze przydatna nawet dla inżynierów. Załóżmy, że zostaniesz poproszony o napisanie wydajnego algorytmu, który rozwiąże niezwykle ważny problem dla Twojej firmy. Po wielu przemyśleniach można wymyślić tylko wykładnicze podejście czasowe, które jest niepraktyczne. Jeśli nie wiesz o NP-kompletności, możesz tylko powiedzieć, że nie mogłem przyjść z wydajnym algorytmem. Jeśli wiesz o NP-zupełności i udowodnisz, że problem jako np-zupełny, możesz z dumą powiedzieć, że rozwiązanie czasu wielomianowego jest mało prawdopodobne. Jeśli jest możliwe rozwiązanie czasu wielomianowego, To rozwiązanie to rozwiązuje duży problem informatyki, którego wielu naukowców starało się od lat.
wkrótce będziemy omawiać więcej problemów np-zupełności i ich dowód na np-kompletność.