证明如果$ mathrm {ntime}（n^{100}） subseteq mathrm {dtime}（n^{1000}）$然后$ mathrm {p} = mathrm {np mathrm {np} $

Question

我真的很喜欢您的帮助以证明以下内容。

如果$ mathrm {ntime}（n^{100}） subseteq mathrm {dtime}（n^{1000}）$然后$ mathrm {p} = mathrm {np {np} $。

在这里，$ mathrm {ntime}（n^{100}）$是所有语言的类}（n^{1000}）$是所有语言的类，可以由$ O（n^{{1000}）$的多项式时间确定性图灵计算机决定。

有帮助/建议吗？

Answer 1

这是使用填充的解决方案。假设$ l in mathrm {ntime}（n^{1000}）$。定义一种新语言$ l'= {x0^{| x |^{10} - | x |}：x in l } $。 l $中的每个$ x 对应于length $ | y |的l'$中的某些$ y | = | x | +（| x |^{10} - | x |）= | x |^{10} $。因此，我们可以决定是否在非确定时间$ | y $ in l'$中$ | x |^{1000} = | y |^{100} $，ie $ l' in mathrm {ntime}（ntime}（ntime}）（n^{ 100}） subseteq mathrm {dtime}（n^{1000}）$。为了确定$ x in L $，$ y = x0^{x^{10} - | x |} $并运行$ | y |^{1000} = | x | x |^{10000} $ - $ l'$的时间确定性算法。我们得出结论，$ l in mathrm {dtime}（n^{10000}）$。

Answer 2

将问题分为两个部分：

1. 有一个$ mathsf {np} $ - $ mathsf {ntime}（n^{1000}）$中的完整语言。
2. 如果$ mathsf {np} $ - 完整的语言在$ mathsf {dtime}（n^{1000}） subset subset mathsf {p} $然后$ mathsf {p} = mathsf {np} $。

Answer 3

这是NP完整性定义的几乎微不足道的结果。如果NP中的任何语言在多项式时间（前提下主张）可以解决，那么它们都是。查看这一点的另一种方法是看 库克定理NP完整性 这将所有NP完整的语言都减少到涉及SAT语言的识别以及非确定的Turing Machine转换为SAT的语言。