Dlaczego nie ma algorytmów aproksymacyjnych dla SAT i innych problemów decyzyjnych?

Mam problem z decyzją o zakończeniu NP. Biorąc pod uwagę przykład problemu, chciałbym zaprojektować algorytm, który wyświetli TAK, jeśli problem jest wykonalny, i NIE, w przeciwnym razie. (Oczywiście, jeśli algorytm nie jest optymalny, popełni błędy.)

Nie mogę znaleźć algorytmów aproksymacyjnych dla takich problemów. Szukałem w szczególności SAT i na stronie Wikipedii o algorytmie aproksymacji znalazłem następujące: Kolejnym ograniczeniem tego podejścia jest to, że dotyczy ono tylko problemów optymalizacyjnych, a nie „czystych” problemów decyzyjnych, takich jak satysfakcja, chociaż często można .. .

Dlaczego na przykład nie definiujemy współczynnika aproksymacji jako czegoś proporcjonalnego do liczby błędów popełnianych przez algorytm? Jak faktycznie rozwiązujemy problemy decyzyjne w sposób zachłanny i nieoptymalny?

Algorytmy aproksymacyjne służą wyłącznie do problemów związanych z optymalizacją, a nie do problemów decyzyjnych.

Dlaczego nie definiujemy współczynnika przybliżenia jako części błędów popełnianych przez algorytm podczas próby rozwiązania problemu decyzyjnego? Ponieważ „współczynnik przybliżenia” jest terminem o dobrze zdefiniowanym, standardowym znaczeniu, który oznacza coś innego, i używanie tego samego terminu dla dwóch różnych rzeczy byłoby mylące.

OK, czy moglibyśmy zdefiniować inny współczynnik (nazwijmy to czymś innym - np. „Współczynnik detekcji”), który określa liczbę błędów popełnianych przez algorytm w przypadku jakiegoś problemu decyzyjnego? Cóż, nie jest jasne, jak to zrobić. Jaki byłby mianownik dla tej frakcji? Innymi słowy: będzie nieskończona liczba przypadków problemów, a dla niektórych z nich algorytm da właściwą odpowiedź, a dla innych złą odpowiedź, więc otrzymamy współczynnik, który jest „coś podzielonego przez nieskończoność”, co ostatecznie nie ma znaczenia ani nie jest zdefiniowane.

Alternatywnie, moglibyśmy zdefiniować jako ułamek błędów, które popełniają błędy algorytmu, w przypadku problemów o rozmiarze n . Następnie moglibyśmy obliczyć granicę r n jako n → ∞ , jeśli taka granica istnieje. To by było$r_n$$n$$r_n$$n \to \infty$być dobrze zdefiniowane (jeśli limit istnieje). Jednak w większości przypadków może to nie być szczególnie przydatne. W szczególności zakłada domyślnie jednolity rozkład przypadków wystąpienia problemów. Jednak w świecie rzeczywistym rzeczywisty rozkład w przypadkach problemowych może nie być jednolity - często jest bardzo daleki od jednolitości. W rezultacie liczba, którą otrzymujesz w ten sposób, często nie jest tak przydatna, jak możesz się spodziewać: często daje mylące wrażenie, jak dobry jest algorytm.

Aby dowiedzieć się więcej o tym, jak ludzie radzą sobie z trudnością (twardość NP), zapoznaj się z Radzenie sobie z trudnością: problemy z NP-zupełnością .

Powodem, dla którego nie widzisz takich współczynników przybliżenia w problemach z podejmowaniem decyzji, jest to, że na ogół nie mają one sensu w kontekście pytań, które zwykle zadaje się na temat problemów z podejmowaniem decyzji. W ustawieniach optymalizacji ma to sens, ponieważ warto być „blisko”. W wielu środowiskach nie ma to sensu. Nie ma sensu widzieć, jak często jesteś „blisko” w dyskretnym problemie logarytmicznym. Nie ma sensu widzieć, jak często jesteś „bliski” znalezienia izomeru grafu. Podobnie w przypadku większości problemów związanych z podejmowaniem decyzji nie ma sensu być „blisko” właściwej decyzji.

Teraz, w praktycznych implementacjach, istnieje wiele przypadków, w których warto wiedzieć, która część problemów może zostać „szybko” ustalona, ​​a która nie. Jednak, w przeciwieństwie do optymalizacji, nie ma jednego uniwersalnego sposobu na określenie tego. Możesz to zrobić statystycznie, jak sugerujesz, ale tylko jeśli znasz rozkład statystyczny swoich danych wejściowych. Przez większość czasu ludzie zainteresowani problemami decyzyjnymi nie mają tyle szczęścia, że ​​mają takie rozkłady.

Jako studium przypadku rozważ problem zatrzymania. Problem zatrzymania jest znany jako nierozstrzygalny. Szkoda, bo to naprawdę przydatny problem, który można rozwiązać, jeśli tworzysz kompilator. W praktyce jednak okazuje się, że większość programów jest w rzeczywistości bardzo łatwa do analizy z perspektywy zatrzymania problemu. Kompilatory wykorzystują to do generowania optymalnego kodu w takich okolicznościach. Kompilator musi jednak rozpoznać, że istnieje możliwość, że określony blok kodu nie będzie rozstrzygalny. Każdy program, który opiera się na „prawdopodobnym rozstrzygnięciu” kodu, może mieć kłopoty.

Jednak metryka używana przez kompilatory do określania, jak dobrze sobie radzą w rozwiązywaniu tych konkretnych przypadków problemu zatrzymania, jest bardzo różna od metryki używanej przez program kryptograficzny do testowania, czy dana para liczb pierwszych jest hartowalna przed atakami. Nie ma jednego uniwersalnego rozwiązania. Jeśli chcesz taką metrykę, będziesz musiał ją dostosować, aby pasowała do konkretnej przestrzeni problemów i logiki biznesowej.

Oprócz istniejących odpowiedzi, chciałbym wskazać, że istnieją sytuacje, w których sensowne jest przybliżone rozwiązanie problemu decyzyjnego, ale działa ono inaczej niż mogłoby się wydawać.

Dzięki tym algorytmom tylko jeden z dwóch wyników jest określany z pewnością, podczas gdy drugi może być niepoprawny. Weźmy na przykład test Millera-Rabina na liczby pierwsze , na przykład: jeśli test ustali, że liczba nie jest liczbą pierwszą, wynik jest na pewno. Ale w innym przypadku oznacza to tylko, że liczba jest prawdopodobnie pierwsza. W zależności od tego, ile czasu obliczeniowego jesteś skłonny zainwestować, możesz zwiększyć swoje zaufanie do wyniku, ale nie będzie to 100%, jak ma to miejsce w przypadku innej niż pierwotna.

Jest to szczególnie przydatne w przypadku nierozwiązywalnych problemów: można napisać narzędzie, które próbuje rozwiązać problem zatrzymania określonego fragmentu kodu. Jeśli znajdzie dowód na to, że program nie będzie się powtarzał bez końca, możesz to zrobić ze 100% pewnością. Jeśli nie możesz znaleźć takiego dowodu, może to oznaczać, że przepływ sterowania programem jest zbyt skomplikowany, aby narzędzie mogło go przeanalizować, ale nie jest to dowód na to, że zapętla się on na zawsze. Upraszczając struktury kontrolne, możesz być w stanie stworzyć równoważny program, który jest wystarczająco prosty, aby narzędzie udowodniło, że na pewno się zatrzyma.