APX-completude: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Linha 1:
Em [[Teoria de complexidade computacional| teoria da complexidade]] a classe ''''APX'''' (uma abreviação de "aproximável" em inglês) é o conjunto de [[Problemas de otimização NP]] que permitem [[algoritmos de aproximação]] em [[tempo polinomial]] com relação de aproximação delimitadas por uma constante (ou ''algoritmos de aproximação de fator constante'' por simplicidade). Em termos simples, problemas nessa classe tem [[algoritmo]]s que podem encontrar uma resposta dentro de alguma porcentagem fixa da resposta ótima. Por exemplo, existe um algoritmo em tempo polinomial que encontra a solução para o problema [[bin packing]] que usa no máximo 5% mais do que o menor número possível de caixas.
Um algoritmo de aproximação é chamado um ''c''-algoritmo de aproximação para alguma constante ''c'' se puder ser provado que a solução que o algoritmo encontra é no máximo ''c'' vezes pior que a solução ótima. Aqui, ''c'' é chamado de ''relação de aproximação''. Dependendo do problema ser uma minimalização ou maximização, isso pode denotar ''c'' vezes maior ou ''c'' vezes menor, respectivamente. Por exemplo, o problema da [[Cobertura de vértices (teoria dos grafos)|cobertura de vértices]] e o [[Problema do caixeiro-viajante]] (com desigualdade de triângulos) tem simples 2-algoritmos de aproximação cada. Em contraste, é provado que o [[problema do caixeiro-viajante]] com tamanhos de arestas arbitrários não podem ser aproximadas com relação de aproximação delimitadas por constante enquanto o problema de caminho hamiltoniano não puder ser resolvido em tempo polinomial, ou seja ao menos que [[P versus NP|P = NP]].
Se existe um algoritmo de tempo polinomial para resolver um problema no qual ''toda'' porcentagem fixa maior que zero (um algoritmo para cada porcentagem), então é dito que o problema tem um [[esquema de aproximação polinomial]] (polynomial-time approximation scheme ou ''PTAS'' em inglês). A menos que [[P=NP]], pode ser mostrado que existem problemas que estão em ''APX'' mas não em ''PTAS''; ou seja, problemas que podem ser aproximados dentro de ''alguma'' relação constante, mas não ''toda'' relação constante. Um problema é dito '''APX'''-difícil se existe alguma [[redução PTAS]] de cada problema em '''APX''' para tal problema, e é dito '''APX'''-completo se o problema é '''APX'''-difícil e também '''APX'''. Como consequência de P ≠ NP ⇒ '''PTAS''' ≠ '''APX''', P ≠ NP ⇒ nenhum problema '''APX'''-difícil está em '''PTAS'''.
Dizer que um problema é '''APX'''-difícil é geralmente uma notícia ruim, porque se P ≠ NP, isso nega a existência de uma '''PTAS''', que é o tipo de algoritmo de eproximação mais útil. Um dos mais simples problemas '''APX'''-completos é o [[problema de satisfabilidade máxima]], uma variação do [[problema de satisfabilidade booleano]]. Neste problema, temos uma fórmula em [[forma normal conjuntiva]] e queremos saber o número máximo de cláusulas que pode ser satisfeita simultâneamente por uma única atribuição de valores verdadeiro/falso para as variáveis. Apesar de que provavelmente ela não tem uma PTAS, ainda assim a resposta correta pode ser estimada dentro de 30% e algumas variantes simplificadas têm PTAS.
==
* O [[Algoritmo de Christofides]]
| |||