計算の複雑さ
Author(s)
Bibliographic Information
計算の複雑さ
(ソフトウェア講座 / 井上謙蔵, 中田育男, 志村正道編集委員, 33)
昭晃堂, 1988.5
- Other Title
-
Theory of computational complexity
- Title Transcription
-
ケイサン ノ フクザツサ
Available at 147 libraries
  Aomori
  Iwate
  Miyagi
  Akita
  Yamagata
  Fukushima
  Ibaraki
  Tochigi
  Gunma
  Saitama
  Chiba
  Tokyo
  Kanagawa
  Niigata
  Toyama
  Ishikawa
  Fukui
  Yamanashi
  Nagano
  Gifu
  Shizuoka
  Aichi
  Mie
  Shiga
  Kyoto
  Osaka
  Hyogo
  Nara
  Wakayama
  Tottori
  Shimane
  Okayama
  Hiroshima
  Yamaguchi
  Tokushima
  Kagawa
  Ehime
  Kochi
  Fukuoka
  Saga
  Nagasaki
  Kumamoto
  Oita
  Miyazaki
  Kagoshima
  Okinawa
  Korea
  China
  Thailand
  United Kingdom
  Germany
  Switzerland
  France
  Belgium
  Netherlands
  Sweden
  Norway
  United States of America
Search this Book/Journal
Note
参考文献: p146-147
Description and Table of Contents
Description
本書は、計算の複雑さの理論が一体どのような現象を解明しようとしているのか、そしてどのような結果が得られつつあるのかを、できるだけコンパクトに紹介することを目標とした。
Table of Contents
- 1 Turing機械とその基本的性質(決定性Turing機械;Turing機械の計算の複雑さ;Turing機械のシミュレーション;非決定性Turing機械;決定性Turing機械による非決定性Turing機械のシミュレーション;集合のいろいろなクラス)
- 2 万能Turing機械とその応用(万能Turing機械;構成可能関数;分離定理;padding法;還元可能性;完全集合とその存在完全集合の応用)
- 3 NP完全な問題(論理式の充足可能性問題;いくつかのNP完全集合;正規表現に関する完全問題)
- 4 NPの構造(NPの重要性;NP完全集合のp同値性;疎なNP完全集合;NP完全でない集合;P=NP?問題の相対化;ランダムなオラクルによる相対化;多項式時間階層)
by "BOOK database"