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

18

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?

Ribz
źródło
5
Istnieją algorytmy aproksymacyjne dla MAX-SAT.
Yuval Filmus,
2
MAX-SAT nie jest problemem decyzyjnym, nie?
Ribz,
15
Algorytmy aproksymacyjne służą zawsze do problemów z optymalizacją.
Yuval Filmus
4
Zasadniczo chcesz mieć algorytm, który kończy się szybko, ale czasami może dać złą odpowiedź. Myślę, że bardzo mylicie problemy, używając tutaj dobrze zdefiniowanych terminów, takich jak „algorytm aproksymacyjny” i „optymalny”. Mają bardzo konkretne znaczenie. Myślę, że zamiast tego szukasz heurystyki - jeśli zaktualizujesz swoje pytanie tym terminem (lub zaczniesz od nowa z nowym pytaniem, aby uniknąć jeszcze większego zamieszania), możesz uzyskać lepsze wyniki.
AnoE
Chociaż nie jest to kompletna odpowiedź, wyjaśnia część przyczyny: istnieją ważne problemy SAT, dla których błędne podanie niskiego bitu nie jest lepsze niż bycie błędnym o połowę.
Joshua,

Odpowiedzi:

33

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łornnrnnbyć 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ą .

DW
źródło
3
+1. Ale ostatni punkt nie jest solidny, można argumentować, że można zdefiniować współczynnik aproksymacji jako granicę, gdy n idzie do nieskończoności liczby błędów, które program popełnia przy wprowadzaniu długości n względem liczby ciągów długości n. To oczywiście okazuje się nieprzydatne, ponieważ często prosty program, który po prostu wypisuje „TAK” (lub „NIE”) osiąga dobry stosunek (czasem nawet 1!).
aelguindy,
1
@det, to osobne pytanie, które należy zadać osobno (po przeczytaniu o tym w standardowych podręcznikach lub zasobach online). Wolimy zadać tylko jedno pytanie na post.
DW
1
@aelguindy, dobry punkt. Zaktualizowałem odpowiednio swoją odpowiedź.
DW
2
@det Dlaczego chciwy? Co to znaczy „prawie” rozwiązać problem decyzyjny?
Raphael
2
@ Mehrdad: Zwykle oceniasz algorytm aproksymacji na podstawie jego najgorszego błędu: górnej granicy tego, jak nie zawsze jest on optymalny. Na przykład można powiedzieć, że dany algorytm aproksymacji zawsze znajduje wynik, który stanowi co najmniej pięć szóstych wyniku optymalnego. Nie ma prawdziwego sposobu na przełożenie tego na problem decyzyjny; jeśli twój algorytm czasami emituje (powiedzmy) 0,1, to albo czasem jest wyłączony o 0,9 (w takim przypadku lepiej byłoby, w najgorszym przypadku, zawsze emitować 0,5), albo „przybliżona” -świadomość jest pozorna i „0,1 „w rzeczywistości oznacza po prostu„ 0 ”.
ruakh
14

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.

Cort Ammon - Przywróć Monikę
źródło
Tak więc, jak rozumiem, jedynym sposobem rozwiązania problemu decyzyjnego jest zaprojektowanie optymalnego algorytmu, który może być bardzo nieefektywny? Ponieważ mam problem decyzyjny (NP-complete) i zostałem poproszony o wymyślenie chciwego (szybkiego) algorytmu w celu znalezienia rozwiązania. Jak mogę to rozwiązać? Czy znasz jakieś artykuły dotyczące tego rodzaju problemów?
Ribz
1
@det Odepchnij i przywróć problem. Jeśli masz problem z NP-zupełnością, raczej utkniesz, ale jest wysoce prawdopodobne, że tak naprawdę nie musisz go rozwiązywać. Na przykład nie zawsze potrzebujesz idealnej odpowiedzi. Może wystarczająco blisko jest wystarczająco blisko. A może możesz rozwiązać problem w przypadku podzbioru spraw, które są łatwe, i wybrać te, które są trudne. Na przykład algorytmy upakowania są często kompletne z NP, ale powszechne są algorytmy, które niezawodnie osiągają 5% optymalnego przy zastosowaniu podejść probabalistycznych.
Cort Ammon - Przywróć Monikę
2
Szczerze mówiąc, polecenie wymyślenia chciwego algorytmu rozwiązania programu NP-zupełnego jest dosłownie tym samym, co zadanie samodzielnego przejęcia całej społeczności informatycznej / matematycznej. Jeśli okaże się, algorytm dla NP-pełnego programu w P momencie na bardzo najmniej byś zarobić $ 1 mln Clay nagrodę za rozwiązywanie P = NP. W rzeczywistości skutki twojego odkrycia zmieniłyby obliczenia, jakie znamy, i całkowicie przewróciły całą branżę bezpieczeństwa / kryptografii z dnia na dzień. Lepiej dopasować sformułowanie zadania, aby nie było w pełni możliwe do wykonania w NP.
Cort Ammon - Przywróć Monikę
Użyłem chciwego dokładnego algorytmu dla problemu pełnego NP. Musiałem tylko rozwiązać małą sprawę i mogłem uzyskać serwer z 64 procesorami na weekend.
Patricia Shanahan,
8

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.

ComicSansMS
źródło
Istnieje duża różnica między algorytmami probabilistycznymi (twoja odpowiedź) i aproksymacyjnymi (pytanie). W szczególności połączenie obu jest bardzo specjalną rasą.
Raphael
Wiemy również, że algorytmy probabilistyczne dla problemu zatrzymania nie istnieją, zakładając rozsądną interpretację tego terminu w tym kontekście.
Raphael
@ Rafael Nie chciałem, aby moja odpowiedź była specyficzna dla algorytmów probabilistycznych. To prawda, że ​​tak jest w przypadku Millera-Rabina, ale jak sam o tym wspomniałeś, nie jest to już prawdą w przypadku problemu z zatrzymaniem i myślę, że nie będzie to również prawdą w większości przypadków, w których znajdziesz takie zachowanie. Chodziło mi o to, że po prostu uzyskasz pewność co do jednego wyniku, ale nie do drugiego.
ComicSansMS
Jeśli nie mówisz więcej, że niektóre problemy są tylko częściowo obliczalne, nie sądzę, że odpowiadasz na pytanie.
Raphael
@Raphael Moja odpowiedź również nie jest specyficzna dla problemów częściowo obliczalnych. W rzeczywistości nie sądzę, aby opisywane przeze mnie podejście miało zastosowanie nawet do problemów częściowo obliczalnych. Tam na pewno będziesz teraz, jeśli wylądowałeś w nieokreślonej gałęzi funkcji, dzięki czemu możesz z całą pewnością stwierdzić, że nie ma rezultatu. To, co opisałem, sprowadza się do: Być może istnieje odpowiedź, ale algorytm mógł nie wyglądać na tyle mocno, by się na nią natknąć.
ComicSansMS