# Reducibility Among Combinatorial Problems > [!abstract] 概要 > 計算問題の大きなクラスは、グラフ、有向グラフ、整数、整数の配列、有限集合の有限族、ブール論理式、およびその他の可算領域の要素の性質の決定を含んでいる。そのような領域から有限アルファベット上の語の集合への単純な符号化を通じて、これらの問題は言語認識問題へと変換でき、我々はそれらの計算複雑性を探求することができる。ある問題に対する解法アルゴリズムが見つかり、それが入力長に対する多項式で抑えられるステップ数で終了するとき、その問題は満足に解かれたと見なすのが合理的である。我々は、被覆、マッチング、パッキング、ルーティング、割り当て、および順序付けに関する多数の古典的な未解決問題が、それらの各々が多項式限定アルゴリズムを持つか、あるいはそれらのいずれも持たないか、のいずれかであるという意味において同値であることを示す。 ## 論文情報 - **著者**: Richard M. Karp（[[Richard M. Karp]]） - **所属**: [[University of California, Berkeley]] - **掲載書**: *Complexity of Computer Computations* (The IBM Research Symposia Series), edited by R. E. Miller and J. W. Thatcher, Plenum Press, pp. 85–103, 1972. - **DOI**: [10.1007/978-1-4684-2001-2_9](https://doi.org/10.1007/978-1-4684-2001-2_9) ## 概要 本論文は、計算量理論において「[[多項式時間還元]]（Karp 還元）」を確立し、21の代表的な古典的組合せ問題が NP 完全であることを証明した金字塔的論文である。Cook（1971）が命題論理式の充足可能性問題（SAT）が NP 完全であることを示したのに対し、Karp は SAT を出発点として、グラフ理論、集合論、整数計画、スケジュール問題など極めて多様な分野にまたがる問題群が、多項式時間変換によって相互に還元可能であることを示した。これにより、NP 完全性が理論的な人工物ではなく、応用計算機科学全般に普遍的に現れる内在的困難性の境界であることが決定的となった。 ## 問題設定と定義 - **クラス P**: 決定性チューリング機械により多項式時間で認識可能な言語のクラス。 - **クラス NP**: 非決定性チューリング機械により多項式時間で認識可能な言語のクラス。 - **多項式時間還元（$\le_P$）**: 言語 $L_1$ から $L_2$ への多項式時間計算可能な関数 $f$ が存在し、$x \in L_1 \iff f(x) \in L_2$ を満たすとき、$L_1 \propto L_2$（多項式時間還元可能）と定義する。 - **完全問題（Complete Problems）**: クラス NP に属し、かつ任意の $L \in ext{NP}$ に対して $L \propto L_0$ が成立する言語 $L_0$。 ## 還元の構造と21のNP完全問題 Karp は Cook の定理（SATISFIABILITY $\in ext{NP-complete}$）を出発点として、木構造の多項式時間還元ネットワークを構築した。 **Figure 1: Complete Problems の還元ツリー** ![[_attachments/Reducibility-Among-Combinatorial-Problems/fig01-tree-of-reductions.png]] (Figure 1. SATISFIABILITY から始まる多項式時間還元の系統樹。各矢印は上の問題から下の問題への多項式時間還元を表す。) ### Karp の 21 の NP 完全問題 1. **SATISFIABILITY**: 命題論理式の充足可能性（Cook 1971） 2. **0-1 INTEGER PROGRAMMING**: 0-1 整数計画法 3. **CLIQUE**: クリーク（完全部分グラフ）の存在判定 4. **SET PACKING**: 互いに素な部分集合族の選択 5. **NODE COVER**: 頂点被覆問題 6. **SET COVERING**: 集合被覆問題 7. **FEEDBACK NODE SET**: フィードバック頂点集合 8. **FEEDBACK ARC SET**: フィードバック辺集合 9. **DIRECTED HAMILTONIAN CIRCUIT**: 有向ハミルトン閉路 10. **UNDIRECTED HAMILTONIAN CIRCUIT**: 無向ハミルトン閉路 11. **SATISFIABILITY WITH AT MOST 3 LITERALS PER CLAUSE (3-SAT)**: 3リテラルSAT 12. **CHROMATIC NUMBER**: グラフの彩色数 13. **CLIQUE COVER**: クリーク被覆問題 14. **EXACT COVER**: 完全被覆問題 15. **HITTING SET**: ヒッティング集合問題 16. **STEINER TREE**: シュタイナー木問題 17. **3-DIMENSIONAL MATCHING**: 3次元マッチング 18. **KNAPSACK**: ナップサック問題 19. **JOB SEQUENCING**: 納期遅延ペナルティ最小化ジョブスケジューリング 20. **PARTITION**: 集合の2分割問題 21. **MAX CUT**: 最大カット問題 ## 新規性と理論的意義 1. **多対一多項式時間還元（Karp還元）の確立**: Cook のチューリング還元に対し、検証が容易で構造保存性の高い多対一還元を定式化した。 2. **NP完全性の普遍性の実証**: SAT という論理学の枠組みから、ネットワーク設計、スケジューリング、最適化といった実用分野のあらゆる中核問題が同一の困難性クラスに属することを証明した。 3. **P対NP問題の中心的パラダイム化**: これら21のいずれか1つでも多項式時間アルゴリズムが存在すれば、全てのNP問題が多項式時間で解ける（$P = NP$）という劇的な同値関係を提示した。 ## 考察 Karp の論文は、アルゴリズム設計者に「多項式時間厳密解法を探すことを諦め、近似アルゴリズム、ヒューリスティクス、または特定部分クラスへの制約を探求する」という現実的かつ生産的な指針を与えた。現代のアルゴリズム論、近似アルゴリズム論、計算困難性研究のすべての基盤となった。 ## 出典 - Richard M. Karp, "Reducibility Among Combinatorial Problems", *Complexity of Computer Computations*, Plenum Press, pp. 85–103, 1972.