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 e, em tempo polinomial, produz uma solução que está dentro de um fator de ser ideal (ou 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 , com 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 , ou mesmo conta como um PTAS.
Variantes
[editar | editar código-fonte]Deterministica
[editar | editar código-fonte]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 . 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 para uma constante 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 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 e . 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 para cada fixado.
Randomizado
[editar | editar código-fonte]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 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.[2]
Como uma complexidade de classe
[editar | editar código-fonte]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
- ↑ Sanjeev Arora, em tempo Polinomial Aproximação Esquemas para Euclidiana TSP e outros Problemas Geométricos, Revista da ACM 45(5) 753-782, 1998.
- ↑ a b Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. pp. 294–295. ISBN 3-540-65367-8
- ↑ H. Kellerer and U. Pferschy and D. Pisinger (2004). Knapsack Problems. [S.l.]: Springer
- ↑ a b 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
[editar | editar código-fonte]- 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.