Esquema de aproximação de tempo polinomial

Em ciência da computação, um esquema de aproximação em 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 $\varepsilon >0$ e, em tempo polinomial, produz uma solução que está dentro de um fator $1+\varepsilon$ de ser ideal (ou $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 $(1+\varepsilon )L$, com $L$ sendo o comprimento do menor percurso .

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 $O(n^{1/\varepsilon })$, ou mesmo $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 $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 $O(n^{c})$ para uma constante $c$ independente de$\varepsilon$. Isso garante que um aumento no tamanho de problema tem o mesmo efeito relativo em tempo de execução, independentemente do $\varepsilon$ que está sendo usado; no entanto, a constante sob o big-O pode ainda depender de $\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 $n$ e $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. 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.

A menos que P = NP, considera-se que FPTAS ⊊ APMS ⊊ APX. 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 $n^{polylog(n)}$ para cada $\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 $\varepsilon >0$ e, em tempo polinomial, produz uma solução que tem uma alta probabilidade de estar dentro de um fator $\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 $\varepsilon$; com mais restrições sobre o tempo de execução em $\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.

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.

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.

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.