Prawie zawsze prawie w porządku

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. $APX^{BPP}$

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? $APX^{BPP}$

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

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

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

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 .

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.

$\:$

$\;\;\;$

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