カープの21のNP完全問題

計算複雑性理論において、カープの21のNP完全問題は、NP完全である計算問題の集合である。リチャード・カープは、1972年の論文「組合せ問題の中の還元可能性」^[1]で、ブール充足可能性問題はNP完全であるというスティーブン・クックの1971年の定理^{[2] （}クック＝レビンの定理とも呼ばれる）を用いて、ブール充足可能性問題から21の組合せおよびグラフ理論計算問題のそれぞれに多項式時間の多対一還元が存在することを示し、それによってそれらがすべてNP完全であることを示した。これは、コンピュータサイエンス全体で発生する多くの自然な計算問題が計算上手に負えないことを初めて実証したものの1つであり、NP完全性およびP対NP問題の研究への関心を高めた。

以下に、Karp の 21 の問題を示します。その多くは元の名前が付けられています。ネストにより、使用された削減の方向が示されます。たとえば、Knapsack は、 Exact cover をKnapsackに削減することで NP 完全であることが示されました。

• 充足可能性:連言正規形の式に対するブール充足可能性問題(SAT とも呼ばれる)
  • 0–1 整数計画法(最適化を行わず、制約のみを満たすバリエーション)
  • クリーク（独立集合問題も参照）
    • セット梱包
    • 頂点カバー
      • カバーを設定する
      • フィードバックノードセット
      • フィードバックアークセット
      • 有向ハミルトン回路（カープの名称、現在では通常有向ハミルトン回路と呼ばれる）
        • 無向ハミルトン回路（カープの名称、現在では通常無向ハミルトン回路と呼ばれる）
  • 1 節あたり最大 3 つのリテラルによる満足可能性(3-SAT に相当)
    • 彩色数（グラフ彩色問題とも呼ばれる）
      • クリークカバー
      • 正確なカバー
        • 打撃セット
        • シュタイナーの木
        • 3次元マッチング
        • ナップサック（カープのナップサックの定義はサブセットの合計に近い）
          • ジョブの順序付け
          • パーティション
            • 最大カット

時が経つにつれ、多くの問題は特殊なケースに限定すれば効率的に解けること、あるいは最適結果の一定の割合内で解けることが発見された。しかし、デイビッド・ザッカーマンは1996年に、これら21の問題のすべてに、P = NPでない限り定数倍で近似することが不可能な制約付き最適化バージョンがあることを示し、カープの削減アプローチが特定のタイプの近似可能性削減に一般化されることを示した。^[3]ただし、これらは問題の標準的な最適化バージョンとは異なる場合があり、標準的な最適化バージョンには近似アルゴリズムがある可能性がある（最大カットの場合など）ことに注意する必要がある。

• NP完全問題のリスト

• クック、スティーブン(1971)。「定理証明手順の複雑さ」。第 3 回 ACM コンピューティング理論シンポジウム (STOC) 議事録。pp . 151–158。doi : 10.1145 /800157.805047。ISBN 9781450374644. S2CID  7573663。
• Karp, Richard M. (1972)。「組み合わせ問題における縮約可能性」( PDF)。RE Miller、JW Thatcher、JD Bohlinger (編)。『コンピュータ計算の複雑性』。ニューヨーク: Plenum。pp. 85–103。doi : 10.1007 /978-1-4684-2001-2_9。ISBN 978-1-4684-2003-6。
• Zuckerman, David (1996). 「NP完全問題の近似不可能なバージョンについて」SIAM Journal on Computing . 25 (6): 1293–1304. doi :10.1137/S0097539794266407.[1]