PLS (complexidade)

Predefinição:Sem notas 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 $\mathrm{\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^{\prime }\in N(s,x)$ de tal forma que $c_L(s^{\prime },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^{\prime }\in F_L(x)$ conectados por um arco direcionado se e somente se $s^{\prime }\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^{\prime },x)\ge c_L(s,x)$ para todos $s^{\prime }\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^{\prime }\in N(s,x)$. Se tal solução existe, substituir $s$ por $s^{\prime }$, 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

• Predefinição:Citation.