山口人生 〜著者へのコメント:特になし〜 Part23
■ このスレッドは過去ログ倉庫に格納されています
0457132人目の素数さん
2005/07/19(火) 17:38:32あのねえ、NPの定義は「あるTMが存在して、正解入力の場合は、いくつ
あるやも知れぬrejectの枝を乗り越えてacceptの枝を見い出す」という
作業全体を、「多項式時間で」完遂する、というものなんですよ。
「多項式時間で」という修飾が、文章のどこに掛かっているのか、ちゃん
と理解できてますか?
だから、上記<1>型も<2>型も、そのようなTMが存在するというだけでは、
定義にも何もなってないでしょ? 誤魔化さないで、ちゃんと答えて頂き
たいのですがね、例えば大先生のおっしゃる<1>型TMが存在する場合、
(1) 「多項式時間で」acceptされた場合、その入力を正解入力と見なすの
でしょうか、それとも不正解入力と見なすのでしょうか、あるいはその段階
では判断を保留するのでしょうか
(2) 「多項式時間で」rejectされた場合、その入力を正解入力と見なすの
でしょうか、それとも不正解入力と見なすのでしょうか、あるいはその段階
では判断を保留するのでしょうか
答えられないでしょ? 答えられる訳ないんです。だって、上記の馬鹿な
原稿は、そもそも定義になってないのですから。
・・・ここまで書いても、やっぱり理解できませんか?
■ このスレッドは過去ログ倉庫に格納されています