$ m $が有限ステップで入力$ W $を停止しても$ NHALT $の$ NHALT $

Question

言語がある場合

$ NHALT={; $ $ m $ 停止入力 $ w $ $ n $ 手順 $$

この言語は、 $ halt $ が未定であるのと同じ方法でも未定ですか？もしそうなら、 $ nhalt \ notin p $ 、right？

Answer 1

この言語は明らかに決定でき、 $ m $ をエミュレートするだけで、$ w $ で$ w $ を扱い、それを参照してください。 $ n $ ステップまたはnot ...

現在、 $ nhalt \ in p $ または $ nhalt \ notin p $ かどうかに。 $ n $ の長さは、その "value"の対数です（ $ \ sigma $ "ここで単項ではありません）。したがって、私たちがエミュレートする必要があるステップの数は、そのサイズで指数関数的になるでしょう！私はそのための多項式の時間アルゴリズムを見ていないので、私はおそらくP ではないと仮定していると仮定します。しかし、私はそれが事実である可能性があるのかを直感を与えただけである）ことを証明していません。> $ \ mathcal {np-complete} $ ？）