可归约性与不可解度

可归约性通过将一个问题转化为另一个问题来比较它们的难度，而将难度相等的问题归为一类则产生了不可解度，这些不可解度构成了可计算范围之外的世界。

Definition

当一个算法能够访问第二个问题的求解器并解决第一个问题时，第一个问题就归约到第二个问题；相互归约的问题具有相同的不可解度，这些度形成了一个衡量相对算法难度的序关系。

Scope

本主题涵盖多一归约（many-one reducibility）和图灵归约（Turing reducibility），利用归约证明不可判定性，产生严格更难问题的图灵跳跃（Turing jump）操作，按逻辑复杂性对问题进行分类的算术层级（arithmetical hierarchy），以及度理论（degree theory）的核心结果，例如中间度（intermediate degrees）的存在性。

Core questions

• 我们如何判断一个不可解问题比另一个更难？
• 归约如何既用于证明不可判定性又用于组织问题？
• 图灵跳跃会产生什么，为什么它总是严格更难？
• 是否存在严格介于可判定问题和停机问题之间的问题？

Key theories

可归约性与图灵跳跃

图灵归约通过谕示计算关联问题，而一个问题的跳跃（编码相对于它的停机问题）总是严格更难，从而产生一个永无止境的、越来越难的问题塔。

中间度的存在性

弗里德伯格-穆奇尼克定理通过构造不可判定但严格比停机问题更容易的可计算可枚举问题，并使用优先级方法，解决了波斯特的问题，表明度具有丰富的结构。

Clinical relevance

归约技术是证明问题不可解或在复杂性理论中证明问题难以处理的日常主力：它表明一个已知难题可以归约到一个新问题，从而将难度转移，这正是不可判定性和NP完全性结果在数学和计算机科学中确立的方式。

History

图灵于1939年引入了谕示机（oracle machines），波斯特于1944年提出了不可解度研究的框架，并提出了是否存在中间可计算可枚举度的问题。弗里德伯格和穆奇尼克于1956-1957年通过发明优先级方法（priority method）独立解决了这个问题，该方法成为该领域的核心技术。

Key figures

• Emil Post
• Alan Turing
• Richard Friedberg
• Albert Muchnik

Seminal works

• soare2016
• rogers1987

Frequently asked questions

直观上，什么是归约？

它是一种利用另一个问题的求解器来解决一个问题的方法。如果你能将问题A的任何实例转换为问题B的实例，并且答案匹配，那么B至少和A一样难，并且B的解决方案可以得到A的解决方案。

是否存在比停机问题更难的问题？

是的，有无限多个。对停机问题应用图灵跳跃会产生一个严格更难的问题，重复该操作会建立一个无尽的层级结构，因此不可解性以无界度的形式存在，而不是单一的层次。