Loading article…
 | |
| 著者 | マイケル・R・ギャリーとデビッド・S・ジョンソン |
|---|---|
| 言語 | 英語 |
| シリーズ | 数学科学に関する書籍シリーズ |
| 主題 | コンピュータサイエンス |
| ジャンル | 教科書 |
| 出版社 | W. H. フリーマン アンド カンパニー |
発行日 | 1979 |
| 出版地 | アメリカ合衆国 |
| メディアタイプ | 印刷 |
| ページ | x+338 |
| 番号 | 0-7167-1045-5 |
| OCLC | 247570676 |
| 519.4 | |
| LCクラス | QA76.6 .G35 |
コンピュータとイントラクタビリティ：NP完全性理論ガイドは、マイケル・ギャリーとデビッド・S・ジョンソンによる教科書です。 [1]これは、 NP完全性と計算イントラクタビリティ の理論だけを扱った最初の本でした。 [2]この本には、NP完全問題の完全な概要を提供する付録が付いています（この本の後の印刷で更新されました）。この本は、 PCP定理などの最近の開発をカバーしていないため、いくつかの点で今では時代遅れになっています。それでもまだ印刷されており、古典と見なされています。2006年の調査では、 CiteSeer検索エンジンは、この本をコンピュータサイエンスの文献で最も引用されている参考文献としてリストしました。 [3]
未解決の問題
この本の別の付録には、NP 完全か P か (あるいはどちらでもない) が不明な問題が掲載されていました。問題 (元の名前) は次のとおりです。
- グラフ同型性
- この問題は NP であることはわかっていますが、NP 完全であるかどうかは不明です。
- 部分グラフ同相性（固定グラフHに対して）
- グラフの属
- 弦グラフの補完
- 色指数[4]
- スパニングツリーパリティ問題[5]
- 半順序次元
- 優先順位制約付き3プロセッサスケジューリング
- この問題は2016年時点でも未解決のままであった。[6]
- 線形計画法
- 総ユニモジュラ性[7]
- 合成数
- 合成性のテストは P に含まれることが知られていますが、密接に関連する整数因数分解問題の複雑さは未解決のままです。
- 最小長三角測量[8]
- 問題 12 は NP 困難であることがわかっていますが、NP に属するかどうかは不明です。
受付
この本は出版後すぐに、理論計算機科学の分野で名高い研究者から好評を得ました。
ロナルド・V・ブックはレビューの中で、この本を「NP完全性について学びたい人」に勧めており、300以上のNP困難な計算問題を含む「非常に役立つ」付録について明確に言及している。彼は「コンピュータサイエンスには、このような本がもっと必要だ」と結論付けている。[9]
ハリー・R・ルイスは著者らの数学的文章を称賛している。「ゲイリーとジョンソンの本は、NP完全性について徹底的かつ明快で実践的な解説をしている。多くの点で、この主題についてこれ以上の扱いを想像するのは難しい。」また、彼は付録を「ユニーク」であり、「新しい問題がNP完全であることを示す試みの出発点」であると考えている。[10]
この本が出版されてから23年後、科学雑誌Transactions on Computational Theoryの編集長ランス・フォートナウは次のように述べている。「私は、ゲーリーとジョンソンの本を私のオフィスの本棚で最も重要な本だと考えています。すべてのコンピュータ科学者もこの本を自分の本棚に置くべきです。[...] ゲーリーとジョンソンは、私が今まで見た中で最も優れた計算複雑性の入門書です。」[11]
参照
参考文献
- ^ Garey, M. R. ; Johnson, D. S. (1979). Victor Klee (ed.). Computers and Intractability: A Guide to the Theory of NP-Completeness . A Series of Books in the Mathematical Sciences. サンフランシスコ、カリフォルニア州: W. H. Freeman and Co. ISBN 0-7167-1045-5. MR 0519066.338 ページ。archive.orgでコピーできます。
- ^ Juris Hartmanis (1982). 「コンピュータと扱いにくさ: NP完全性理論ガイド」書評. SIAM Review . 24 (1): 90–91. doi :10.1137/1024022. JSTOR 2029450.
- ^ 「コンピュータサイエンス分野で最も引用された記事 - 2006 年 9 月 (CiteSeer.Continuity)」。2007 年 11 月 3 日閲覧。
- ^ NP完全: Holyer, Ian (1981年11月). 「エッジカラーリングのNP完全性」. SIAM Journal on Computing . 10 (4): 718–720. doi :10.1137/0210055.
- ^ P では: Lovász、L. Lovász、L.; Sós、VT (編)。グラフ理論における代数的手法、第 II 巻 (コロキウム セゲド、1978 年)。 Colloquia Mathematica Societatis János Bolyai、25、北オランダ。 495–517ページ。
- ^ van Bevern, René; Bredereck, Robert; Bulteau, Laurent; Komusiewicz, Christian; Talmon, Nimrod; Woeginger, Gerhard J. (2016). 「部分順序幅によってパラメータ化された優先順位制約付きスケジューリング問題」。DOOR 2016: 離散最適化とオペレーションズ・リサーチ。コンピュータサイエンスの講義ノート。 Vol. 9869。Springer-Verlag。 pp. 105–120。arXiv : 1605.00901。doi :10.1007/978-3-319-44914-2_9。
- ^ P: Seymour , PD (1980年6月)。「正則マトロイドの分解」(PDF)。Journal of Combinatorial Theory、シリーズB。28 ( 3 ): 305–359。doi : 10.1016/0095-8956(80)90075-1。
- ^ NP困難か: Mulzer, Wolfgang; Rote, Günter (2008)、「最小重み三角法はNP困難である」、Journal of the ACM、55 ( 2)、Art. 11 、arXiv : cs.CG/0601002、doi:10.1145/1346330.1346336、MR 2417038
- ^ ロナルド V. 著作。レビュー：コンピュータと扱いにくさ：NP完全性理論のガイド Bull. Amer. Math. Soc. (NS)、3 (2)、pp. 898–904、1980
- ^ ハリー・R・ルイス、レビュー：コンピュータと扱いにくさ：NP完全性理論へのガイド、Journal of Symbolic Logic 、第48巻（2）、pp.498-500、1983年
- ^ Lance Fortnow、Great Books: Computers and Intractability: A Guide to the Theory of NP-Completeness、Michael R. Garey および David S. Johnson 著。計算複雑性ブログ、2002 年 8 月 30 日。