計算の複雑さ
著者
書誌事項
計算の複雑さ
(ソフトウェア講座 / 井上謙蔵, 中田育男, 志村正道編集委員, 33)
昭晃堂, 1988.5
- タイトル別名
-
Theory of computational complexity
- タイトル読み
-
ケイサン ノ フクザツサ
大学図書館所蔵 全147件
  青森
  岩手
  宮城
  秋田
  山形
  福島
  茨城
  栃木
  群馬
  埼玉
  千葉
  東京
  神奈川
  新潟
  富山
  石川
  福井
  山梨
  長野
  岐阜
  静岡
  愛知
  三重
  滋賀
  京都
  大阪
  兵庫
  奈良
  和歌山
  鳥取
  島根
  岡山
  広島
  山口
  徳島
  香川
  愛媛
  高知
  福岡
  佐賀
  長崎
  熊本
  大分
  宮崎
  鹿児島
  沖縄
  韓国
  中国
  タイ
  イギリス
  ドイツ
  スイス
  フランス
  ベルギー
  オランダ
  スウェーデン
  ノルウェー
  アメリカ
この図書・雑誌をさがす
注記
参考文献: p146-147
内容説明・目次
内容説明
本書は、計算の複雑さの理論が一体どのような現象を解明しようとしているのか、そしてどのような結果が得られつつあるのかを、できるだけコンパクトに紹介することを目標とした。
目次
- 1 Turing機械とその基本的性質(決定性Turing機械;Turing機械の計算の複雑さ;Turing機械のシミュレーション;非決定性Turing機械;決定性Turing機械による非決定性Turing機械のシミュレーション;集合のいろいろなクラス)
- 2 万能Turing機械とその応用(万能Turing機械;構成可能関数;分離定理;padding法;還元可能性;完全集合とその存在完全集合の応用)
- 3 NP完全な問題(論理式の充足可能性問題;いくつかのNP完全集合;正規表現に関する完全問題)
- 4 NPの構造(NPの重要性;NP完全集合のp同値性;疎なNP完全集合;NP完全でない集合;P=NP?問題の相対化;ランダムなオラクルによる相対化;多項式時間階層)
「BOOKデータベース」 より