• ベストアンサー

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

ネット上で計算量理論に関する説明を読んでいますが、いまいち理解ができません。 例えば、木の形で表せれる問題で、一つのノードに対する子がN個(定数)あり、深さX(未知、変数)に答えがある場合、計算量は N^X(NのX乗) になると思います。 N^Xは計算量のクラス(NP困難やNP完全等)でいうと何に属するのでしょうか？

質問者が選んだベストアンサー

  • ベストアンサー
  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.5

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

yaruotto
質問者

お礼

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

その他の回答 (4)

  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.4

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

yaruotto
質問者

補足

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

  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.3

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

yaruotto
質問者

補足

あるノードでその子ノードを全て調べた場合、その子ノードでも全て調べなければならないとします。 幅優先探索で、その深さの全てのノードを調べます。 Xは、どう依存するかは難しいです。 深さは未知で、どの深さで解が見つかり探索が終了するかは解が見つかるまで分かりません。 情報不足申し訳ないです。

  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.2

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

yaruotto
質問者

補足

探索木のことです。 最初に一つの状態(ノード)があって、そこからN個の状態に分かれていきます。 それらN個のノードそれぞれが更にN個のノードに分かれていきます。 文章下手で申し訳ないです。 木の部分は読み飛ばしてくれて構いません。 要は、N^Xがどのクラスに属するか？ということが知りたいです。

  • koko_u_u
  • ベストアンサー率18% (216/1139)
回答No.1

>ネット上で計算量理論に関する説明を読んでいますが、いまいち理解ができません。 適当に参考書を買ってください。

yaruotto
質問者

補足

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

  1. カテゴリ
  2. 学問・教育
  3. 数学・算数

