Visualizza wikitesto di Schema di approssimazione in tempo polinomiale

In [[informatica]], uno '''schema di approssimazione in tempo polinomiale''' (in [[Lingua inglese|inglese]] ''polynomial-time approximation scheme'' o '''PTAS''') è un tipo di [[algoritmo di approssimazione]] per [[Problema di ottimizzazione|problemi di ottimizzazione]] (molto spesso, problemi di ottimizzazione [[NP-difficile|NP-difficili]]).

Un PTAS è un algoritmo che prende un'istanza di un problema di ottimizzazione e un parametro ε&nbsp;>&nbsp;0 e, in tempo polinomiale, produce una soluzione che è ottimale entro un fattore 1 + ε (o 1 - ε per i problemi di massimizzazione). Ad esempio, per il [[Problema del commesso viaggiatore|problema euclideo del commesso viaggiatore]], un PTAS produrrebbe un giro di lunghezza al massimo (1&nbsp;+&nbsp;ε)''L'', con ''L'' che è la lunghezza del giro più breve.<ref>[[Sanjeev Arora]], "Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems", ''Journal of the ACM'', 45(5), pp. 753–782, 1998.</ref>

È richiesto che il tempo di esecuzione di un PTAS sia un tempo polinomiale in ''n'' per ogni ε fisso, ma può essere diverso per diversi ε. Così un algoritmo eseguito nel ''[[O-grande|O]]''(''n''<sup>1/ε</sup>) o anche in ''O''(''n''<sup>exp(1/ε)</sup>) conta come un PTAS.

