>>14 神様
問題はまさにそこですね。
非決定性機械の reject は、それだけでは入力が不正解であることを
意味しないんですよ。先生の言うとおり。先生万歳。そこまでは。

実は、全部の枝が reject しない限り、不正解入力であると本当に知
ることはできないのですね。

だから、あてずっぽうに枝を進んで、accept にたどり着いたら w は
L の元だと誰もが自信を持っていえる。けれども、reject にたどり着
いた場合は 正解入力なのに当てが外れたのか、不正解入力だったのか
誰にもわからないんですよね。
山口先生の主張は、それじゃ不味いから何とかしようと言うことなんだ
よね？
でも、世間のNP は、「それでいいのだ」なんですよ。
山口先生が主張する、不正解も何とか確認すべきというのは、NP の
定義から外れるんです。だから皆、山口NP を独自概念として区別して
るんです。
不正解入力の場合、accept してはいけないというのは、アルゴリズム
設計者が、アルゴリズムを発表するときに証明をつけておけばいいだけ
です。
アルゴリズムに入力が与えられたあと、TM が多項式時間で不正解入力
と判定するなどということを、誰も求めていないのですよ。

ときどき、餓鬼の中に山口NPは定義が違うから無意味と主張するのがい
るけど、私はそうは思わない。P≠山口NP も、NP≠山口NP も、実は
証明に成功すればそれなりに重要な意味がある。
残念なことに、その間違った定義から出発した先生の証明は、さらにそ
の先でまた間違っているので、結論から言うとやっぱり無意味なんだけ
ど。