Loading article…
コンピュータサイエンス（特にアルゴリズム）において、多項式時間近似スキーム（PTAS ）は、最適化問題（多くの場合、NP困難な最適化問題）に対する近似アルゴリズムの一種である。
PTAS は、最適化問題のインスタンスとパラメータε > 0を受け取り、最適解から1 + ε倍以内の解(最大化問題の場合は1 – ε以内) を生成するアルゴリズムです。たとえば、ユークリッド巡回セールスマン問題の場合、PTAS は最短巡回の長さをLとしたとき、長さが最大(1 + ε) Lの巡回ルートを生成します。[ 1 ]
PTAS の実行時間は、固定された ε に対して問題サイズの多項式である必要がありますが、ε が異なると実行時間は異なっても構いません。したがって、O ( n 1/ε )またはO ( n exp(1/ε) )の時間で実行されるアルゴリズムはPTAS とみなされます。
PTAS アルゴリズムの実際的な問題点は、実行時間がO ( n (1/ε)! )の場合など、ε が小さくなるにつれて多項式の指数が劇的に増加する可能性があることです。この問題を解決する 1 つの方法は、効率的な多項式時間近似スキーム( EPTAS)を定義することです。EPTASでは、実行時間はεに依存しない定数cに対してO ( n c )である必要があります。これにより、問題サイズの増加が、使用される ε の値に関係なく、実行時間に同じ相対的な影響を与えることが保証されます。ただし、ビッグ オー記法の定数は、依然として ε に任意に依存する可能性があります。言い換えれば、EPTAS は、パラメータが ε であるFPT時間で実行されます。
さらに制約が厳しく、実用上有用なのが、完全多項式時間近似スキーム（FPTAS）で、アルゴリズムが問題サイズnと1/εの両方に関して多項式時間であることを要求します。
P = NPでない限り、 FPTAS ⊊ PTAS ⊊ APXが成り立つ。[ 2 ]したがって、この仮定の下では、APX 困難問題には PTAS は存在しない。
PTAS のもう 1 つの決定論的バリアントは、準多項式時間近似スキーム( QPTAS)です。QPTAS は、固定されたε > 0ごとに、n polylog ( n )の時間計算量 を持ちます。さらに、PTAS は問題のいくつかのパラメータ化に対してFPT時間で実行でき、これによりパラメータ化された近似スキームが実現します。
PTAS が存在しない問題の中には、同様の特性を持つランダム化アルゴリズム、多項式時間ランダム化近似スキーム( PRAS)が許容されるものがある。PRAS は、最適化問題または計数問題のインスタンスとパラメータε > 0を受け取り、多項式時間で最適解からε倍以内の確率が高い解を生成するアルゴリズムである。慣習的に、「高い確率」とは 3/4 より大きい確率を意味するが、ほとんどの確率的複雑性クラスと同様に、この定義は正確な値の変動に対して頑健である (最低限の要件は一般的に 1/2 より大きい)。PTAS と同様に、PRAS の実行時間はn の多項式でなければならないが、必ずしもεの多項式である必要はない。εの実行時間にさらに制約を加えることで、 EPTAS に類似した効率的な多項式時間ランダム化近似スキーム( EPRAS)と、 FPTAS に類似した完全な多項式時間ランダム化近似スキーム( FPRAS)を定義できる。[ 3 ]
PTASという用語は、PTASを持つ最適化問題のクラスを指す場合にも使用されることがあります。PTASはAPXの部分集合であり、P = NPでない限り、厳密な部分集合です。[ 2 ]
PTAS への所属は、PTAS の所属を維持するPTAS 還元、L 還元、またはP 還元を用いて示すことができ、これらは PTAS の完全性を示すためにも使用できます。一方、PTAS に所属していないこと (つまり、PTAS が存在しないこと) は、問題が APX 困難であることを示すことで示すことができ、その後、PTAS の存在は P = NP を示します。APX 困難性は、一般的に PTAS 還元またはAP 還元によって示されます。