計算の複雑さ
Author(s)
Bibliographic Information
計算の複雑さ
（ソフトウェア講座 / 井上謙蔵, 中田育男, 志村正道編集委員, 33）
昭晃堂, 1988.5
- Other Title
-
Theory of computational complexity
- Title Transcription
-
ケイサン ノ フクザツサ
Available at 147 libraries
Search this Book/Journal
Note
参考文献: p146-147
Description and Table of Contents
Description
本書は、計算の複雑さの理論が一体どのような現象を解明しようとしているのか、そしてどのような結果が得られつつあるのかを、できるだけコンパクトに紹介することを目標とした。
Table of Contents
- １ Ｔｕｒｉｎｇ機械とその基本的性質（決定性Ｔｕｒｉｎｇ機械；Ｔｕｒｉｎｇ機械の計算の複雑さ；Ｔｕｒｉｎｇ機械のシミュレーション；非決定性Ｔｕｒｉｎｇ機械；決定性Ｔｕｒｉｎｇ機械による非決定性Ｔｕｒｉｎｇ機械のシミュレーション；集合のいろいろなクラス）
- ２ 万能Ｔｕｒｉｎｇ機械とその応用（万能Ｔｕｒｉｎｇ機械；構成可能関数；分離定理；ｐａｄｄｉｎｇ法；還元可能性；完全集合とその存在完全集合の応用）
- ３ ＮＰ完全な問題（論理式の充足可能性問題；いくつかのＮＰ完全集合；正規表現に関する完全問題）
- ４ ＮＰの構造（ＮＰの重要性；ＮＰ完全集合のｐ同値性；疎なＮＰ完全集合；ＮＰ完全でない集合；Ｐ＝ＮＰ？問題の相対化；ランダムなオラクルによる相対化；多項式時間階層）
by "BOOK database"