3,094
个编辑
更改
→SRT 与计算复杂性理论
==== SRT 与计算复杂性理论 ====
==== SRT 与计算复杂性理论 ====
在[[复杂性理论]]中，递归定理主要扮演'''证明工具'''的角色。[[复杂性类]]的许多分离与结构定理采用"带时钟的对角化"：让机器检查并躲开自己（或更早的机器）的行为；当这种自躲藏需要程序援引自己的代码时，严格化的抓手正是 SRT。这类证明有一个内禀的时序难题：对角化机器要躲开的对象可能就是它自己（或自己的更早版本），而它必须在对方"提交行为"之后才能可靠地反着做——处理这一难题的技术称为'''延迟对角化'''（delayed diagonalization），其源头是 Breidbart 的"[[分裂递归集]]"构造显式调用递归定理<ref name="breidbart1978">'''Breidbart, S. (1978).''' ''On splitting recursive sets''. Journal of Computer and System Sciences 17: 56–64.【复杂性类对角化中显式使用递归定理的"延迟构造"源头】</ref>；其思想后来被 Schmidt 统一为"[[复杂性类的递归论结构]]"定理，推论包括：除非 [[NP = P]]，[[NP]] 不等于 [[P]] 与 NP 完全类之并这类"[[可递归呈现类]]"的非平凡并<ref name="schmidt1985">'''Schmidt, D. (1985).''' ''The recursion-theoretic structure of complexity classes''. Theoretical Computer Science 38: 143–156. doi:10.1016/0304-3975(85)90217-8.【复杂性类对角化定理的递归论统一；推论：除非 NP=P，NP ≠ P ∪ {NP完全类}】</ref>。延迟对角化由此成为分离复杂性类的标准武器——本质上，它是"带时钟的对角线"对自引用时序的形式化处理。
在[[复杂性理论]]中，递归定理主要扮演'''证明工具'''的角色。[[复杂性类]]的许多分离与结构定理采用"带时钟的对角化"：让机器检查并躲开自己（或更早的机器）的行为；当这种自躲藏需要程序援引自己的代码时，严格化的抓手正是 SRT。这类证明有一个内禀的时序难题：对角化机器要躲开的对象可能就是它自己（或自己的更早版本），而它必须在对方"提交行为"之后才能可靠地反着做——处理这一难题的技术称为'''[[延迟对角化]]'''（delayed diagonalization）。这一思想的源头可以追溯到 Breidbart 的"[[分裂递归集]]"构造显式调用递归定理<ref name="breidbart1978">'''Breidbart, S. (1978).''' ''On splitting recursive sets''. Journal of Computer and System Sciences 17: 56–64.【复杂性类对角化中显式使用递归定理的"延迟构造"源头】</ref>，后来被 Schmidt 统一为"[[复杂性类的递归论结构]]"定理，推论包括：除非 [[NP = P]]，[[NP]] 不等于 [[P]] 与 NP 完全类之并这类"[[可递归呈现类]]"的非平凡并<ref name="schmidt1985">'''Schmidt, D. (1985).''' ''The recursion-theoretic structure of complexity classes''. Theoretical Computer Science 38: 143–156. doi:10.1016/0304-3975(85)90217-8.【复杂性类对角化定理的递归论统一；推论：除非 NP=P，NP ≠ P ∪ {NP完全类}】</ref>。延迟对角化由此成为分离复杂性类的标准武器——本质上，它是"带时钟的对角线"对自引用时序的形式化处理。
在[[曼纽尔·布卢姆|Blum]]的机器无关复杂性理论中，SRT 与对角化结合产生了一批"存在性"结果。代表性的一例：Helm 与 Young 回答了 Blum 的一个问题——存在这样的可计算函数，任何为它"换上更快的程序"的尝试都要付出程序尺寸爆炸的代价，且刻画这一代价的增长函数快于任何递归函数<ref name="helmyoung1971">'''Helm, J.; Young, P. (1971).''' ''On size vs. efficiency for programs admitting speed-ups''. Journal of Symbolic Logic 36.【回答 Blum 的问题：加速必然伴随尺寸爆炸，代价函数增长快于任何递归函数】</ref>。"加速与简洁不可兼得"由此成为定理而非格言。
在[[曼纽尔·布卢姆|Blum]]的机器无关复杂性理论中，SRT 与对角化结合产生了一批"存在性"结果。代表性的一例：Helm 与 Young 回答了 Blum 的一个问题——存在这样的可计算函数，任何为它"换上更快的程序"的尝试都要付出程序尺寸爆炸的代价，且刻画这一代价的增长函数快于任何递归函数<ref name="helmyoung1971">'''Helm, J.; Young, P. (1971).''' ''On size vs. efficiency for programs admitting speed-ups''. Journal of Symbolic Logic 36.【回答 Blum 的问题：加速必然伴随尺寸爆炸，代价函数增长快于任何递归函数】</ref>。"加速与简洁不可兼得"由此成为定理而非格言。