在空间复杂性中证明语言

Question

我想知道我是否有正确的直觉，我的答案是正确的。

我获得了一个函数$ f = {0，1 }^* rightarrow {0，1 }^* $在space $ o（ log n）$中可计算的$假设为每个$ x in {0，1 }^*$，$ f $是长度保存，$ | f（x）| = | x | $。

定义$$ l = left {x #y mid x，y in {0，1 }^*，| x | = | y |， text {and} f（x）= f（y） right } $$

我想证明{ sf dspace}（ log n）$中的$ l 。

如果我的直觉不正确，请纠正我。

我的解决方案是构建一台Turing机器的决定件$ M $。

$ m $带输入$ x $和$ y $，在输入$ x $和$ y $上运行函数$ f $，如果两个字符串的长度相等，则应接受，否则拒绝。

现在，图灵机以$ o（ log n）$运行通过函数为$ o（1）$，因此该语言是由$ o（ log n）$运行的图灵计算机可以决定的，并且仅占用space $ o（ log n）$。

Answer 1

这是一个粗略的想法，如何解决这个问题。您可以按字符比较$ f（x）$和$ f（y）$字符。您的磁带分为4件。第一个是用于模拟$ f（x）$的第二个$ f（y）$，然后您有两个部分，一个零件计算您当前是computig的$ x $的字符，另一个$ o（ log o（ log） n）$区域可以帮助您导航。现在程序员看起来像这样

1. 确定$ | x | $和$ | y | $（将其存储在二进制中！），并检查是否相同。
2. 通过在计算机上模拟$ f（x）$的第一个字符。将输出存储在TM状态中。暂停$ f（x）$的计算。
3. 步行$ | x |+1 $步骤向右步骤。
4. 模拟$ f（y）$，直到您获得第一个字符，请检查它是否与$ f（x）$的开始是否重合，如果没有拒绝，则继续进行。
5. 步行$ | x | $ sept。
6. 重复步骤2.-5。直到您完全检查$ f（x）= f（y）$。

Answer 2

恐怕您误读了这个问题。 $ x $和$ y $的尺寸需要相等，而不是$ f（x）$和$ f（y）$的尺寸。当然，在这种情况下，由于$ f $是长度保留，$ | x | = | y | $与$ | f（x）|相同= | f（y）| $。但是第二部分，$ f（x）= f（y）$什么？

您的算法不起作用的另一个原因是它使用线性空间。计算函数$ f $需要对数空间，但是输出需要线性空间。因此，如果您在工作录像带上存储$ f（x）$和$ f（y）$，则使用Space $ theta（n）$而不是$ o（ log n）$。