Mostrar código-fonte de 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 [[Problema de otimização|problemas de otimização]] (na maioria das vezes,  problemas de otimização [[NP-difícil|NP-difíceis]]).

Um PTAS é um algoritmo que toma como entrada uma instância de um problema de otimização e um parâmetro <math>\varepsilon>0</math> e, em tempo polinomial, produz uma solução que está dentro de um fator <math>1 + \varepsilon</math> de ser ideal (ou <math>1 - \varepsilon</math> para problemas de maximização). Por exemplo, para  [[Problema do caixeiro-viajante|problema do caixeiro viajante]] Euclidiano, um PTAS iria produzir um percurso com duração no máximo <math>(1+\varepsilon)L</math>, com <math>L</math> sendo o comprimento do menor percurso .<ref>Sanjeev Arora, em tempo Polinomial Aproximação Esquemas para Euclidiana TSP e outros Problemas Geométricos, Revista da ACM 45(5) 753-782, 1998.</ref>

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 <math>O(n^{1/\varepsilon})</math>, ou mesmo <math>O(n^{\exp{1/\varepsilon}})</math> conta como um PTAS.

== Variantes ==

=== Deterministica ===
Um problema prático com os algoritmos de PTAS  é que o expoente do [[Função polinomial|polinômio]] poderia aumentar dramaticamente à medida que ε diminui, por exemplo, se o tempo de execução for <math>O(n^{1/\varepsilon})</math>. 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 <math>O(n^c)</math> para uma constante <math>c</math> independente de<math>\varepsilon</math>. Isso garante que um aumento no tamanho de problema tem o mesmo efeito relativo em tempo de execução, independentemente do <math>\varepsilon</math> que está sendo usado; no entanto, a constante sob o [[Grande-O|big-]]O pode ainda depender de <math>\varepsilon</math> 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 <math>n</math> e <math>1/\varepsilon</math>. Todos os problemas em FPTAS são [[Complexidade parametrizada|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-completo|fortemente NP-difícil]] com uma função objetiva delimitada polinomialmente pode ter um FPTAS, a menos que P=NP.<ref name="vvv">{{Citar livro|último=Vazirani|primeiro=Vijay V.|título=Approximation Algorithms|publicado=Springer|ano=2003|páginas=294–295|local=Berlin|isbn=3-540-65367-8}}</ref> 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.<ref>{{Citar livro|autores=H. Kellerer and U. Pferschy and D. Pisinger|título=Knapsack Problems|publicado=Springer|ano=2004}}</ref>

A menos que [[P versus NP|P = NP]], considera-se que FPTAS&#x20;⊊&#x20;APMS&#x20;⊊&#x20;[[Apx completude|APX]].<ref name="Jansen">{{Citation|primeiro=Thomas|último=Jansen|contribuição=Introduction to the Theory of Complexity and Approximation Algorithms|páginas=5–28|título=Lectures on Proof Verification and Approximation Algorithms|editor-nome1=Ernst W.|editor-sobrenome1=Mayr|editor-nome2=Hans Jürgen|editor-sobrenome2=Prömel|editor-nome3=Angelika|editor-sobrenome3=Steger|editor3-link=Angelika Steger|publicado=Springer|ano=1998|isbn=9783540642015|doi=10.1007/BFb0053011}}. </ref> 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 <math>n^{polylog(n)}</math> para cada <math>\epsilon >0</math> fixado.

=== Randomizado ===
Alguns problemas que não têm uma PTAS podem admitir que um [[Algoritmo probabilístico|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 <math>\varepsilon>0</math> e, em tempo polinomial, produz uma solução que tem uma ''alta probabilidade'' de estar dentro de um fator <math>\varepsilon</math> 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 <math>\varepsilon</math>; com mais restrições sobre o tempo de execução em <math>\varepsilon</math>, 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.<ref name="vvv">{{Citar livro|último=Vazirani|primeiro=Vijay V.|título=Approximation Algorithms|publicado=Springer|ano=2003|páginas=294–295|local=Berlin|isbn=3-540-65367-8}}</ref>

== 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 completude|APX]], e a menos que [[P versus NP|P = NP]], é um subconjunto estrito.<ref name="Jansen">{{Citation|primeiro=Thomas|último=Jansen|contribuição=Introduction to the Theory of Complexity and Approximation Algorithms|páginas=5–28|título=Lectures on Proof Verification and Approximation Algorithms|editor-nome1=Ernst W.|editor-sobrenome1=Mayr|editor-nome2=Hans Jürgen|editor-sobrenome2=Prömel|editor-nome3=Angelika|editor-sobrenome3=Steger|editor3-link=Angelika Steger|publicado=Springer|ano=1998|isbn=9783540642015|doi=10.1007/BFb0053011}}. </ref>

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}}

== Ligações externas ==
* A complexidade do Zoo: [https://complexityzoo.uwaterloo.ca/Complexity_Zoo:P#ptas APMS], [https://complexityzoo.uwaterloo.ca/Complexity_Zoo:E#eptas EPTAS], [https://complexityzoo.uwaterloo.ca/Complexity_Zoo:F#fptas FPTAS]
* Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, e Gerhard Woeginger, [http://www.nada.kth.se/~viggo/wwwcompendium/ ''Um compêndio de problemas de otimização NP''] – lista de problemas de otimização NP tem PTAS.
[[Categoria:Classes de complexidade]]