5ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

山口人生〜ストリートダンスの連中に絡まれるの巻 Part21

1 :132人目の素数さん:2005/05/11(水) 04:36:03
参拝先:大神帝山口大先生超教授のサイトIII
http://www.int2.info/news1.htm

前スレ:山口人生 〜超無職、失意の実家帰り〜 Part20
http://science3.2ch.net/test/read.cgi/math/1113806284/

過去スレ、関連スレは>>2-5あたりで。

143 :132人目の素数さん:2005/05/12(木) 09:34:31
>>142
用は、カウンタを作っておいて、規定のステップ数を見て止めるのだ。
ステップ数は、入力の長さを見て決める。

しかし、理解するには予備知識が要る。
例えば、2台のTM M1,M2 を並列実行させるような処理が1台のTM Mで可能
であることの証明とか、M1 と M2 が多項式時間で動作するなら、M も多項式
時間で停止するとか、簡単な補題をいくつか知っとく必要がある。


144 :132人目の素数さん:2005/05/12(木) 09:47:49
判りにくければこうだ。
Pに属する L を多項式時間で受理する TM Mがあるとする。
Mを改良して、以下のTM M’を作る。
「M’は、入力長さ n としたとき、s(n) ステップ経過したら何が何でも
停止する。」
s(n) は、正解入力で「受理停止」する時間より、長めに取っておきかつ
多項式時間であるようにする。
正解入力なら、必ず受理停止し、不正解入力なら、s(n) ステップ目で拒
否停止する。

M’を作る方法はかなり煩雑で、正確に短くは書きにくいので略。スマソ
これであなたは、ヤマジンを超えた。


290 KB
★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.04.00 2017/10/04 Walang Kapalit ★
FOX ★ DSO(Dynamic Shared Object)