На этой странице Вы можете получить подробный анализ слова или словосочетания, произведенный с помощью лучшей на сегодняшний день технологии искусственного интеллекта:
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 tem um conjunto de instâncias que são codificados usando seqüências de caracteres sobre um alfabeto finito . Para cada instância existe uma solução finita de . Cada solução tem um número inteiro não-negativo de custo dado por uma função e uma vizinhança . Além disso, a existência dos três seguintes algoritmos de tempo polinomial é necessária:
Uma instância tem a estrutura de um grafo implícito, os vértices sendo as soluções com duas soluções conectados por um arco direcionado se e somente se . O mais interessante problema computacional é o seguinte:
Dado alguma instância de um problema PLS , encontrar um local optimum de , i.e. uma solução tal que para todos
O problema pode ser resolvido usando o seguinte algoritmo:
Infelizmente, isso geralmente leva um número exponencial de passos de melhoria para encontrar um local optimum, mesmo se o problema 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.