Problemy z optymalizacją „NP-complete”

Jestem nieco zdezorientowany pewną terminologią, którą napotkałem, dotyczącą złożoności problemów związanych z optymalizacją. W klasie algorytmów miałem duży problem z oszczędnością opisany jako NP-zupełny. Nie jestem jednak do końca pewien, co oznacza termin NP-complete w kontekście problemu optymalizacji. Czy to tylko oznacza, że odpowiedni problem decyzyjny jest NP-zupełny? Czy to oznacza, że problem optymalizacji może być trudniejszy (być może poza NP)?

W szczególności niepokoi mnie fakt, że chociaż problem decyzyjny związany z całkowitą NP może być weryfikowany w czasie wielomianowym, rozwiązanie odpowiedniego problemu optymalizacji nie wydaje się być weryfikowalne w czasie wielomianowym. Czy to oznacza, że problem tak naprawdę nie występuje w NP, czy też wielomianowa weryfikowalność czasowa jest jedynie cechą problemów decyzyjnych NP?

complexity-theory np-complete terminology Aniket Schneider
źródło

sprawdź to pytanie

Ran G.

Także to pytanie: optymalizacyjna wersja problemów decyzyjnych .

Kaveh

@RanG., Nie jestem pewien, czy jest to dokładny duplikat.

Kaveh

@Kaveh masz rację, ale świetna odpowiedź uli w pełni odpowiada na to pytanie.

Ran G.

@RanG., Może być więcej niż jedna świetna odpowiedź. :)

Kaveh

Odpowiedzi:

Próba częściowej odpowiedzi:

Problemy decyzyjne były już badane przez pewien czas, zanim pojawiły się problemy z optymalizacją , w tym sensie, że są one traktowane z perspektywy algorytmów aproksymacyjnych.

Należy zachować ostrożność przy przenoszeniu pojęć z problemów decyzyjnych. Można to zrobić i podać dokładne pojęcie kompletności NP dla problemów optymalizacyjnych. Spójrz na tę odpowiedź . Oczywiście różni się od NP-kompletności problemów decyzyjnych, ale opiera się na pomysłach sames (redukcjach).

Jeśli masz do czynienia z problemem optymalizacji, który nie pozwala na weryfikację wykonalnego rozwiązania, niewiele możesz zrobić. Dlatego zwykle zakłada się, że:

Możemy skutecznie zweryfikować, czy dane wejściowe są faktycznie prawidłowym wystąpieniem naszego problemu z optymalizacją.
Rozmiar możliwych rozwiązań jest wielomianowo ograniczony przez wielkość danych wejściowych.
Możemy skutecznie zweryfikować, czy rozwiązanie jest wykonalnym rozwiązaniem wkładu.
Wartość rozwiązania można skutecznie ustalić.

W przeciwnym razie nie możemy wiele osiągnąć.

$\mathrm{NP}$ $\mathrm{NP}$ $\mathrm{NP}$

Jeśli chcesz sprawdzić, czy rozwiązanie jest nie tylko wykonalne, ale także optymalne, powiedziałbym, że jest to tak trudne, jak rozwiązanie pierwotnego problemu optymalizacji, ponieważ aby obalić dane wykonalne i możliwie optymalne rozwiązanie jako nieoptymalne, musisz podać lepsze rozwiązanie, które może wymagać znalezienia prawdziwego optymalnego rozwiązania.

Ale to nie znaczy, że problem optymalizacji jest trudniejszy. Zobacz tę odpowiedź , która zależy oczywiście od dokładnych definicji.

uli
źródło

Czy możesz podać artykuł lub odniesienie do książki, w której mogę znaleźć więcej informacji na temat dokładnej definicji, redukcji itp. Twardości NP w przypadku problemów z optymalizacją? Jak dotąd nie udało mi się tego rozgryźć. To byłoby dla mnie bardzo interesujące. Dziękuję Ci.

John Threepwood,

@John Spróbuj algorytmy przybliżenie problemów NP-trudnych lub złożoności i zbliżenia lub Zbliżanie algorytmów

Uli

-1

Przyczyną większości problemów optymalizacyjnych jako P, NP, NP-complete itp. Są warunki Kuhna-Tuckera. Opowiem o problemach z programowaniem liniowym, ale KTC ma zastosowanie w wielu innych problemach związanych z optymalizacją. Dla każdego problemu optymalizacji występuje problem podwójny. Jeśli celem pierwotnego problemu jest maksymalizacja niektórych funkcji, wówczas podwójny (zwykle) ma funkcję, którą należy zminimalizować. * Wykonalne, ale nieoptymalne rozwiązania pierwotnego problemu będą niewykonalne / nieważne dla podwójnego problemu i odwrotnie -versa. Jeśli i tylko wtedy, gdy rozwiązanie jest możliwe dla pierwotnego i podwójnego, jest to optymalne rozwiązanie dla obu. (Technicznie może to być jedno z wielu optymalnych rozwiązań, które dają ten sam rezultat).

Zatem znalezienie optymalnego rozwiązania problemu optymalizacji jest równoważne ze znalezieniem prawidłowego rozwiązania dla pierwotnego i podwójnego. Możesz użyć algorytmów optymalizacyjnych, aby znaleźć to rozwiązanie, ale cały proces jest dowodem na istnienie.

Jeśli chcesz przełączyć od minimalizacji do maksymalizacji, pomnóż funkcję celu przez -1.

Robert I. Eachus
źródło

Nie rozumiem, jak warunki KKT odnoszą się do twardości NP, czy mógłbyś to rozwinąć?

Dyskretna jaszczurka

Naprawdę nie rozumiem, jak to odpowiada na pytanie. P , NP itp. Są klasami problemów decyzyjnych. Problemy z optymalizacją nie są problemami decyzyjnymi, więc z definicji nie należą do żadnej z tych klas .

David Richerby,

Nie rozumiem też, jak to odpowiada na pytanie - to ciekawy komentarz, ale wydaje się, że odpowiada na inne pytanie niż zadane. Pytanie brzmi, co to znaczy powiedzieć, że problem optymalizacji jest NP-kompletny i czy można powiedzieć, że problemy optymalizacji występują w NP, biorąc pod uwagę, że nie są one problemem decyzyjnym. Opisuje to, w jaki sposób, biorąc pod uwagę problem optymalizacji (gdzie rozwiązania nie są weryfikowalne), często możemy skonstruować odpowiedni problem, w którym rozwiązania można zweryfikować. Bardzo interesujące rzeczy, ale nie jestem pewien, czy odpowiada na zadane pytanie.

@DW Głównym powodem, dla którego uważam, że tak naprawdę nie jest odpowiedź na pytanie, jest to, że oprócz tego, co już wspomniano, KKT ogranicza ustawienie do matematycznej optymalizacji funkcji „regularnych” (np. Ciągłych, różnicowalnych, wypukłych). To ustawienie nie ma zastosowania do większości problemów trudnych dla NP.

Dyskretna jaszczurka