if $ mathrm {ntime}（n^{100}） subseteq mathrm {dtime}（n^{1000}）$ then $ mathrm {p} = mathrm {np} $ $

Question

以下を証明することであなたの助けが本当に欲しいです。

$ mathrm {ntime}（n^{100}） subseteq mathrm {dtime}（n^{1000}）$ then $ mathrm {p} = mathrm {np} $。

ここでは、$ mathrm {ntime}（n^{100}）$は、$ o（n^{100}）$および$ mathrm {dtimeの多項式時間で非決定的チューリングマシンによって決定できるすべての言語のクラスです。 }（n^{1000}）$は、$ o（n^{1000}）$の多項式時間で決定論的チューリングマシンによって決定できるすべての言語のクラスです。

何かヘルプ/提案はありますか？

Answer 1

これがパディングを使用したソリューションです。 $ l in mathrm {ntime}（n^{1000}）$を仮定します。新しい言語を定義します$ l '= {x0^{| x |^{10} - | x |}：x in l } $。各$ x in l $は、長さ$ | y |のl '$ in l' $の$ y に対応しています。 = | x | +（| x |^{10} - | x |）= | x |^{10} $。したがって、非決定的時間で$ y in l '$ | x |^{1000} = | y |^{100} $、ie $ l' in mathrm {ntime}（n^{ 100}） Subseteq Mathrm {dtime}（n^{1000}）$。 $ x in l $を決定するために、$ y = x0^{x^{10} - | x |} $を形成し、$ | y |^{1000} = | x |^{10000} $を実行するかどうか - $ l '$の時間決定論的アルゴリズム。 $ l in mathrm {dtime}（n^{10000}）$であると結論付けます。

Answer 2

問題を2つの部分に分割します。

1. $ mathsf {np} $ - $ mathsf {ntime}（n^{1000}）$に完全な言語があります。
2. $ mathsf {np} $ - 完全な言語が$ mathsf {dtime}（n^{1000}） subset mathsf {p} $ then $ mathsf {p} = mathsf {np} $にある場合

Answer 3

これは、NP不完全性の定義のほぼ些細な結果です。 NPのいずれかの言語が多項式時間で解決可能である場合（これは前提によって主張されています）、それらはすべてそうです。これを見る別の方法は、 NPの完全性のためのクックの定理 これにより、すべてのNP完全な言語が、SATを含む言語の認識と、非決定的チューリングマシンのSATへの変換に削減されます。