计算机科学对数空间归约本页总览对数空间归约阐述 对数空间转换器 定义对数空间转换器是一个具有只读、只写和读写纸带的 Turing 机，且在只写纸带上不能向左移动。该转换器计算一个函数 f:Σ∗→Σ∗f:\Sigma^*\to\Sigma^*f:Σ∗→Σ∗，其中 www 在只读纸带上而 f(w)f(w)f(w) 被写到只写纸带上。这样的函数称为对数空间可计算函数 对数空间归约 如果 A 可以用一个对数空间转换器来映射归约为 B，则称它是对数空间归约，记作 A≤LBA\le_LBA≤LB。 这种归约具有性质： A≤LB and B∈L, then A∈LA \leq_{\mathrm{L}} B \text { and } B \in \mathrm{L} \text {, then } A \in \mathrm{L}A≤LB and B∈L, then A∈L 实例 性质 相关内容 参考文献