近似の難しさ

コンピュータサイエンスにおいて、近似の困難性は、最適化問題に対する最適に近い解を見つけるアルゴリズムの複雑さを研究する分野です。

近似困難性は、特定の問題に対して、その解を効率的に近似できる因数の限界を証明することにより、近似アルゴリズムの研究を補完します。通常、このような限界は、それを超えると問題がNP 困難になる近似因数を示し、 NP=Pでない限り、問題の多項式時間近似を見つけることは不可能であることを意味します。ただし、近似困難性の結果の中には、他の仮説に基づくものもあり、その中で注目すべきものとしては、ユニークゲーム予想があります。

1970 年代初頭以来、多くの最適化問題はP = NPでない限り多項式時間で解くことができないことが知られていましたが、これらの問題の多くでは、最適解はある程度効率的に近似できました。 1970 年代に、Teofilo F. GonzalezとSartaj Sahni は、特定の最適化問題が与えられた近似率内で近似することさえ NP 困難であることを示し、近似の困難さの研究を始めました。 つまり、これらの問題にはしきい値があり、このしきい値を超える近似率を持つ任意の多項式時間近似を使用して、NP 完全問題を多項式時間で解くことができます。^[1] 1990 年代初頭、PCP理論の発展により、近似が困難な近似問題がさらに多くあり、( P = NP でない限り) 既知の近似アルゴリズムの多くが可能な限り最高の近似率を達成していることが明らかになりました。

近似理論の困難性は、このような問題の近似しきい値の研究を扱います。

近似するのが難しい NP 困難な最適化問題の例については、set cover を参照してください。

• PCP定理

• Trevisan, Luca (2004 年 7 月 27 日)、組み合わせ最適化問題の近似不可能性(PDF)、arXiv : cs/0409043、Bibcode :2004cs.......9043T

• CSE 533: PCP 定理と近似の困難性、2005 年秋、ワシントン大学シラバス、Venkatesan GuruswamiおよびRyan O'Donnell