Wielomianowy schemat aproksymacji

Algorytm A jest wielomianowym schematem aproksymacji dla problemu ${\displaystyle \pi }$ jeśli spełnione są następujące warunki:

• dla każdego odpowiedniego ${\displaystyle \varepsilon }$ A jest algorytmem ε-aproksymacyjnym dla ${\displaystyle \pi ,}$
• dla każdego odpowiedniego ${\displaystyle \varepsilon }$ złożoność czasowa A jest wielomianowa ze względu na rozmiar instancji problemu podanej na wejściu A.

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

• W pełni wielomianowy schemat aproksymacji
• L-redukcja