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 ${\displaystyle {\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 ${\displaystyle 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 ${\displaystyle f(x)}$ (uma instância do problema B) for pelo menos ${\displaystyle 1+\alpha (\epsilon )}$ vezes pior que a solução ótima, então a solução que leva ${\displaystyle g(x,y,\epsilon )}$ para x (uma instância do problema A) é pelo menos ${\displaystyle 1+\epsilon }$ vezes pior que a solução ótima.

Propriedades

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

• ${\displaystyle {\text{A}}\leq _{\text{PTAS}}{\text{B}}}$ e ${\displaystyle {\text{B}}\in {\text{PTAS}}\implies {\text{A}}\in {\text{PTAS}}}$
• ${\displaystyle {\text{A}}\leq _{\text{PTAS}}{\text{B}}}$ e ${\displaystyle {\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

• Redução com preservação de aproximação
• Redução L
• APX

Referências

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- 

• 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