APX-completude

Em 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 algoritmos 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 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 = 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 aproximaçã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.

Bibliografia

• C. Papadimitriou and M. Yannakakis. Optimization, approximation and complexity classes. Journal of Computer and System Sciences, 43:425–440, 1991.
• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski and Gerhard Woeginger.

Ligação externa

• Maximum Satisfiability (em inglês)
• A compendium of NP optimization problems (em inglês)