計算量(PやNP)について

質問

ネット上で計算量理論に関する説明を読んでいますが、いまいち理解ができません。

例えば、木の形で表せれる問題で、一つのノードに対する子がN個(定数)あり、深さX(未知、変数)に答えがある場合、計算量は
N^X(NのX乗)
になると思います。

N^Xは計算量のクラス(NP困難やNP完全等)でいうと何に属するのでしょうか？

回答No.5

Tacosan · ベストアンサー

ああ, 「計算量」っていうと普通は時間計算量を指すけど, 「使うメモリ量」を指標とする「領域計算量」というのもあります.
いずれにしても「計算が終了するまでに必要な時間なりメモリ量なり」で定義するので, それが分からないと「分からない」以上は答えられないです.

お礼

1つ1つの質問に丁寧に答えていただきありがとうございます。
お陰で凄く勉強になりました！
質問の答えは、自分の中でも「この場合は分からない」に結論できました。
ありがとうございます。

回答No.4

Tacosan

それは.... X と「入力の大きさ」の関係がわからない以上なんとも言えない.
例えば X が入力の大きさの対数になるなら全体として多項式になっちゃうし, 入力の大きさに対して線形なら全体として指数になる.
だから, 「これなら絶対にあっている」という表現をしようとすると「(多項式時間帰着に関する) P困難」としか言いようがないんだけど, これは事実上何も言っていないに等しい.

補足

そうですか・・・ありがとうございます。
Xは入力の大きさが大きくなるほど大きくなる傾向ですが、やはり答えの長さは分からず、未定です。(一回で答えが出る場合もあれば、深さが200になる場合もあります。)
この場合、計算量は定義できないということでよいのですね？

回答No.3

Tacosan

それは全然情報が足りない.
例えば, 「探索木」といってもどれだけ調べなきゃならないのかで全く違いますよね. 「あるノードでその子ノードを全部調べたら, そのうち 1つの子ノードに進めば十分」ということだと, 計算量はべきになりません.
さらに, X が何に依存するのかってのも問題になりうる. X が入力サイズに多項式的に依存して O(N^X) の時間計算量なら多分 NP完全くらいですむけど, 入力サイズに対し指数的になるとまた別のクラス (Σ2 とか) になるかもしれん.
とはいえ, PSPACE を超えるような驚異的に難しい問題ってあんまりないんだけどね.

補足

あるノードでその子ノードを全て調べた場合、その子ノードでも全て調べなければならないとします。
幅優先探索で、その深さの全てのノードを調べます。

Xは、どう依存するかは難しいです。
深さは未知で、どの深さで解が見つかり探索が終了するかは解が見つかるまで分かりません。

情報不足申し訳ないです。

回答No.2

Tacosan

「木の形で表せれる」というのは, 何が「木の形で表せれる」のですか?
しかし「表せれる」って違和感あるなぁ.

補足

探索木のことです。
最初に一つの状態(ノード)があって、そこからN個の状態に分かれていきます。
それらN個のノードそれぞれが更にN個のノードに分かれていきます。

文章下手で申し訳ないです。
木の部分は読み飛ばしてくれて構いません。
要は、N^Xがどのクラスに属するか？ということが知りたいです。

回答No.1

koko_u_u

>ネット上で計算量理論に関する説明を読んでいますが、いまいち理解ができません。

適当に参考書を買ってください。

補足

参考書も少し漁りましたが短時間ではやはりわかりませんでした。(そりゃそうですね
将来的には計算量理論を一から勉強するつもりですが、今はN^Xがどのクラスに属するかだけ知りたいです。
よろしくお願いします。