PLS (complexidade)

Na teoria da complexidade computacional, a Pesquisa Local Polinomial (PLS) é uma classe de complexidade que modela a dificuldade de encontrar uma solução ótima localmente para um problema de otimização.

Um problema PLS $L$ tem um conjunto $D_{L}$ de instâncias que são codificados usando seqüências de caracteres sobre um alfabeto finito $\Sigma$. Para cada instância $x$ existe uma solução finita de $F_{L}(x)$. Cada solução $s\in F_{L}(x)$ tem um número inteiro não-negativo de custo dado por uma função $c_{L}(s,x)$ e uma vizinhança $N(s,x)\subseteq F_{L}(x)$. Além disso, a existência dos três seguintes algoritmos de tempo polinomial é necessária:

• Algoritmo $A_{L}$ produz alguma solução $A_{L}(x)\in F_{L}(x)$.
• Algoritmo $B_{L}$ determina o valor de $c_{L}(s,x)$.
• Algoritmo $C_{L}$ mapeia um solução $s\in F_{L}(x)$ para um elemento $s'\in N(s,x)$ de tal forma que $c_{L}(s',x)<c_{L}(s,x)$ se tal elemento não existe. Caso contrário, $C_{L}$ relata que tal elemento não existe.

Uma instância $D_{L}$ tem a estrutura de um grafo implícito, os vértices sendo as soluções com duas soluções $s,s'\in F_{L}(x)$ conectados por um arco direcionado se e somente se $s'\in N(s,x)$. O mais interessante problema computacional é o seguinte:

Dado alguma instância $x$ de um problema PLS $L$, encontrar um local optimum de $c_{L}(s,x)$, i.e. uma solução $s\in F_{L}(x)$ tal que $c_{L}(s',x)\geq c_{L}(s,x)$ para todos $s'\in N(s,x)$

O problema pode ser resolvido usando o seguinte algoritmo:

1. Use $A_{L}$ para encontrar uma solução inicial $s$
2. Use o algoritmo $C_{L}$ para encontrar uma solução melhor $s'\in N(s,x)$. Se tal solução existe, substituir $s$ por $s'$, caso contrário retorne $s$

Infelizmente, isso geralmente leva um número exponencial de passos de melhoria para encontrar um local optimum, mesmo se o problema $L$ pode ser resolvido exatamente em tempo polinomial.

Exemplos de problemas PLS-completo incluem relativos ao local optimum do problema do caixeiro viajante, corte máximo e satisfatibilidade, bem como a procura de um puro equilíbrio de Nash de um jogo congestionamento.

PLS é uma subclasse da TFNP, uma classe de complexidade estreitamente relacionada com a NP que descreve problemas computacionais em que é garantida a existência de uma solução e que pode ser reconhecida em tempo polinomial. Por um problema no PLS, é garantida a existência de uma solução porque o vértice de custo mínimo do gráfico inteiro é uma solução válida, e a validade de uma solução pode ser verificada através do cálculo de seus vizinhos e comparando os custos de cada um.

Referências

• Yannakakis, Mihalis (2009), «Equilibria, fixed points, and complexity classes», Elsevier, Computer Science Review, 3 (2): 71–85, doi:10.1016/j.cosrev.2009.03.004 .