NP完全問題についての

質問

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

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

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

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

回答No.2

kobold · ベストアンサー

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

お礼

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

回答No.1

ojisan7

Ｔuring機械の計算量理論は、抽象的な内容が中心となりますので、じっくりと時間を掛けて学び、理解を確実にしておくことが大切です。（１）と（２）についてはオーマトンの教科書に記載されていますので、それを読んで下さい。先ず、大切なことは、ご自分で理解することだと思います。

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

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

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