多項式時間近似スキーム

多項式時間近似スキーム（PTAS）とは

計算機科学において、多項式時間近似スキーム（PTAS）は、特にNP困難な最適化問題に対して用いられる近似アルゴリズムの一種です。これは、与えられた最適化問題のインスタンスとパラメータ ε > 0 を入力として受け取り、多項式時間内で最適解の (1 + ε) 倍以下（最大化問題の場合は (1 - ε) 倍以上）の解を求めることを目的とします。例えば、ユークリッド距離に基づく巡回セールスマン問題では、最適解の長さを L としたとき、PTASを用いることで、高々 (1 + ε)L の長さの解を見つけることができます。

PTASの重要な特徴は、その実行時間が問題のサイズ n に対して多項式時間である必要がある点です。しかし、パラメータ ε に対しては多項式時間である必要はありません。そのため、実行時間が O(n^(1/ε)) や O(n^exp(1/ε)) のようなオーダーであっても、PTASとみなされます。この点が、後に述べる効率的な多項式時間近似スキーム（EPTAS）や完全多項式時間近似スキーム（FPTAS）との違いを生み出します。

PTASの変形

PTASには、いくつかの変形が存在します。以下にそれらを説明します。

効率的な多項式時間近似スキーム（EPTAS）

現実的な問題において、PTASは ε を小さくすると多項式の指数部が非常に大きくなってしまうことがあります。例えば、実行時間が O(n^((1/ε)!)) のように ε に大きく依存する場合があります。この問題に対処するために考案されたのが、効率的な多項式時間近似スキーム（EPTAS）です。

EPTASは、実行時間が O(n^c) であるアルゴリズムです。ここで c は ε と独立な定数です。これにより、ε の値に関わらず、問題のサイズが実行時間に与える影響は一定になります。しかし、O記法における定数は ε に対して任意に大きくなりうる点には注意が必要です。

完全多項式時間近似スキーム（FPTAS）

さらに強い制約を持つのが、完全多項式時間近似スキーム（FPTAS）です。FPTASは、実行時間が問題のサイズ n と 1/ε の両方に対して多項式時間であるものを指します。例えば、ナップサック問題はFPTASを持つ問題の例として知られています。

FPTASの限界

多項式的に有界な目的関数を持つ強度にNP困難な最適化問題は、P=NPでない限りFPTASを持ち得ません。ただし、逆は必ずしも真ではありません。例えば、P≠NPの場合、2つの制約を持つナップサック問題はFPTASを持ちませんが、目的関数が多項式的に有界であっても強度にNP困難ではない問題も存在します。

各スキームの関係性

P=NPでない場合、FPTAS ⊂ PTAS ⊂ APX という包含関係が成り立ちます。これは、APX困難な問題はPTASを持たないことを意味します。

準多項式時間近似スキーム（QPTAS）

PTASの別の変形として、準多項式時間近似スキーム（QPTAS）があります。QPTASは、ある固定された ε に対して、実行時間が n^polylog(n) のオーダーとなるアルゴリズムです。

乱択近似スキーム

決定的なPTASの他に、乱択アルゴリズムを用いた近似スキームも存在します。

多項式時間乱択近似スキーム（PRAS）

PTASを持たない問題でも、多項式時間乱択近似スキーム（PRAS）を持つ場合があります。PRASは、最適化問題のインスタンスとパラメータ ε > 0 を入力とし、多項式時間で「高い確率」で最適解の (1 + ε) 倍以下の解を生成します。「高い確率」とは、通常 3/4 以上を指しますが、ほとんどの確率的計算複雑度のクラスでは、この具体的な値は重要ではありません。

PRASもPTASと同様に、問題のサイズ n に対して多項式時間の計算時間を持ちますが、パラメータ ε に対してはその限りではありません。

効率的多項式時間乱択近似スキーム（EPRAS）と完全多項式時間乱択近似スキーム（FPRAS）

PRASには、EPTASと同様に ε に対する制約を持つ効率的多項式時間乱択近似スキーム（EPRAS）、およびFPTASと同様の制約を持つ完全多項式時間乱択近似スキーム（FPRAS）が存在します。

まとめ

PTASは、NP困難な最適化問題に対する重要な近似アルゴリズムの枠組みです。PTAS、EPTAS、FPTAS、QPTAS、PRASなど、さまざまな変形が存在し、問題の特性や要求される精度に応じて適切なスキームを選択することが重要です。

もう一度検索