APX

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

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

最適解の乗法因子が 1 より悪い場合、その因子の範囲内で問題を解く多項式時間アルゴリズムが存在する場合、その問題は多項式時間近似スキーム ( PTAS )を持つと言われます。P = NPでない限り、APX に含まれるが PTAS を持たない問題が存在するため、PTAS を持つ問題のクラスは厳密に APX に含まれます。PTAS を持つ問題の 1 つはナップサック問題です。

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

• 近似保存型縮小
• 複雑性クラス
• 近似アルゴリズム
• 最大/最小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年4月13日にアーカイブ済み。「NP最適化問題の概要」 Wayback Machineに2007年4月5日にアーカイブ済み。