PLS (complexity) (original) (raw)
In computational complexity theory, Polynomial Local Search (PLS) is a complexity class that models the difficulty of finding a locally optimal solution to an optimization problem. The main characteristics of problems that lie in PLS are that the cost of a solution can be calculated in polynomial time and the neighborhood of a solution can be searched in polynomial time. Therefore it is possible to verify whether or not a solution is a local optimum in polynomial time.Furthermore, depending on the problem and the algorithm that is used for solving the problem, it might be faster to find a local optimum instead of a global optimum.
| Property | Value |
|---|---|
| dbo:abstract | In computational complexity theory, Polynomial Local Search (PLS) is a complexity class that models the difficulty of finding a locally optimal solution to an optimization problem. The main characteristics of problems that lie in PLS are that the cost of a solution can be calculated in polynomial time and the neighborhood of a solution can be searched in polynomial time. Therefore it is possible to verify whether or not a solution is a local optimum in polynomial time.Furthermore, depending on the problem and the algorithm that is used for solving the problem, it might be faster to find a local optimum instead of a global optimum. (en) 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: * Algoritmo produz alguma solução . * Algoritmo determina o valor de . * Algoritmo mapeia um solução para um elemento de tal forma que se tal elemento não existe. Caso contrário, relata que tal elemento não existe. 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: 1. * Use para encontrar uma solução inicial 2. * Use o algoritmo para encontrar uma solução melhor . Se tal solução existe, substituir por , caso contrário retorne 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. (pt) |
| dbo:thumbnail | wiki-commons:Special:FilePath/PLS-complete_Problems_Overview.svg?width=300 |
| dbo:wikiPageID | 4669257 (xsd:integer) |
| dbo:wikiPageLength | 33256 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1112508674 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:NP_(complexity) dbr:Nash_equilibrium dbr:Hopfield_network dbr:Independent_set_(graph_theory) dbr:Integer_programming dbr:Pseudo-polynomial_time dbr:Maxima_and_minima dbr:Maximum_cut dbr:Co-NP dbr:Congestion_game dbr:Constraint_satisfaction_problem dbr:Alphabet_(computer_science) dbr:Lipschitz_continuity dbr:Complexity_class dbr:Computational_complexity_theory dbr:P_(complexity) dbr:String_(computer_science) dbr:Time_complexity dbr:Transitive_relation dbr:Travelling_salesman_problem dbr:Linear_programming dbr:Local_optimum dbr:TFNP dbr:3-dimensional_matching dbr:Graph_partition dbr:Reduction_(complexity) dbr:2-satisfiability dbc:Complexity_classes dbr:Hamming_distance dbr:Directed_acyclic_graph dbr:Boolean_circuit dbr:Boolean_satisfiability_problem dbr:Circuit_satisfiability_problem dbr:Implicit_graph dbr:Optimization_problem dbr:Set_cover_problem dbr:Simplex_algorithm dbr:FNP_(complexity) dbr:FP_(complexity) dbr:NK_model dbr:NP-hardness dbr:Job_shop_scheduling dbr:Fitness_landscapes dbr:File:PLS-complete_Problems_Overview.svg |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Reflist |
| dct:subject | dbc:Complexity_classes |
| rdf:type | yago:WikicatComplexityClasses yago:Abstraction100002137 yago:Class107997703 yago:Collection107951464 yago:Group100031264 |
| rdfs:comment | In computational complexity theory, Polynomial Local Search (PLS) is a complexity class that models the difficulty of finding a locally optimal solution to an optimization problem. The main characteristics of problems that lie in PLS are that the cost of a solution can be calculated in polynomial time and the neighborhood of a solution can be searched in polynomial time. Therefore it is possible to verify whether or not a solution is a local optimum in polynomial time.Furthermore, depending on the problem and the algorithm that is used for solving the problem, it might be faster to find a local optimum instead of a global optimum. (en) 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: (pt) |
| rdfs:label | PLS (complexity) (en) PLS (complexidade) (pt) |
| owl:sameAs | freebase:PLS (complexity) yago-res:PLS (complexity) wikidata:PLS (complexity) dbpedia-he:PLS (complexity) dbpedia-pt:PLS (complexity) https://global.dbpedia.org/id/4suYZ |
| prov:wasDerivedFrom | wikipedia-en:PLS_(complexity)?oldid=1112508674&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/PLS-complete_Problems_Overview.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:PLS_(complexity) |
| is dbo:wikiPageDisambiguates of | dbr:PLS |
| is dbo:wikiPageRedirects of | dbr:PLS-completeness |
| is dbo:wikiPageWikiLink of | dbr:Complete_(complexity) dbr:PLS dbr:Succinct_game dbr:Hedonic_game dbr:TFNP dbr:PLS-completeness dbr:Carathéodory's_theorem_(convex_hull) dbr:Implicit_graph dbr:NK_model |
| is foaf:primaryTopic of | wikipedia-en:PLS_(complexity) |
