间隙定理
维基百科,自由的 encyclopedia
在计算复杂性理论,间隙定理,又称鲍罗丁-特拉赫坚布罗特间隙定理,为与可计算函数复杂度有关的重要定理。[1]
定理断言,复杂性类的层阶之间,有任意大的可计算间隙。意思是,若给定任意一个可计算函数,表示计算资源增加一次的效果,则必能找到某个资源上限
,使得即使将资源上限增加一次变成
,也无法计算更多函数。
定理由鲍里斯·特拉赫坚布罗特(英语:Boris Trakhtenbrot)[2]和艾伦·鲍罗丁(英语:Allan Borodin)[3][4]分别独立证出。
虽然特拉赫坚布罗特的推导比鲍罗丁早几年,但时值冷战,该定理直到鲍罗丁发表后才为西方认识。
定理叙述
定理的一般形式如下:
- 设
为抽象(布卢姆)复杂度衡量。对任意满足
(对所有
)的全可计算函数
,都存在严格单调的全可计算函数
,使得就
而言,以
为限的复杂性类等于以
为限的复杂性类。
定理可由复杂度衡量需满足的布卢姆公理证出,而无须牵涉具体的计算模型,故其适用于时间复杂度、空间复杂度,或任何其他合适的复杂度衡量。
关于时间复杂度的特例,定理可更简单复述成:
由于时限可以很大(且通常不可构),间隙定理无法推出有关复杂度类
或
的非平凡结果,[5]也不与时间阶层定理或空间阶层定理矛盾。[6]
证明
鲍罗丁[4]证明的关键是,函数在不同自然数的取值
可以逐一选取,迫使所有复杂度
都不能介乎
和
之间。具体而言:
- 定义
;
- 对
,定义
为最小的自然数
,使得
,且对所有
,有
或
。
首先,由于满足布卢姆公理,
和
两者皆是可判定的,故上述定义是
的
-递归定义,从而
为(偏)可计算函数。
然后,为验证是全函数,需证明在定义
时,满足条件的
存在。对每个
,
- 若
,则
总成立;
- 否则,希望
成立。
所以只要大于
之中有限的全部数便可。故有
全可计算。
最后,由的定义知,
递增,且对每个
,当
时,或有
,或有
,故编号为
的可计算函数的复杂度不能介于
和
之间。
与加速定理的比较
原始的间隙定理比上述定理更强:
- 设
是一个复杂度衡量。对任意满足
的全可计算函数
,都存在严格单调的全可计算函数
,令
和
限制下的程式编号集相等。
这里的编号指的是附带的编号 (可计算性理论)。
由此可见,没有程式的复杂度在和
之间。虽然能用复杂度
和复杂度
实现的程式的集合是一样的,但这只对某些的充分大的
成立。因此,间隙定理与加速定理不同。[7]
诚实性定理
以不同的函数为限,可以得到同一个复杂度类
。此种
称为该复杂度类的名。时间阶层定理和空间阶层定理断言,若限定复杂度类的名具有某种好性质(可构),则不会有太大的间隙。对抽象复杂度而言,也有类似的性质,称为诚实性(honestness)。以具有此种性质的函数为名的复杂度类之间,并无间隙现象。[8]函数诚实是指其计算复杂度与输入和输出相比不太大(用词源自“函数的值诚实反映其复杂度”)。麦克雷特(E. M. McCraight)和迈耶(A. R. Meyer)证明,以可计算函数为名的复杂度类,总能改名为诚实函数,而不改变其实质。所以,间隙定理的实际源由,是复杂度类改坏名。[9]:86
算子间隙定理
以表示(一元)可计算偏函数的类。映射
称为可(有效)计算算子,若存在全可计算函数
,使得
对所有
成立。此处
是编号为
的函数。若
将全函数映至全函数,则称
保全。间隙定理可复述成:对于由
定义的可计算保全算子
,可找到
令
和
之间有间隙。罗伯特·李·康斯特勃(英语:Robert Lee Constable)证明,同样的结论对其他可计算保全算子也成立,即:[10]
- 设
为抽象复杂度衡量,则对任意满足
的可计算保全算子
,存在严格递增的可计算全函数
,令以
和
为限的程式编号集相等。
参见
参考资料
- Fortnow, Lance; Homer, Steve. A Short History of Computational Complexity [计算复杂性简史] (PDF). Bulletin of the European Association for Theoretical Computer Science. June 2003, (80): 95–133. (原始内容 (PDF)存档于2005-12-29) (英语).
- Trakhtenbrot, Boris A. The Complexity of Algorithms and Computations (Lecture Notes) [算法与计算的复杂度(讲义)]. Novosibirsk University. 1967.
- Allan Borodin. Complexity Classes of Recursive Functions and the Existence of Complexity Gaps [递归函数的复杂度类与复杂度间隙的存在性]. Proc. of the 1st Annual ACM Symposium on Theory of Computing. 1969: 67–78 (英语).
- Borodin, Allan. Computational complexity and the existence of complexity gaps [计算复杂度与复杂度间隙的存在性]. Journal of the ACM. January 1972, 19 (1): 158–174. doi:10.1145/321679.321691 (英语).
- Allender, Eric W.; Loui, Michael C.; Regan, Kenneth W., Chapter 7: Complexity Theory, Gonzalez, Teofilo; Diaz-Herrera, Jorge; Tucker, Allen (编), Computing Handbook, Third Edition: Computer Science and Software Engineering [计算手册,第三版:电脑科学与软件工程], CRC Press: 7–9, 2014 [2021-08-09], ISBN 9781439898529, (原始内容存档于2021-09-06) (英语),
Fortunately, the gap phenomenon cannot happen for time bounds t that anyone would ever be interested in
. - Zimand, Marius, Computational Complexity: A Quantitative Perspective [计算复杂度:定量观点], North-Holland Mathematics Studies 196, Elsevier: 42, 2004 [2021-08-09], ISBN 9780080476667, (原始内容存档于2021-09-04) (英语).
- Borodin, Allan B. Computational Complexity and the Existence of Complexity Gaps [计算复杂度与复杂度间隙的存在性]. Cornell University. 1969 (英语).
- R.Moll; A.R.Meyer. Honest Bounds for Complexity Classes of Recursive Functions [递归函数复杂度类的诚实界]. Journal of Symbolic Logic. 1974, 39 (1): 127–138 (英语).
- E. M. McCreight; A. R. Meyer. Classes of computable functions defined by bounds on computation: preliminary report [由计算的限制定义的可计算函数类:初步报告]. Proceedings of the first annual ACM symposium on Theory of computing. 1969: 79–88 (英语).
- Robert L. Constable. The operator gap [算子间隙]. IEEE Conference Record of 10th Annual Symposium on Switching and Automata Theory. 1969: 20–26 (英语).