この問題はNP?(円周率πの10進展開中に3がx個連続して現れるか?)

以下のような判定問題があります。

<円周率中の3の連続出現>
入力: 正整数x
質問: 円周率を10進で展開した無限数列(3.14159...)に数字3がx個連続して並ぶ箇所があるか?

この問題はクラスNPに属するのでしょうか?

たとえば「証明」が与えられたとき、その正しさを入力サイズ(この場合はx?)の多項式時間で検証できればNPに属するわけですが、

この場合の「証明」とは円周率中の3がx個並んだ箇所を「ほら、i桁目からj(=i+x-1)桁目に3がx個並んでいるよ」と円周率を小数点以下j桁目まで書いて示すことなのか?
↓
そうだとしたら、その検証は円周率をj桁目まで適当な方法で計算することなのか?
↓
そうだとしたら、xの多項式時間で円周率をj桁目まで計算出来るか?
↓
計算コストはxとは独立なのでは?

などと考えるうちに分からなくなってしまいました。
どうぞよろしくお願いいたします。

No.3 回答者： masa2211 回答日時： 2010/04/10 08:05

いえ、この部分をどう解釈したらいいのかよくわかりません。

＞そうだとしたら、その検証は円周率をj桁目まで適当な方法で計算することなのか?
この部分について、円周率の再計算が必要なのか、円周率を既知として当該桁を示せばいいのかというのがよくわからない点。
言い換えれば、質問文の
＞円周率を10進で展開した無限数列(3.14159...)...
というのを、
・この無限数列が与えられていて、3333...があるかを探す
・この無限数列は不明なので計算が必要。
のどちらの意味にも解釈可能ということ。
私は前者寄りです。後者なら、すなおに
・円周率（10進）のｎ桁めの値の計算時間
とすればよいのを、わざわざヤヤコシイ書き方をしているため。

あと、16進の場合限定ですが、
＞そうだとしたら、その検証は円周率をj桁目まで適当な方法で計算することなのか?
は、誤り。
円周率のj桁目だけを計算すればよいわけで、それが可能なため。（ＢＢＰアルゴリズム）

この回答へのお礼

masa2211様

御教示をありがとうございます。
BBPアルゴリズムのことは知りませんでしたので勉強になりました。
また御礼が大変遅くなりましたことを深くお詫び申し上げます。

お礼日時：2012/05/19 12:18

No.2 回答者： Tacosan 回答日時： 2010/04/09 12:50

このように「『証明』を作ってそれを検証する」という方針では, 「NP に属する」ことは言えても「NP に属さない」ことは言えないと思います. つまり, 「他の方法ではできるかもしれない」といわれると困りますよね.

そういう場合には「明らかに NP には属さない問題」から帰着するという方針を取るんだけど.... どのクラスから持ってくればいいんだ? 2EXPTIME-完全な問題が必要か?
ちなみに, 今の問題の場合「入力サイズ」は「x の値そのもの」ではなく「x の値を表すために必要な桁数」です. そして, 「円周率を j桁目」まで計算するために必要な時間は少なくとも「j の値に対する多項式」になります (「j桁の数の加算」ですら j の値に比例する時間がかかる). 従って当然に x の値に依存し, かつ「x の桁数」に対しては少なくとも指数時間必要です.

この回答へのお礼

Tacosan様

御教示をありがとうございます。参考になりました。
また御礼が大変遅れましたことを深くお詫び申し上げます。

お礼日時：2012/05/19 12:08

No.1 回答者： masa2211 回答日時： 2010/04/09 00:35

円周率の数値があらかじめ無制限にわかっていたとして、それでも計算量は指数関数的に増加します。

理由：かなり大雑把な計算ですが、円周率の各桁は0～9がランダムに現れると近似して
Ｘ＝1　3が現れればよい　→平均　10桁に1つ
Ｘ＝2　33が　　〃　　　→平均　100桁に1つ
Ｘ＝3　333が　　〃　　　→平均　1000桁に1つ
n桁の文字列からm桁の文字を探索するのにかかる計算量は、Ｏ（ｎ）。
（ｎ＞＞ｍとして。）
よって、Ｘが1増えるごとに計算量10倍強なので、指数オーダーであり、多項式時間では計算できない。。

この回答へのお礼

masa2211様、ご投稿ありがとうございます。

ただ、私が知りたいのはこの問題がクラスPに属する(多項式時間で解ける)か否かではなく、クラスNPに属する(Non-deterministic Polynomial, 非決定性チューリングマシンを用いて多項式時間で解ける)か否かなのです。

お礼日時：2010/04/09 06:13