Jaki jest związek między i ?

Jaki jest związek między i ? Innymi słowy, czy problemy, które dopuszczają wyszukiwanie lokalne w czasie wielomianowym, są przybliżone? Czy problemy z optymalizacją w przybliżeniu sugerują ogólnie lokalny algorytm wyszukiwania?$\mathsf{PLS}$$\mathsf{APX}$

Jeśli ktoś chce zbliżyć funkcję potencjalną, to tak, istnieje nawet schemat aproksymacji w pełni wielomianowy (FPTAS). Widzieć

James B. Orlin, Abraham P. Punnen, Andreas S. Schulz: Przybliżone wyszukiwanie lokalne w optymalizacji kombinatorycznej. SIAM J. Comput. 33 (5): 1201–1214 (2004).

Jednak w przypadku niektórych ustawień nie jest to interesujące. Na przykład w przypadku gier z przeciążeniem, w których istnieją czyste równowagi, a ich obliczenia są kompletne z PLS, profile strategii dobrze przybliżające potencjalną funkcję mogą być bardzo słabymi przybliżonymi równowagami. W przypadku niektórych ustawień, przybliżone równowagi o stałym współczynniku można obliczyć w czasie wielomianowym, nawet jeśli obliczenie dokładnej równowagi jest trudne PLS, dla innych ustawień PLS trudne jest obliczenie przybliżonej równowagi dla dowolnego nietrywialnego obliczalnego przybliżenia w czasie wielomianowym współczynnik, jak wyjaśniono w poniższym dokumencie z ogłoszeniem.

Ioannis Caragiannis, Angelo Fanelli, Nick Gravin, Alexander Skopalik: Obliczanie przybliżonej równowagi Nasha w grach z zatorami. SIGecom Exchange 11 (1): 26-29 (2012).

Uwaga PLS może być znacznie łatwiejszy niż FNP.