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

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

山口人生 〜超無職、失意の実家帰り〜 Part20

854 :132人目の素数さん:2005/05/10(火) 10:56:52
(1) wが正解の場合、多項式時間で受理する決定性TM M が存在する場合、L(M) は P 
(2) wが正解の場合、多項式時間で受理し、wが不正解の場合多項式時間で拒否する決定性TM M が存在する場合、L(M) は P

山口氏は、(1)と(2) が本質的に違うものを指していると思っている。
(1) では、wが不正解の場合 TM が停止しないかもしれないという理由で。
もちろん、wが不正解の場合に単に無限ループに陥る TM を作ることは可能である。
問われているのは、(1)の定義を満たす TM M1 があったとき、(2)を満たす TM M2 を
作ることが出来るかどうかだけである。
P,EXP に関しては、(1)の定義から(2)が導けることが証明された。
(全然難しく無いよ。山口氏にとっては難しいかもしれないが)
NP に関してはまだ証明されていないというだけの話である。

P,EXP に関して、教科書には(1)も(2)もかかれたりする。
正式な教科書は (1)を採用するだろうが、暗号理論や圧縮などの応用本で「計算量」を予備知識
としてしか触らない場合には(2)を採用することもあるだろうと思われる。

山口氏は、英語の教科書には違うことが書いていると指摘しているが、ありえない。
(そもそも彼の英語力は >>849 に指摘されている程度しかない。)

例えて言えば・・群を定義するときに、(1)で定義しても(2)で定義しても、本質的に変らない。
(1) 左単位元、右単位元、左逆元 の存在
(2) 左単位元、右単位元、左逆元、右逆元の存在
数学としては、(1)が普通かもしれないが情報工学本は(2)で定義するほうが多い。
(1)から(2)が容易に導けるのだから、定義としては(1)で十分で、(2)は冗長である。
しかし、(2)で定義したほうが再読するのに便利であるから(知っていながら)
あえて(2)で書く本がたまたま多いのである。
それがわからない人にとっては、別のものを指しているように見えてしまう。


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

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