インド

計算複雑性理論において、クラスAPX (「近似可能」の略) は、近似率が定数で制限される多項式時間近似アルゴリズム(または略して定数係数近似アルゴリズム) を許可するNP 最適化問題の集合です。簡単に言えば、このクラスの問題には、最適な答えの一定の乗数内で答えを見つけることができる 効率的なアルゴリズムがあります。

近似アルゴリズムは、アルゴリズムが見つけた解が最適解より最大で 倍の係数だけ悪くなることが証明できる場合、入力サイズに対する -近似アルゴリズムと呼ばれます。ここで、 は近似比と呼ばれます。APX の問題は、近似比が定数 であるアルゴリズムを使用する問題です。近似比は通常、1 より大きいと表現されます。最小化問題の場合、は見つかった解のスコアを最適解のスコアで割ったものであり、最大化問題の場合はその逆になります。最大化問題では、劣った解のスコアが小さくなるため、は 1 未満と表現されることがあります。このような場合、 の逆数は、見つかった解のスコアと最適解のスコアの比です。 ${\displaystyle f(n)}$${\displaystyle n}$${\displaystyle f(n)}$${\displaystyle f(n)}$${\displaystyle f(n)}$${\displaystyle c}$${\displaystyle f(n)}$${\displaystyle f(n)}$${\displaystyle f(n)}$

最適値の 1 より悪いすべての乗法係数に対して、その係数内で問題を解く多項式時間アルゴリズムが存在する場合、その問題は多項式時間近似スキーム ( PTAS )を持つと言われます。P = NPでない限り、APX に含まれるが PTAS を持たない問題が存在するため、PTAS を持つ問題のクラスは厳密に APX に含まれます。PTAS を持つ問題の 1 つの例は、ビン パッキング問題です。

APX 内のすべての問題からその問題へのPTAS 還元が存在する場合、その問題はAPX 困難であると言われ、問題が APX 困難であり、かつ APX でもある場合、その問題はAPX 完全であると言われます。P ≠ NP ⇒ PTAS ≠ APX の結果として、P ≠ NP が仮定されている場合、APX 困難な問題には PTAS がありません。実際には、APX 完全性を証明するために 1 つの問題を別の問題に還元することは、 PTAS 還元を意味するL 還元などの他の還元スキームを使用して行われることがよくあります。

最も単純な APX 完全問題の 1 つは、ブール充足可能性問題のバリエーションであるMAX-3SAT-3です。この問題では、各変数が最大 3 回出現する連言正規形のブール式があり、変数に true/false 値を 1 回割り当てるだけで同時に満たすことができる節の最大数を知りたいと考えています。

その他の APX 完全問題には次のものがあります:

• 制限次数グラフの最大独立集合(ここで、近似比はグラフの最大次数に依存しますが、最大次数が固定されている場合は一定です)。
• 最小頂点カバー。任意の最大独立集合の補集合は頂点カバーでなければなりません。
• 制限された次数グラフにおける最小支配集合。
• グラフ内の距離がメトリックの条件を満たす場合の巡回セールスマン問題。TSP は一般的なケースではNPO 完全です。
• 集合被覆からのL 削減によるトークン再構成問題。

PTAS (多項式時間近似スキーム) は、入力サイズに対して多項式の時間で 1 以外の任意の定数係数内で近似できる問題で構成されますが、多項式はそのような係数に依存します。このクラスは APX のサブセットです。

P = NPでない限り、APX には PTAS でも APX 完全でもない問題が存在します。このような問題は、PTAS 問題と APX 完全問題の間の難しさを持つと考えられ、APX 中間問題と呼ばれることがあります。ビンパッキング問題はAPX 中間問題であると考えられています。既知の PTAS がないにもかかわらず、ビンパッキング問題には、最適解が大きい場合に PTAS のように動作するいくつかの「漸近 PTAS」アルゴリズムがあるため、直感的には APX 困難な問題よりも簡単な場合があります。

潜在的に APX 中間問題のもう 1 つの例は、最小エッジ カラーリングです。

また、複雑性クラスのファミリー-APX を定義することもできます。ここで、-APX には、近似比を持つ多項式時間近似アルゴリズムの問​​題が含まれます。同様に、-APX 完全クラスを定義することもできます。このようなクラスには、よく知られている最適化問題が含まれます。Log-APX 完全性とポリ APX 完全性は、PTAS 縮小ではなくAP 縮小によって定義されます。これは、PTAS 縮小が APX には十分であるにもかかわらず、Log-APX およびポリ APX のメンバーシップを維持するほど強力ではないためです。 ${\displaystyle f(n)}$${\displaystyle f(n)}$${\displaystyle O(f(n))}$${\displaystyle f(n)}$

入力サイズの対数係数内で効率的に近似できる最も困難な問題で構成される Log-APX 完全問題には、次数が無制限の場合の 最小支配セットが含まれます。

ポリ APX 完全は、入力サイズの因数多項式内で効率的に近似できる最も困難な問題で構成され、一般的なケースでは 最大独立集合が含まれます。

近似率が入力サイズに対して指数関数的である、exp-APX 完全な問題も存在します。これは、近似が問題インスタンス内の数値に依存している場合に発生する可能性があります。これらの数値は、空間的に対数的に表現される可能性があり、そのため指数係数となります。

• 近似値保存縮小
• 複雑度クラス
• 近似アルゴリズム
• 最大/最小 CSP/Ones 分類定理- ブール関係に関する問題を近似複雑性クラスに機械的に分類できるようにする定理のセット
• MaxSNP - 密接に関連するサブクラス

• 複雑性動物園: APX
• C. Papadimitriou および M. Yannakakis。最適化、近似および複雑性クラス。Journal of Computer and System Sciences、43:425–440、1991 年。
• Pierluigi Crescenzi、Viggo Kann、Magnús Halldórsson、Marek Karpinski、Gerhard Woeginger 。最大満足度。Wayback Machineに 2007-04-13 にアーカイブ。NP 最適化問題の概要。Wayback Machineに 2007-04-05 にアーカイブ。