Redução PTAS

Na teoria de complexidade computacional, uma redução PTAS é uma redução com preservação de aproximação que é geralmente usada para fazer reduções junto à soluções para problemas de otimização. Isso preserva a propriedade que um problema possui um esquema de aproximação em tempo polinomial (PTAS) e é usado para definir completude para certas classes de otimização de problemas como APX. Por definição, se existe uma redução PTAS de um problema A para um problema B, nós escrevemos ${\text{A}}\leq _{\text{PTAS}}{\text{B}}$ .

Com redução em tempo polinomial, se pudermos descrever a redução de um problema A para um problema B, então qualquer solução em tempo polinomial para B pode ser composta com a redução para obter uma solução em tempo polinomial para o problema A. Similarmente, nosso objetivo em definir as reduções PTAS é que para uma dada redução PTAS de um problema de otimização A para um problema B, um PTAS para B pode ser composto com uma redução para obter um PTAS para um problema A.

Formalmente, definimos a redução PTAS de A para B usando três funções computáveis em tempo polinomial, f, g, e α, com a seguintes propriedades:

f mapeia instâncias do problema A para instâncias do problema B.
g pega uma instância x de um problema A, uma solução aproximada para o seguinte problema $f(x)$ em B, e um parâmetro de erro ε e produz uma solução aproximada para x.
α mapeia parâmetros de erro de soluções para instâncias do problema em A para parâmetros de erro de soluções para o problema em B.
Se a solução y para $f(x)$ (uma instância do problema B) for pelo menos $1+\alpha (\epsilon )$ vezes pior que a solução ótima, então a solução que leva $g(x,y,\epsilon )$ para x (uma instância do problema A) é pelo menos $1+\epsilon$ vezes pior que a solução ótima.

Propriedades[editar | editar código-fonte]

A partir da definição é fácil demonstrar que:

${\text{A}}\leq _{\text{PTAS}}{\text{B}}$ e ${\text{B}}\in {\text{PTAS}}\implies {\text{A}}\in {\text{PTAS}}$
${\text{A}}\leq _{\text{PTAS}}{\text{B}}$ e ${\text{A}}\not \in {\text{PTAS}}\implies {\text{B}}\not \in {\text{PTAS}}$

Reduções L significam reduções PTAS. Como consequência, alternativamente pode-se demonstrar a existência de uma redução PTAS por meio de uma redução L.^[1]

reduções PTAS são usadas para definir completude em APX, a classe de otimização de problemas com algoritmos de aproximação a fator constante.

Veja também[editar | editar código-fonte]

Referências[editar | editar código-fonte]

↑ Crescenzi, Pierluigi (1997). «A Short Guide To Approximation Preserving Reductions». Washington, D.C.: IEEE Computer Society. Proceedings of the 12th Annual IEEE Conference on Computational Complexity: 262-

Ingo Wegener. Complexity Theory: Exploring the Limits of Efficient Algorithms. ISBN 3-540-21045-8. Chapter 8, pp. 110–111. Google Books preview

Predefinição:Comp-sci-theory-stub

[crescenzi-1] Crescenzi, Pierluigi (1997). «A Short Guide To Approximation Preserving Reductions». Washington, D.C.: IEEE Computer Society. Proceedings of the 12th Annual IEEE Conference on Computational Complexity: 262-

[1]