多項式時間近似スキーム

計算機科学において、多項式時間近似スキーム（、PTAS）は(大抵NP困難であるような)最適化問題に対する近似アルゴリズムの一種である。
PTASは最適化問題のインスタンスとパラメータ formula_1 を入力として受け取り、多項式時間内に最適解の formula_2 倍以下の解を求めることのできるアルゴリズムである（最大化問題の場合は formula_3 倍以上）。例えば、ユークリッド距離に基づく巡回セールスマン問題では、最適解の長さを formula_4 としたとき、高々 formula_5 の解を見つけることができる。
PTASの実行時間は、formula_6 を固定すると、問題の大きさ formula_7 の多項式であることが求められるが、formula_6 に対しては定められていない。このため、実行時間が formula_9 や formula_10 オーダーであっても、PTASである。
変形.
決定的.
PTASアルゴリズムがある現実的な問題は、εを小さくすると多項式の指数部が劇的に大きくなってしまう（例えば formula_11 のように）。この問題に対処するひとつの方法が効率的な多項式時間近似スキーム（EPTAS）と呼ばれる、実行時間が formula_12 を formula_6 と独立な定数として、formula_14 であるようなアルゴリズムである。この場合、どのようなεを選んでも問題の大きさは実行時間に与える影響は等しくなる。しかし、"O"記法における定数はεに対して任意に大きくなりうる。これに対してより強い制約として、実行時間が問題の大きさ formula_7 と formula_16 両方の多項式時間であるものを完全多項式時間近似スキーム（FPTAS）と呼ぶ。 ナップサック問題はFPTASがある問題の例である.
多項式的に有界な目的関数を持つどんな強度にNP困難な最適化問題も、P=NPでない限り、FPTASを持ち得ない。
しかし、逆は真ではない。例えば、P≠NPのとき、2つの制約をもつナップサック問題はFPTASを持たないが、たとえ目的関数が多項式的に有界の場合でも強度にNP困難ではない。
P=NPでない限り、formula_17 が成り立つ。すなわち、同じ仮定の下で、APX困難な問題はPTASを持たない。
別の決定論的なPTASの変形として、準多項式時間近似スキーム（QPTAS）がある。QPTASはある固定された formula_6 に対してformula_19の時間複雑度を持つ。
乱択.
PTASを持たない問題が、PTASと似通った特徴を持つ多項式時間乱択近似スキーム（PRAS）を持つことがある。PRASは最適化問題のインスタンスとパラメータ formula_1 を入力とし、多項式時間で『高い確率』で最適解の formula_21 倍以下のソリューションを生成することのできるアルゴリズムである。『高い確率』とは慣習的に formula_22 以上のことであるが、ほとんどの確率的計算複雑度のクラスは、この具体的な値に対してロバストである。PTASと同様にPRASは問題のサイズ formula_7 に対して多項式の計算時間を持たねばならないが、formula_6 に対してはそうではない。formula_6 に対するEPTASと同様の制約を持つものを効率的多項式時間乱択近似スキーム（EPRAS）と呼ぶ。また、FPTASと同様の制約を持つものを完全多項式時間乱択近似スキーム（FPRAS）と呼ぶ。