Le Cam シミュラビリティによる近似計算フレームワーク

この論文は、正確な解から決定的に有効な近似へと焦点を移し、計算複雑性に対する新しい決定論的フレームワークを提案しています。計算欠陥を定義し、正確に解くことは難しいが近似が容易な問題を特徴付けるLeCam-Pクラスを導入しています。この論文の重要性は、アルゴリズムの複雑性と決定理論のギャップを埋め、近似理論に新たな視点を提供し、計算的に困難な問題の分類とアプローチに影響を与える可能性にある。

• •計算複雑性に対する決定論的フレームワークを提案。
• •正確な解ではなく、決定的に有効な近似に焦点を当てる。
• •計算欠陥とLeCam-Pクラスを導入。
• •古典的なKarp還元をゼロ欠陥シミュレーションに接続。
• •No-Free-Transfer不等式を確立。