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?
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.