为什么经常需要在Savitch定理中进行空间构造性？
https://cs.stackexchange.com/questions/11168
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
当陈述了Savitch的著名定理时，人们经常看到$ s（n）$是空间可构建的要求（有趣的是，Wikipedia省略了）。我的简单问题是：我们为什么需要这个？我了解$ s（n）$在$ omega（ log n）$中的要求，这可以从证明中明确。但是，到目前为止，没有证据表明我明确地使用了$ s（n）$是可以构建空间的。
我的解释：为了调用步骤到达（或路径或任何您想称呼的路径），最后一个参数需要“拼写”，并且为了不离开我们的S（N）空间范围，以进行一个呼叫，我们绝对不需要超过$ s（n）$空间来写下它。
解决方案
我相信您的解释是正确的。 ST-REACH子例程将$（S，T， Ell）$作为输入，并发现$ s $ by $ ell $ steps是否可以从$ s $达到$ t $。 $ s $和$ t $将是初始配置和最终配置，$ ell = 2^{o（s（n））} $，上限在不同配置的数量上。
为了设置$ ell $，一个人需要能够计算$ s（n）$（或更确切地说，$ 2^{o（s（n））} $）。如果此过程需要超过$ O（s^2（n））$空间，则整个机器的空间将超过允许的空间。由于对ST-RECH的递归电话，甚至可能有其他可能的原因？
其他提示
在第2章中，Dexter Kozen的计算教科书理论很好地阐述了这一点。
Savitch的定理（他的论文中的定理1）说：如果$ s（n） ge log n $，则$ text {nspace}（s（n）） subseteq text {dspace}（s（n）^ 2）$。空间构造性似乎通常是在证明中假定的，但是可以通过使用固定空间绑定重新启动搜索来消除此要求，该搜索可以随着每次尝试而增加。
混乱也许是因为 原始Savitch纸 主要是要研究$ text {nspace}（s（n）） not subseteq text {dspace}（s（n））$。因此，由于本文的以下观察结果，它在空间结构函数上花费了很多精力：
自然要问是否有任何存储函数的确定性和非确定性复杂性类别相等。答案是由Manuel Blum给出的，是“是”。 Blum表明，有任意的存储函数l（n），因此在确定性存储l（n）中接受了一个集合，并且只有在非确定存储l（n）中被接受。但是，这些函数l（n）并不是“行为良好”，定理3不适用于它们。
（在这里，“行为良好”是指空间结构的功能，称为 可衡量 由Savitch。）
