Prawie zawsze prawie w porządku

11

Szukam klasy złożoności, który dotyczy APX jako BPP dotyczy P. Już samo pytanie tutaj , ale być może będzie TCS być bardziej owocne lokalizacja odpowiedzi.

Powodem tego pytania jest to, że w praktycznych problemach często trzeba znaleźć przybliżone odpowiedzi (a więc APX) z wystarczająco wysoką pewnością (a więc BPP), co uczyniłoby klasę problemów z ograniczonymi probabilistycznymi algorytmami aproksymacji potencjalnie użytecznym modelem tego, co można obliczyć w ćwiczyć.

Możliwym kandydatem takiej klasy byłby : problemy dopuszczające przybliżone rozwiązania z ograniczonymi podprogramami probabilistycznymi; nie jestem jednak pewien, czy taka klasa byłaby odpowiednim ustawieniem dla przybliżonych prawdopodobieństw klasy.APXBPP

Zarówno BPP, jak i APX zostały szeroko zbadane. Czy tak jest w przypadku , czy innej klasy, która najlepiej uchwyciłaby powyższe problemy?APXBPP

cc.complexity-theory approximation-hardness Michael
źródło
BPP i P są klasami problemów decyzyjnych. Być może powinieneś najpierw zapytać, jaka jest klasa funkcji / wyszukiwania odpowiadająca BPP przed przejściem do aproksymacji, myślę, że jeśli mamy klasę funkcji / wyszukiwania, to określenie jej wersji aproksymacji nie powinno być trudne.
Kaveh
1
Myślę, że to, czego szukasz, to optymalizacyjna wersja uczenia się PAC (prawdopodobnie w przybliżeniu poprawna). Podczas gdy teoria uczenia się PAC dotyczy w szczególności (losowo, z dużym prawdopodobieństwem poprawności) funkcji uczenia się służących do opisywania danych, tak jak w uczeniu maszynowym pytasz o problemy z optymalizacją. Może jednak literatura do nauki PAC jest dobrym miejscem do rozpoczęcia poszukiwań ...
Joshua Grochow
3
Zamiast notacji wyroczni to, co opisujesz, jest bliższe operatorowi BP. Operator BP jest zdefiniowany na podstawie klas złożoności problemów decyzyjnych. Powinno być łatwe rozszerzenie definicji w celu obiecywania problemów i zdefiniowanie w ten sposób wersji problemu złożonej z klasy złożoności. Definiowanie wersji dla problemów optymalizacji może być trudniejsze.
Sasho Nikolov

Odpowiedzi:

1

Dla dowolnej funkcji celu, niech BotL (najlepszy z listy) będzie algorytmem, który ocenia funkcję celu na zestawie danych wejściowych i zwraca dane wejściowe z tej listy, które miały maksymalną wydajność (spośród tych danych wejściowych), z powiązaniami zepsuty arbitralnie. Ponieważ APX obejmuje tylko problemy , których funkcję celu można obliczyć w deterministycznym czasie wielomianowym, BotL można zaimplementować deterministycznie w czasie wielomianowym. Ponadto wartość zwracana przez BotL jest co najmniej tak dobra, jak każda z danych wejściowych w co najmniej tej, na której oceniano BotL. W szczególności, jeśli którekolwiek z danych wejściowych z tej listy jest wystarczająco dobre, wynik BotL będzie wystarczająco dobry.



Dlatego uruchomienie BotL na wyjściach wystarczająco dużej liczby niezależnych wykonań algorytmu podstawowego może zwiększyć prawdopodobieństwo powodzenia z 1 / poli do 1- (1 / (2 ^ poli)).

W wyniku poprzedniego akapitu dokładny
poziom ufności zasadniczo nie wpływa na klasę wynikową.
(Ta sytuacja jest wysoce analogiczna do RP .)

Nie udało mi się znaleźć nic na ten temat w złożonym zoo, chociaż
mogły być o tym rozmowy podczas warsztatów, o których mowa w tym artykule .


źródło
1
OP pyta o nazwę klasy problemów, które mają losowe algorytmy aproksymacji współczynnika stałego. Mówisz (myślę), że prawdopodobieństwo sukcesu takich algorytmów można zwiększyć. Nie widzę, jak to odpowiada na pytanie?
Sasho Nikolov
Nie widzę tego pytania w PO. Michael pyta, czy klasa została „gruntownie przestudiowana”. Wprawdzie nie miałem wiele do powiedzenia na ten temat, ale (przynajmniej próbowałem) rozwiązać nieporozumienie na temat tego, jaka byłaby taka klasa.
W pytaniu nie ma takiego nieporozumienia.
Sasho Nikolov
Dobrze. Nieporozumienie polega na tym, że „potencjalnym kandydatem takiej klasy byłyby ... przybliżenia obliczalne probabilistycznie”. akapit, który jest w poście, ale nie ma pytania.
1
Po wyjaśnieniach nadal uważam, że twoja odpowiedź nie koryguje nieporozumień w PO, a jedynie podaje arbitralny fakt dotyczący losowych przybliżeń.
Sasho Nikolov