561
个编辑
更改
跳到导航
跳到搜索
第935行：
第935行： − 更准确地说，时间谱系理论声称+ 第949行：
第949行： − 空间层次定理指出+ 第955行：
第955行： − 大(f (n) big)子集数学大(f (n) big (f (n) sdot log (f (n) big) </math > 。 第963行：
第962行： − 时间和空间层次定理是复杂类分离结果的基础。例如，时间谱系理论告诉我们 p 严格包含在 EXPTIME，而空间层次定理告诉我们 l 严格包含在 PSPACE。+ − −
→Hierarchy theorems层次定理
More precisely, the time hierarchy theorem states that
More precisely, the time hierarchy theorem states that
更准确地说，'''<font color="#ff8000"> 时间层谱定理Time hierarchy theorem</font>'''声称
:<math>\mathsf{DTIME}\big(f(n) \big) \subsetneq \mathsf{DTIME} \big(f(n) \sdot \log^{2}(f(n)) \big)</math>.
:<math>\mathsf{DTIME}\big(f(n) \big) \subsetneq \mathsf{DTIME} \big(f(n) \sdot \log^{2}(f(n)) \big)</math>.
The space hierarchy theorem states that
The space hierarchy theorem states that
'''<font color="#ff8000"> 空间层谱定理Space hierarchy theorem</font>'''指出
:<math>\mathsf{DSPACE}\big(f(n)\big) \subsetneq \mathsf{DSPACE} \big(f(n) \sdot \log(f(n)) \big)</math>.
:<math>\mathsf{DSPACE}\big(f(n)\big) \subsetneq \mathsf{DSPACE} \big(f(n) \sdot \log(f(n)) \big)</math>.
<math>\mathsf{DSPACE}\big(f(n)\big) \subsetneq \mathsf{DSPACE} \big(f(n) \sdot \log(f(n)) \big)</math>.
<math>\mathsf{DSPACE}\big(f(n)\big) \subsetneq \mathsf{DSPACE} \big(f(n) \sdot \log(f(n)) \big)</math>.
The time and space hierarchy theorems form the basis for most separation results of complexity classes. For instance, the time hierarchy theorem tells us that P is strictly contained in EXPTIME, and the space hierarchy theorem tells us that L is strictly contained in PSPACE.
The time and space hierarchy theorems form the basis for most separation results of complexity classes. For instance, the time hierarchy theorem tells us that P is strictly contained in EXPTIME, and the space hierarchy theorem tells us that L is strictly contained in PSPACE.
时间和空间层谱定理构成了大多数复杂类分离结果的基础。例如，时间层谱定理告诉我们P严格包含在EXPTIME中，而空间层谱定理告诉我们L严格包含在PSPACE中。
===Reduction约简===
===Reduction约简===