雑談はここに書け!【38】
■ このスレッドは過去ログ倉庫に格納されています
008043
2010/09/25(土) 15:01:43"You're not registered to endorse for math.MG"とのことです。
色々と条件満たしていないので、endorseはムリそうですね。
投稿自体はendorse無しで終了できたかと記憶しています。
endorseは投稿終わった後にpaper passwordがeメールで
送付されるので、それを使って行ったかと思います。
>78
OKです。このようなTMは判定機と呼ばれるタイプのTMで、
かなり多くのP&NP問題が判定機で判定可能です。
例えばSATなどは典型ですね。論理式の真理値割当は
有限の数しか存在しないので、マトモなTMならばいつかは
計算が終了します。
「与えられたプログラムと、与えられた入力に対して、そのプログラムが計算を終えて止まるか、
あるいはいつまで経っても計算し続けて止まらないかを判定するアルゴリズムは存在しない。」
というのはNP問題に属しないので、P≠NPを考えるときは除外して問題ないです。
■ このスレッドは過去ログ倉庫に格納されています