計算の複雑さ

Author(s)

• 小林, 孝次郎 コバヤシ, コウジロウ

Bibliographic Information

計算の複雑さ

小林孝次郎著

（ソフトウェア講座 / 井上謙蔵, 中田育男, 志村正道編集委員, 33）

昭晃堂, 1988.5

Other Title

Theory of computational complexity

Title Transcription

ケイサン ノ フクザツサ

Note

参考文献: p146-147

Description and Table of Contents

Description

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

Table of Contents

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

by "BOOK database"

Details

• NCID: BN02228129
• ISBN:
  • 4785635339
• Country Code: ja
• Title Language Code: jpn
• Text Language Code: jpn
• Place of Publication: 東京
• Pages/Volumes: iv, 2, 155p
• Size: 22cm
• Classification:
  • NDC8 : 007.64
  • NDC7 : 418.6
  • NDLC : M151
• Subject Headings:
  • BSH : 電子計算機 -- プログラミング
  • NDLSH : アルゴリズム
• Parent Bibliography ID:
  • BN0005766X