== Varianti ==
=== Deterministico ===
Un problema pratico con gli algoritmi PTAS è che l'esponente del polinomiale potrebbe aumentare drammaticamente quando ε si contrae, ad esempio se il tempo di esecuzione è O(''n''<sup>(1/ε)!</sup>). Un modo di affrontare questo problema è definire lo '''schema di approssimazione efficiente in tempo polinomiale''' (in inglese ''''efficient polynomial-time approximation scheme'' o '''EPTAS'''), nel quale si richiede che il tempo di esecuzione sia ''O''(''n''<sup>''c''</sup>) per una ''c'' costante indipendente da ε. Questo assicura che un aumento della dimensione del problema abbia lo stesso effetto relativo sul tempo di esecuzione indipendentemente da quale ε venga usato; tuttavia, la costante sotto [[O-grande]] può ancora dipendere arbitrariamente da ε. Ancora più restrittivo, e più utile in pratica, è lo '''schema di approssimazione in tempo pienamente polinomiale''' (''fully polynomial-time approximation scheme'' o '''FPTAS'''), che richiede che l'algoritmo sia polinomiale tanto nella dimensione ''n'' del problema quanto in 1/ε. Tutti i problemi in FPTAS sono [[Complessità parametrizzata|trattabili a parametri fissi]]. Un esempio di un problema che ha un FPTAS è il [[problema dello zaino]].

Qualsiasi problema di ottimizzazione [[Fortemente NP-completo|fortemente NP-difficile]] con una [[funzione obiettivo]] limitata polinomialmente non può avere un FPTAS a meno che P=NP.<ref name="vvv"/> Tuttavia, l'inverso viene meno: ad es. se P non è uguale a NP, lo [[Problema dello zaino#Introduzione|zaino con due limiti]] non è fortemente NP-difficile, ma non ha un FPTAS anche quando l'obiettivo ottimale è limitato polinomialmente.<ref>{{cita libro | autore = H. Kellerer, U. Pferschy e D. Pisinger| titolo = Knapsack Problems | editore = Springer | anno = 2004}}</ref>

A meno che [[Classi di complessità P e NP|P = NP]], vale che FPTAS&nbsp;⊊&nbsp;PTAS&nbsp;⊊&nbsp;[[APX (complessità)|APX]].<ref>{{cita testo|nome = Thomas|cognome=Jansen|contributo=Introduction to the Theory of Complexity and Approximation Algorithms|pagine=5–28|titolo=Lectures on Proof Verification and Approximation Algorithms|curatore1-nome=Ernst W.|curatore1-cognome=Mayr|curatore2-nome=Hans Jürgen|curatore2-cognome=Prömel|curatore3-nome=Angelika|curatore3-cognome=Steger|editore=Springer|anno=1998|isbn=9783540642015|doi=10.1007/BFb0053011}}. Vedi la discuezione che segue la Definizione 1.30 a [http://books.google.com/books?id=_C8Ly1ya4cgC&pg=PA20 p.&nbsp;20].</ref> Conseguentemente, in base a questa assunzione, i problemi APX-difficili non hanno PTAS.

Un'altra variante deterministica del PTAS è lo '''schema di approssimazione in tempo quasi-polinomiale''' (''quasi-polynomial-time approximation scheme'' o '''QPTAS'''). Un QPTAS ha complessità temporale <math>n^{polylog(n)}</math> per ciascun <math>\epsilon >0</math> fisso.

=== Randomizzato ===
Alcuni problemi che non hanno un PTAS possono ammettere un [[algoritmo randomizzato]] con proprietà simili, uno '''schema di approssimazione randomizzato in tempo polinomiale''' (''polynomial-time randomized approximation scheme'' o '''PRAS'''). Un PRAS è un algoritmo che prende un'istanza di un problema di ottimizzazione o di conteggio e un parametro ε&nbsp;>&nbsp;0 e, in tempo polinomiale, produce una soluzione che ha un<nowiki>'</nowiki>''alta probabilità'' di essere entro un fattore ε dall'ottimale. Convenzionalmente, "alta probabilità" significa probabilità maggiore di 3/4, benché come con la maggior parte delle classi di complessità probabilistiche la definizione sia robusta rispetto a variazioni di questo valore esatto. Come un PTAS, un PRAS deve avere un tempo di esecuzione polinomiale in ''n'', ma non necessariamente in ε; con ulteriori restrizioni sul tempo di esecuzione in ε, si può definire uno '''schema di approssimazione randomizzato efficiente in tempo polinomiale''' (''efficient polynomial-time randomized approximation scheme'' o '''EPRAS''') simile all'EPTAS, e uno '''schema di approssimazione randomizzato in tempo pienamente polinomiale''' (''fully polynomial-time randomized approximation scheme'' o '''FPRAS''') simile al FPTAS.<ref name="vvv">{{cita libro
  | cognome = Vazirani
  | nome = Vijay V.
  | titolo = Approximation Algorithms
  | editore = Springer
  | anno = 2003
  | pagine = 294–295
  | città = Berlino
  | isbn = 3-540-65367-8
}}</ref>

== Note ==
<references/>

== Collegamenti esterni ==
* ''[[Complexity Zoo]]'': [https://complexityzoo.uwaterloo.ca/Complexity_Zoo:P#ptas PTAS] {{Webarchive|url=https://web.archive.org/web/20180119121055/https://complexityzoo.uwaterloo.ca/Complexity_Zoo:P#ptas |date=19 gennaio 2018 }}, [https://complexityzoo.uwaterloo.ca/Complexity_Zoo:E#eptas EPTAS] {{Webarchive|url=https://web.archive.org/web/20160827163715/https://complexityzoo.uwaterloo.ca/Complexity_Zoo:E#eptas |date=27 agosto 2016 }}, [https://complexityzoo.uwaterloo.ca/Complexity_Zoo:F#fptas FPTAS] {{Webarchive|url=https://web.archive.org/web/20160827183856/https://complexityzoo.uwaterloo.ca/Complexity_Zoo:F#fptas |date=27 agosto 2016 }}
* Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, [[Marek Karpinski]], and Gerhard Woeginger, [http://www.nada.kth.se/~viggo/wwwcompendium/ ''A compendium of NP optimization problems''] – elenca i problemi di ottimizzazione NP dotati di PTAS.

{{Portale|Informatica|Matematica}}

[[Categoria:Algoritmi]]
[[Categoria:Teoria della complessità computazionale]]