計算の複雑さ
著者
書誌事項
計算の複雑さ
（ソフトウェア講座 / 井上謙蔵, 中田育男, 志村正道編集委員, 33）
昭晃堂, 1988.5
- タイトル別名
-
Theory of computational complexity
- タイトル読み
-
ケイサン ノ フクザツサ
大学図書館所蔵 件 / 全147件
-
該当する所蔵館はありません
- すべての絞り込み条件を解除する
この図書・雑誌をさがす
注記
参考文献: p146-147
内容説明・目次
内容説明
本書は、計算の複雑さの理論が一体どのような現象を解明しようとしているのか、そしてどのような結果が得られつつあるのかを、できるだけコンパクトに紹介することを目標とした。
目次
- １ Ｔｕｒｉｎｇ機械とその基本的性質（決定性Ｔｕｒｉｎｇ機械；Ｔｕｒｉｎｇ機械の計算の複雑さ；Ｔｕｒｉｎｇ機械のシミュレーション；非決定性Ｔｕｒｉｎｇ機械；決定性Ｔｕｒｉｎｇ機械による非決定性Ｔｕｒｉｎｇ機械のシミュレーション；集合のいろいろなクラス）
- ２ 万能Ｔｕｒｉｎｇ機械とその応用（万能Ｔｕｒｉｎｇ機械；構成可能関数；分離定理；ｐａｄｄｉｎｇ法；還元可能性；完全集合とその存在完全集合の応用）
- ３ ＮＰ完全な問題（論理式の充足可能性問題；いくつかのＮＰ完全集合；正規表現に関する完全問題）
- ４ ＮＰの構造（ＮＰの重要性；ＮＰ完全集合のｐ同値性；疎なＮＰ完全集合；ＮＰ完全でない集合；Ｐ＝ＮＰ？問題の相対化；ランダムなオラクルによる相対化；多項式時間階層）
「BOOKデータベース」 より
