Tekst źródłowy strony Wielomianowy schemat aproksymacji

'''Wielomianowy schemat aproksymacji''' ([[Język angielski|ang.]] ''Polynomial-Time Approximation Scheme'', w skrócie PTAS) – [[algorytm aproksymacyjny]], który pozwala na uzyskanie dowolnie dobrego rozwiązania przybliżonego danego [[Problem optymalizacyjny|problemu optymalizacyjnego]] i którego [[Złożoność obliczeniowa|złożoność czasowa]] jest wielomianowa dla każdej żądanej dokładności.

== Definicja formalna ==
[[Algorytm]] A jest '''wielomianowym schematem aproksymacji''' dla problemu <math>\pi</math> jeśli spełnione są następujące warunki:
* dla każdego odpowiedniego <math>\varepsilon</math> A jest [[Algorytm aproksymacyjny|algorytmem ε-aproksymacyjnym]] dla <math>\pi,</math>
* dla każdego odpowiedniego <math>\varepsilon</math> [[Złożoność obliczeniowa|złożoność czasowa]] A jest wielomianowa ze względu na rozmiar instancji problemu podanej na wejściu A.

== Złożoność ==
[[Złożoność obliczeniowa|Złożoność czasowa]] wielomianowego schematu aproksymacji choć wielomianowa względem rozmiaru wejścia dla każdego ustalonego <math>\varepsilon,</math> może rosnąć wykładniczo ze zmianą <math>\varepsilon.</math> Przykładem takiej złożoności jest <math>O(n^\frac{1}{\varepsilon}).</math> Dla każdego <math>\varepsilon</math> jest ona wielomianowa, lecz w miarę jak <math>\varepsilon</math> maleje złożoność ta rośnie wykładniczo.

== Zobacz też ==
* [[W pełni wielomianowy schemat aproksymacji]]
* [[L-redukcja]]

[[Kategoria:Algorytmy aproksymacyjne]]