関連するQ&A

  • NP完全問題についての

    NP完全問題についての質問です （1）NP完全問題とは多項オーダーの計算量で解決可能な問題のクラスですか、 　　問題のサイズをｎとしたとき「ｎの階乗」，「２のｎ乗」オーダーとなる問題は 　　NP完全問題のうちには入らない？ （2）PSPACE完全問題とは何か（NP完全問題はPSPACE問題に含まれる（？）） 以上です．よろしくお願いします．

  • co-NPについて

    計算の複雑性理論について勉強しているのですが、ある問題がクラスco-NPに属すことがわかったんのですが、そもそもco-NPに属する問題はどの程度複雑といえるのでしょうか？お願いします。

  • 計算量の少ないｎ乗根の求め方

    現在C++であるクラスのインスタンスaのN乗根を求める関数を作成中なのですが、どうしても実行時間が長くなってしまいます。 現在ニュートン法に則って X(m+1)=((N-1)(Xm)^N+a)/(N*(Xm)^(N-1)) という漸化式を回して変化量が一定値以下になったら終了という関数なのですが、 値によっては累乗計算のところで時間を大幅にロスしてしまうようです。 原因としては累乗計算が同じ数をN回掛けるという単純な仕組みなため、 Nが大きすぎるとループがなかなか終わらないということがわかっています。 もしご存知であれば 1.極力累乗計算を使わないN乗根の求め方 2.計算量の少ない累乗計算の仕方 のどちらかを教えていただけないでしょうか？ なお、クラスを使っている関係上powなどの既存の関数は使えません。 よろしくお願いいたします。

  • 偏微分方程式の数値計算について

    偏微分方程式の解の数値計算の仕方についての質問です。 例えば、偏微分方程式の解が以下のような形だったとします。 Ｔ(x,y)=Σ(A1n*x^n+A2n*x^(-n))*cos(ny) nは変数分離定数です。A1n,A2nが積分定数です。またn=1～∞とします。 今、あるxにおけるTとyの数値計算をするとします。 つまりxを定数として扱います。 そして、上式を条件に代入して解を求めるのですが、 n=3の場合の結果が欲しい場合は、 n=1,2,3のとき連立方程式をそれぞれで解いて、 数値結果は、 （n=1の結果）＋（n=2の結果）＋（n=3の結果） という考え方であってますか？ アドバイスをお願いします。 プログラムで数値計算をするのですがなかなかうまくいかずこまっています。

  • 【P≠NP予想】容疑者Ｘの献身を観たのですが

    容疑者Ｘの献身を観たのですが、 映画の一場面で「Ｐ≠ＮＰ問題」の話題が出てきました。 その中で、 「数学の問題について、自分で考えて答えを出すのと、他人から答えを聞いて、その答えが正しいかどうかを確認するのとではどちらが易しいか（難しいか）？ ただし、その問題には必ず答えが存在する。」 というセリフがありました。 恐らく、前者がクラスＰ、後者がクラスＮＰのことを表していると思われます。 しかし、「どちらが易しいか？（難しいか？）というのは、「Ｐ≠ＮＰ問題」の本質ではないような気がします。（Ｐの方がＮＰより解くのが大変ですよね・・） Ｐ≠ＮＰ問題の核心部分は、「Ｐ⊂ＮＰが成り立つかどうか？（ＮＰ⊂Ｐは自明）」ではないでしょうか？ 自分は映画を見ていて、「そんなの、他人から答えを聞いてその答えが正しいかどうかを確認する作業の方が、自分で答えを考え出すのより何百倍も簡単だろ！！」と思ってしまいました。 詳しい方解説お願いします！！！

  • 2進アルゴリズムの時間計算量

    ベキ乗計算を2進アルゴリズムで解いた場合の時間計算量を求める方法を教えてください。 x^nの時の時間計算量でn=2,3以外の時でn=2p,2p+1の時で場合わけして(pは整数)数学的帰納法で解いてあるのは見た事はあるのですが、どこからその仮定を持ってきたのか見当がつきません。 どうかお願いします。 n>3のときの時間計算量kは　k<=(2*log(n))-1 となっていました。

  • 再帰呼び出しの計算量

    再帰呼び出しを用いた関数の計算量を求める方法がわからないので質問させていただきます． xのn乗を再帰呼び出しを用いて求める関数に関して，計算量を求める問題なのですが，どのような方針で求めればよいのでしょうか？ int exponent(int x, int n) { 　　if(n == 0){ 　　　　return 1; 　　}else{ 　　　　return x * exponent(x, n-1); 　　} } exponentがn回呼ばれるからO(n)というのは間違いでしょうか？

  • 計算量について

    プログラムの計算量について質問です。計算量には時間計算量と空間計算量がありますが、そのうち空間計算量の概念がいまいち分かりません。アルゴリズムが必要とする記憶容量といっても漠然としててどのように求めたらいいのか分かりません。 例えばプログラムの基本構成が for(n回){ for(n回){ 処理 } } のようだったら時間計算量がO(n^2)というのはわかるんですが、この場合の空間計算量はどのようになりますか?

  • 二項分布の期待値の計算過程

    二項分布の期待値を計算しています。 https://mathtrain.jp/bin の中の E[X] = np Σ[k=1, n] n-1 C k-1 p^(k-1) q^(n-k) = np Σ[k=0, n-1] n-1 C k p^k q^(n-1-k) の計算過程を教えて下さい。 この計算の間に k=1 ⇒ k=0 n ⇒ n-1 が変わっています。 それらを一つずつ変更できますでしょうか？ 意味は半分わかっているつもりです。 k=1からnだったのが k=0からn-1になったので、 配列が一つズレた印象です。 二行目はn-1に括弧を付けると np Σ[k=0, n-1] n-1 C k p^k q^{(n-1)-k} だと思っています。 ではよろしくお願いします。

  • ソートの計算量などについて

    こんにちは ソートに関することの質問です。 １．バブルソートの計算量を出す式ですが Ｏ(n^2)=Ｏ(n-1)*Ｏ(n/2)*Ｏ(1)=Ｏ(n)*Ｏ(n)=Ｏ(n^2) で合っていますでしょうか？ ２．クイックソートの（平均）計算量が ｎlog n(底は２)になるのは、なぜなのかを わかりやすく教えて下さい。（できれば式も） ３．クイックソートが最も高速に実行されるのは、ピボットの要素が真中にある場合で、反対に最も効率が悪いのはピボットが端にある場合ですが、この理由をやさしい言葉で教えて下さい。 どなたか教えて下さい。 よろしくお願いします

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する