08/07/11 20:29:03
NP問題の題材はSATとランダムウォーク。
これにするとしよう。
68:1
08/07/12 07:38:05
さすがにNPは難攻不落の要塞であるな。
P=NPになるなんてことがいかにありそうでないか、以前より強く感じられるようになったしだいだ。
ところでグレイコードというものがあるが、何かの足しにならないだろうか。
69:１３２人目の素数さん
08/07/12 16:15:07
妄想語ってないで、真面目にランダム性の本でも読めばいいのに。
ランダム性の研究は現在も活発に研究されてるし、いくらでも専門書の類はあるんだがな。
本を読まないまでも、
Kolmogorov Complexity
Martin-lof random
とかのワードを検索してみたらどうだろう。
んで、>>1のことは確かに大昔に証明されている事実だ。
70:１３２人目の素数さん
08/07/12 16:30:42
>>12
お、このアイデアを自分で思いついたなら大したもんだ。
実際、ランダム性の一種で、こういう風に定式化するものもあるぞ。
（正確には、マルチンゲールを使って定義する）
チャイティンのオメガ（Chaitin's Omega）とか、>>1は興味ありそうだ。
検索してみれば、面白いかもしれないよ。
あと、スレの後半は妄想が入り込んで、でたらめな発言になっているから、
>>1にはちゃんとした本を読んでもらって、軌道修正してもらいたいところ。
71:1
08/07/12 17:39:47
1だ。
妄想こそ真理への原動力なのだ。
だが、先人に学ぶことは大事だ。
これは車の両輪だ。
とりあえず、Kolmogorov Complexityは検索してみる。
チャイティンという人も少しは知ってるが、詳しく知ってるわけではない。これも調べてみる。
ありがとう。
確かに電波なレスもしたが、あの辺のことは
「宇宙を計算機に見立てて物事を考えるとそういう発想が出てくる」
とだけいっておく。俺なりに根拠があるのだ。すまない。
しかし、完全否定の罵声しか来ないと思ってたのに、部分的であれ認められるレスが付くとは。
やべ、マジ泣きそうｗ
72:1
08/07/13 18:20:07
1だ。
とりあえず、チャイティンの数学の限界という本を買ってきた。
黒くて薄い奴だ。
まだ全部読んでないが、なるほど俺の欲しかったことが沢山書いてある。
正直に告白すれば、俺は勉強は嫌々やるタイプの人間なんだが…
チャイティンのような天才の長年の研究の成果のエッセンスを
本という形でただ同然で得られるとはありがたいことである。
ところでNP問題について考えていたんだが、NP問題は素因数分解の拡張版であるという解釈もできる。
実際、素因数分解はNPの一種だ。
素因数分解は掛け算と素数でもって全ての整数を表すという発想だが、実数についても同じことが出来ないだろうか。
実数における掛け算に対応する何かと素数に対応する何かを定義し、全ての実数を表す。
それができたらNP問題を考察するためのインスピレーションが得られるのではないかとおもった。
ところでNP問題に対して対角線論法は無力であるという結果があるらしい。
であれば、俺はNP問題に対して有効な武器を全くもっていないということだ。
NP問題はひとまず保留にしよう。
とりあえず、素因数分解について調べようかと思っている。
量子コンピュータなんか面白そう。
73:１３２人目の素数さん
08/07/13 20:53:39
NP とランダムの関係を知りたかったら、ランダムオラクル仮説と
PCP(probabilistically checkable proof) 関係を調べてみたら？
74:1
08/07/14 20:20:31
１だ。
>>73
了解。
調べてみる。
THX。
しかしTODOがちょっとづつ溜まってきてしまったな。
さてどうするか。
まあ、マイペースでやるしかあるまい。
75:1
08/07/14 21:16:37
1だ。
WikiのPCPのページを見てみたが、いまいち心に響くものがないのはなぜだ？
俺が悪いのか、Wikiが悪いのか、PCPが悪いのか。
俺は神託機械の内側を見たいのに、PCPは神託機械の外側をみているからか？
外側からどう見えるかは内側を推測するヒントを与えてくれるはずなんだが…。
いまいち、ピンとこないのだ。
PCPの重要性が低いということはあるまい。
俺が悪いと思うのも癪だ。
Wikiが悪いということにして、別のページを探すとしよう。
76:１
08/07/16 19:29:19
１だ。
>>73
すまないがPCPとランダムオラクル仮説について、
詳しく書かれたサイトか書籍を教えてもらえないだろうか。
できれば日本語のやつで。
俺は検索能力が低いのでろくなサイトが見つからない。orz
77:１３２人目の素数さん
08/08/23 23:46:43
最後まで読んじまった。時間を返せ。
78:１３２人目の素数さん
08/10/26 11:59:54
509
79:１３２人目の素数さん
08/11/27 01:00:30
うるさい。
80:1
08/12/17 18:19:01
１だ。
このスレはこのままひっそりとdat落ちさせるつもりだったが、やりたいことが一個出来たので再利用させてもらう。
とりあえず、ｽﾚﾘﾝｸ(math板) の427を見てくれ。
81:１
08/12/17 18:22:34
告白すると、あの427は俺だ。
残念ながらわかってる奴から見ればあれは真の乱数とは呼べないものだということだ。
てことであれは擬似乱数の一種になる。
じゃあ、擬似乱数としてあれを評価した場合、他の擬似乱数と比べてどうなの？てのが気になる。
82:1
08/12/17 18:26:15
向こうのスレが１０００行きそうなので転載。
次のような非常に制限の強いプログラム言語X_1を考える。
1.使用できるデータ型（変数、定数とも）はC言語で言うところのunsigned charのみである。
2.使用できる演算は代入、足し算、引き算、論理演算(AND,OR,NOT,XOR,右シフト、左シフト)のみである。
3.if,while,goto,関数呼び出し等の制御構造は一切なし。プログラムは上から下へ順番に実行されるのみである。
4.unsigned char型の変数を使うことが出来る。個数に制限はない。
5.一ステップで代入一回、演算一回行うことが出来る。つまり１ステップは以下のどれか。
a=b;
a=~b;
a=b+c;
a=b-c;
a=b&c;
a=b|c;
a=b^c;
a=b<<c;
a=b>>c;
(※単項の-は禁止）
6.プログラムの終わりに次のような値を返す文を入れる。
return a;
この値をプログラムの値と呼ぶ。
7.プログラム中で使用できる定数は0x01のみである。
問題1
プログラム言語Pにおいてプログラムの値がaになるもので
最小ステップのプログラムを、Pにおけるaを返すエレガントなプログラムと呼ぶ。
0～255についてそれぞれその値を返すX_1におけるエレガントなプログラムを一つ挙げよ。
問題2
プログラム言語X_1に対してプログラム中で使用できる定数を0x01では無く、他の値aに変えたものをプログラム言語X_aと呼ぶ。
また、エレガントなプログラムのステップ数が最も大きくなるような値をそのプログラム言語の最悪の値と呼ぶ。
プログラム言語X_0～X_255の内、最悪の値に対するエレガントなプログラムのステップ数が最も小さくなるプログラム言語はどれか。
83:１３２人目の素数さん
08/12/17 20:01:26
良スレ
84:1
08/12/17 22:28:39
とりあえず、データがなければ何も論じられないな。
できればunsigned shortのデータが欲しいところだ。
まずは自力でunsigned charの場合を解くか。
85:１３２人目の素数さん
08/12/18 13:58:25
真のランダムとは、数値の表現が自然数とか、そんなものは関係ないよ>>1
たとえ「０と１と２」の３パターンしかなかったとしても、それは然り、
出現確率が歪んでいたとしても、それも然り。
一様であるとか、すべての状態に変化しえるとか、それは人が決めた
扱いやすさという意味で描くランダムにすぎないだろう。
前の出現と、後の出現の値に因果関係が無い、そして将来の値も同じ、
予測不可能で何かを基準として値を生むということではないものがランダムでしょう。
秩序が無いという意味で、どのような高次の捉え方であっても規則性を見つける
ことが不可能な挙動をする何かですよ。
故にランダムは>>1のいう結論と同じで無意味。
意味があるものは人が扱いやすいこと、
扱う対象の秩序と、乱数の結果は無関係であること。（つまり秩序や周期があっても問題ない）
予測できても問題はない。前の値から算出されても問題はない。
しかし、マクロ的な流れでは完全に近い乱数であってもミクロ、つまり部分的な
時間であっても周期性が見られるようなものは乱数としては好ましくない。
似た値が近い状態で連続するのはランダムでは許されるが人が好む乱数では
好ましくない。
>>1
真の乱数ではなく、擬似乱数の必要条件としての結論を出してくれ。
86:1
08/12/18 20:24:07
1だ
>>85からは、なんていうのかな、かなりの量の人生のリソースを
乱数の探求に突っ込んだ人間、そんな雰囲気を感じるといったら言い過ぎか？
とりあえず告白するんだが俺が興味があるのは物事の複雑性を測る尺度だ。
どうやら、ランダムはこれに深くかかわってるらしい。
役に立つ擬似乱数を探すとかはあんまり興味ないんだ。
もうちょっと勉強が進めば実はつながってるのかもしれないが。
87:１３２人目の素数さん
08/12/18 21:36:42
>>86
複雑度を測るのなら、オカルトをお勧め。
オカルトの本質にはそれがある。まあ君程度が覗けるのは表面的な
オカルトだけだろうけどね。