ソフトウェア講座（３３） 計算の複雑さ

小林 孝次郎【著】

昭晃堂（1988/05発売）

• サイズ A5判／ページ数 155p／高さ 22X16cm
• 商品コード 9784785635336
• NDC分類 418
• Cコード C3055

内容説明

本書は、計算の複雑さの理論が一体どのような現象を解明しようとしているのか、そしてどのような結果が得られつつあるのかを、できるだけコンパクトに紹介することを目標とした。

目次

１　Ｔｕｒｉｎｇ機械とその基本的性質（決定性Ｔｕｒｉｎｇ機械；Ｔｕｒｉｎｇ機械の計算の複雑さ；Ｔｕｒｉｎｇ機械のシミュレーション；非決定性Ｔｕｒｉｎｇ機械；決定性Ｔｕｒｉｎｇ機械による非決定性Ｔｕｒｉｎｇ機械のシミュレーション；集合のいろいろなクラス）
２　万能Ｔｕｒｉｎｇ機械とその応用（万能Ｔｕｒｉｎｇ機械；構成可能関数；分離定理；ｐａｄｄｉｎｇ法；還元可能性；完全集合とその存在完全集合の応用）
３　ＮＰ完全な問題（論理式の充足可能性問題；いくつかのＮＰ完全集合；正規表現に関する完全問題）
４　ＮＰの構造（ＮＰの重要性；ＮＰ完全集合のｐ同値性；疎なＮＰ完全集合；ＮＰ完全でない集合；Ｐ＝ＮＰ？問題の相対化；ランダムなオラクルによる相対化；多項式時間階層）