PLS (complexidade)
# 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:
* Use $A_{L}$ para encontrar uma solução inicial $s$
* 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.