NP完全問題についての

NP完全問題についての質問です

（1）NP完全問題とは多項オーダーの計算量で解決可能な問題のクラスですか、
　　問題のサイズをｎとしたとき「ｎの階乗」，「２のｎ乗」オーダーとなる問題は
　　NP完全問題のうちには入らない？

（2）PSPACE完全問題とは何か（NP完全問題はPSPACE問題に含まれる（？））

以上です．よろしくお願いします．

No.2 ベストアンサー 回答者： kobold 回答日時： 2006/01/06 11:14

> NP完全問題とは多項オーダーの計算量で解決可能な問題のクラスですか

何か誤解をされているようです
多項式オーダーの計算量で解決可能な問題はPで、
解かどうかの確認が多項式オーダーの計算量で解決可能な問題がNPです
更に他のNP問題に帰着できる場合NP完全と言います
PSPACEは計算に必要な空間(チューリングマシーンではテープ)の量が多項式オーダーというものです
PSPACEはNPに含まれます

この回答へのお礼

参考になりました
どうもありがとうございます．

お礼日時：2006/01/07 22:47

No.1 回答者： ojisan7 回答日時： 2006/01/03 19:01

Ｔuring機械の計算量理論は、抽象的な内容が中心となりますので、じっくりと時間を掛けて学び、理解を確実にしておくことが大切です。

（１）と（２）についてはオーマトンの教科書に記載されていますので、それを読んで下さい。先ず、大切なことは、ご自分で理解することだと思います。

少し、古い本ですが、以下の参考書を推薦します。

「オートマトンの理論」小林孝次郎、高橋正子　共著
　共立出版

です。読むのに結構、骨の折れる本？（特に、わたしの場合、理解度が低いので、そう思いました）ですが、内容は充実しています。