多項式時間近似スキームのソースを表示

[[計算機科学]]において、'''多項式時間近似スキーム'''（{{lang-en-short|polynomial-time approximation scheme}}、'''PTAS'''）は(大抵[[NP困難]]であるような)[[最適化問題]]に対する[[近似アルゴリズム]]の一種である。

PTASは最適化問題のインスタンスとパラメータ <math>\varepsilon>0</math> を入力として受け取り、多項式時間内に最適解の <math>1 + \varepsilon</math> 倍以下の解を求めることのできるアルゴリズムである（最大化問題の場合は <math>1 - \varepsilon</math> 倍以上）。例えば、ユークリッド距離に基づく[[巡回セールスマン問題]]では、最適解の長さを <math>L</math> としたとき、高々 <math>(1+\varepsilon) L</math> の解を見つけることができる。<ref>[[:en:Sanjeev Arora|Sanjeev Arora]], Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems, Journal of the ACM 45(5) 753–782, 1998.</ref>

PTASの実行時間は、<math>\varepsilon</math> を固定すると、問題の大きさ <math>n</math> の多項式であることが求められるが、<math>\varepsilon</math> に対しては定められていない。このため、実行時間が <math>O(n^{1/\varepsilon})</math> や <math>O(n^{\exp(1/\varepsilon)})</math> [[ランダウの記号|オーダー]]であっても、PTASである。

==変形==
===決定的===
PTASアルゴリズムがある現実的な問題は、εを小さくすると多項式の指数部が劇的に大きくなってしまう（例えば <math>O(n^{(1/\varepsilon)!})</math> のように）。この問題に対処するひとつの方法が'''効率的な多項式時間近似スキーム'''（'''EPTAS'''<ref>{{lang-en-short|efficient polynomial-time approximation scheme}}</ref>）と呼ばれる、実行時間が <math>c</math> を <math>\varepsilon</math> と独立な定数として、<math>O(n^c)</math> であるようなアルゴリズムである。この場合、どのようなεを選んでも問題の大きさは実行時間に与える影響は等しくなる。しかし、''[[ランダウの記号|O]]''記法における定数はεに対して任意に大きくなりうる。これに対してより強い制約として、実行時間が問題の大きさ <math>n</math> と <math>1/\varepsilon</math> 両方の多項式時間であるものを'''完全多項式時間近似スキーム'''（'''FPTAS'''<ref>{{lang-en-short|fully polynomial-time approximation scheme}}</ref>）と呼ぶ。<!-- All problems in FPTAS are [[fixed-parameter tractable]]. --> [[ナップサック問題]]はFPTASがある問題の例である.

多項式的に有界な目的関数を持つどんな[[強度にNP困難]]な最適化問題も、P=NPでない限り、FPTASを持ち得ない。<ref name="vvv"/>
しかし、[[逆]]は真ではない。例えば、P≠NPのとき、2つの制約をもつナップサック問題はFPTASを持たないが、たとえ目的関数が多項式的に有界の場合でも強度にNP困難ではない。<ref>{{cite book|authors= H. Kellerer and U. Pferschy and D. Pisinger| title = Knapsack Problems | publisher = Springer | year = 2004}}</ref>

[[P≠NP予想|P=NP]]でない限り、<math>FPTAS\subsetneq PTAS\subsetneq APX</math> が成り立つ。すなわち、同じ仮定の下で、APX困難な問題はPTASを持たない。

別の決定論的なPTASの変形として、'''準多項式時間近似スキーム'''（'''QPTAS'''<ref>{{lang-en-short|quasi-polynomial-time approximation scheme}}</ref>）がある。QPTASはある固定された <math>\varepsilon</math> に対して<math>n^{polylog(n)}</math>の時間複雑度を持つ。

===乱択===
PTASを持たない問題が、PTASと似通った特徴を持つ'''多項式時間乱択近似スキーム'''（'''PRAS'''<ref>{{lang-en-short|polynomial-time randomized approximation scheme}}</ref>）を持つことがある。PRASは最適化問題のインスタンスとパラメータ <math>\varepsilon>0</math> を入力とし、多項式時間で『高い確率』で最適解の <math>1+\varepsilon</math> 倍以下のソリューションを生成することのできるアルゴリズムである。『高い確率』とは慣習的に <math>3/4</math> 以上のことであるが、ほとんどの確率的計算複雑度のクラスは、この具体的な値に対してロバストである。PTASと同様にPRASは問題のサイズ <math>n</math> に対して多項式の計算時間を持たねばならないが、<math>\varepsilon</math> に対してはそうではない。<math>\varepsilon</math> に対するEPTASと同様の制約を持つものを'''効率的多項式時間乱択近似スキーム'''（'''EPRAS'''<ref>{{lang-en-short|efficient polynomial-time randomized approximation scheme}}</ref>）と呼ぶ。また、FPTASと同様の制約を持つものを'''完全多項式時間乱択近似スキーム'''（'''FPRAS'''<ref>{{lang-en-short|fully polynomial-time randomized approximation scheme}}</ref>）と呼ぶ。<ref name="vvv">{{cite book
  | last = Vazirani
  | first = Vijay V.
  | title = Approximation Algorithms
  | publisher = Springer
  | year = 2003
  | pages = 294–295
  | location = Berlin
  | isbn = 3-540-65367-8
}}</ref>

==脚注==
<references/>

==外部リンク==
*Complexity Zoo: [http://qwiki.stanford.edu/index.php/Complexity_Zoo:P#ptas PTAS], [http://qwiki.stanford.edu/index.php/Complexity_Zoo:E#eptas EPTAS], [http://qwiki.stanford.edu/index.php/Complexity_Zoo:F#fptas FPTAS]
*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''] – list which NP optimization problems have PTAS.

{{DEFAULTSORT:たこうしきしかんきんしすきいむ}}
[[Category:近似アルゴリズム]]
[[Category:複雑性クラス]]
[[Category:数学に関する記事]]