Qual é a relação entre e ? Em outras palavras, os problemas que admitem uma pesquisa local em horário polinomial são aproximados? Problemas aproximados de otimização implicam em geral um algoritmo de busca local?
Se alguém quiser aproximar a função potencial, sim, existe um esquema de aproximação de tempo totalmente polinomial (FPTAS). Vejo
James B. Orlin, Abraham P. Punnen, Andreas S. Schulz: Pesquisa Local Aproximada em Otimização Combinatória. SIAM J. Comput. 33 (5): 1201-1214 (2004).
Para algumas configurações, porém, isso não é interessante. Por exemplo, para jogos de congestionamento, onde existem equilíbrios puros e sua computação é completa em PLS, perfis de estratégia que aproximam bem a função potencial podem ser equilíbrios aproximados muito ruins. Para algumas configurações, os equilíbrios aproximados de fator constante podem ser calculados em tempo polinomial, mesmo quando calcular um equilíbrio exato é difícil para PLS, para outras configurações é difícil para PLS calcular um equilíbrio aproximado para qualquer aproximação não trivial computável em tempo polinomial fator, conforme explicado no documento a seguir.
Ioannis Caragiannis, Angelo Fanelli, Nick Gravin, Alexander Skopalik: A computação aproximada de equilíbrios puros de Nash em jogos de congestionamento. Trocas SIGecom 11 (1): 26-29 (2012).
Nota O PLS pode ser muito mais fácil que o FNP.