Esquema de aproximação de tempo polinomial

Em ciência da computação, um esquema de aproximação de tempo polinomial (PTAS) é um tipo de algoritmo de aproximação para problemas de otimização (na maioria das vezes, problemas de otimização NP-difíceis).

Um PTAS é um algoritmo que toma como entrada uma instância de um problema de otimização e um parâmetro ${\displaystyle \varepsilon >0}$ e, em tempo polinomial, produz uma solução que está dentro de um fator ${\displaystyle 1+\varepsilon }$ de ser ideal (ou ${\displaystyle 1-\varepsilon }$ para problemas de maximização). Por exemplo, para  problema do caixeiro viajante Euclidiano, um PTAS iria produzir um percurso com duração no máximo ${\displaystyle (1+\varepsilon )L}$, com ${\displaystyle L}$ sendo o comprimento do menor percurso .^[1]

O tempo de execução de um PTAS é necessariamente polinomial em n para cada ε fixado, mas pode ser diferente para diferentes ε. Assim, um algoritmo sendo executado em tempo ${\displaystyle O(n^{1/\varepsilon })}$, ou mesmo ${\displaystyle O(n^{\exp {1/\varepsilon }})}$ conta como um PTAS.

Variantes

Deterministica

Um problema prático com os algoritmos de PTAS é que o expoente do polinômio poderia aumentar dramaticamente à medida que ε diminui, por exemplo, se o tempo de execução for ${\displaystyle O(n^{1/\varepsilon })}$. Uma forma de lidar com isso é definir o esquema de  aproximação eficiente em tempo polinomial ou EPTAS, em que o tempo de execução é necessário que seja ${\displaystyle O(n^{c})}$ para uma constante ${\displaystyle c}$ independente de${\displaystyle \varepsilon }$. Isso garante que um aumento no tamanho de problema tem o mesmo efeito relativo em tempo de execução, independentemente do ${\displaystyle \varepsilon }$ que está sendo usado; no entanto, a constante sob o big-O pode ainda depender de ${\displaystyle \varepsilon }$ arbitrariamente. Ainda mais restritivo, e útil na prática, é o esquema de aproximação totalmente em tempo polinomial ou FPTAS, que requer que o algoritmo seja polinomial em ambos os problema de tamanho ${\displaystyle n}$ e ${\displaystyle 1/\varepsilon }$. Todos os problemas em FPTAS são tratáveis com parâmetros de tamanho fixo. Um exemplo de um problema que tem uma FPTAS é o Problema da mochila.

Qualquer problema de otimização fortemente NP-difícil com uma função objetiva delimitada polinomialmente pode ter um FPTAS, a menos que P=NP.^[2] No entanto, o inverso falha: por exemplo, se P não é igual a NP, o problema da mochila com duas restrições não é fortemente NP-difícil, mas não tem FPTAS mesmo quando o objetivo ótimo é polinomialmente limitado.^[3]

A menos que P = NP, considera-se que FPTAS ⊊ APMS ⊊ APX.^[4] por conseguinte, com este pressuposto, problemas APX-difícil não têm PTASs.

Outra variante determinística PTAS é o esquema de aproximação quase em tempo polinomial ou QPTAS. Um QPTAS tem complexidade de tempo ${\displaystyle n^{polylog(n)}}$ para cada ${\displaystyle \epsilon >0}$ fixado.

Randomizado

Alguns problemas que não têm uma PTAS podem admitir que um algoritmo randomizado com propriedades semelhantes, esquema de aproximalção em tempo polinomial randomizados ou PRAS. Um PRAS é um algoritmo que leva uma instância de uma otimização ou problema de contagem e um parâmetro ${\displaystyle \varepsilon >0}$ e, em tempo polinomial, produz uma solução que tem uma alta probabilidade de estar dentro de um fator ${\displaystyle \varepsilon }$ do ideal. Convencionalmente, a "alta probabilidade" significa probabilidade maior que 3/4, embora, como com a maioria das classes de complexidade probabilísticas a definição é robusta a variações neste valor exato (o mínimo requisito é geralmente maior do que 1/2). Como um PTAS, um PRAS deve ter o tempo de execução polinomial em n, mas não necessariamente em ${\displaystyle \varepsilon }$; com mais restrições sobre o tempo de execução em ${\displaystyle \varepsilon }$, pode-se definir um esquema de aproximação eficiente em tempo polinomial randomizados  ou EPRAS semelhante à EPTAS, e um esquema de aproximação totalmente em tempo polinomial randomizados ou FPRAS semelhante à FPTAS.^[2]

Como uma complexidade de classe

O termo PTAS também pode ser usado para se referir à classe de problemas de otimização que tem um PTAS. PTAS é um subconjunto de APX, e a menos que P = NP, é um subconjunto estrito.^[4]

A presença em PTAS pode ser demonstrada utilizando uma Redução PTAS, Redução linear, ou P-redução, as quais preservam a presença em PTAS, e estes também podem ser utilizados para demonstrar a PTAS-completude. Por outro lado, mostrar a não presença em PTAS (ou seja, a não-existência de um PTAS), pode ser feita mostrando que o problema é APX-difícil, após o qual a existência de um PTAS iria mostrar P = NP. APX-dificuldade é geralmente mostrado através de uma redução PTAS redução ou AP-redução.

Referências

1. Sanjeev Arora, em tempo Polinomial Aproximação Esquemas para Euclidiana TSP e outros Problemas Geométricos, Revista da ACM 45(5) 753-782, 1998.
2. Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. pp. 294–295. ISBN 3-540-65367-8 
3. H. Kellerer and U. Pferschy and D. Pisinger (2004). Knapsack Problems. [S.l.]: Springer  !CS1 manut: Usa parâmetro autores (link)
4. Jansen, Thomas (1998), «Introduction to the Theory of Complexity and Approximation Algorithms», in: Mayr, Ernst W.; Prömel, Hans Jürgen; Steger, Angelika, Lectures on Proof Verification and Approximation Algorithms, ISBN 9783540642015, Springer, pp. 5–28, doi:10.1007/BFb0053011 .

Ligações externas

• A complexidade do Zoo: APMS, EPTAS, FPTAS
• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, e Gerhard Woeginger, Um compêndio de problemas de otimização NP – lista de problemas de otimização NP tem PTAS.