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 leva uma instância de um problema de otimização e um parâmetro ε > 0 e, em tempo polinomial, produz uma solução que está dentro de um fator 1 + ε de ser ideal (ou 1 - ε 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 + ε)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/ε), ou mesmo O(n^exp(1/ε)) conta como um PTAS.

Variantes

Deterministica

Um problema prático com as PTAS algoritmos é que o expoente do polinômio poderia aumentar dramaticamente como ε diminui, por exemplo, se o tempo de execução é O(n^(1/ε)!). 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 ε. Isso garante que um aumento no tamanho de problema tem o mesmo efeito relativo em tempo de execução, independentemente do ε que está sendo usado; no entanto, a constante sob o big-O pode ainda depender de ε arbitrariamente. Ainda mais restritivas, e úteis 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/ε. 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 ${\displaystyle }$ para cada ${\displaystyle }$.

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 ε > 0 e, em tempo polinomial, produz uma solução que tem uma alta probabilidade de estar dentro de um fator ε 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 ε; com mais restrições sobre o tempo de execução em ε, 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.

O pertencimento a PTAS pode ser demonstrado utilizando uma Redução PTAS, Redução linear, ou P-redução, os quais preservam o pertencimento a PTAS, e estes também podem ser utilizados para demonstrar a PTAS-completude. Por outro lado, mostrando o não pertencimento a PTAS (ou seja, a não-existência de um PTAS ), pode ser feito 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.