在计算复杂性理论,间隙定理,又称鲍罗丁-特拉赫坚布罗特间隙定理,为与可计算函数复杂度有关的重要定理。[1]
定理断言,复杂性类的层阶之间,有任意大的可计算间隙。意思是,若给定任意一个可计算函数,表示计算资源增加一次的效果,则必能找到某个资源上限,使得即使将资源上限增加一次变成,也无法计算更多函数。
定理由鲍里斯·特拉赫坚布罗特[2]和艾伦·鲍罗丁[3][4]分别独立证出。
虽然特拉赫坚布罗特的推导比鲍罗丁早几年,但时值冷战,该定理直到鲍罗丁发表后才为西方认识。
定理叙述
定理的一般形式如下:
- 设为抽象(布卢姆)复杂度衡量。对任意满足(对所有)的全可计算函数,都存在严格单调的全可计算函数,使得就而言,以为限的复杂性类等于以为限的复杂性类。
定理可由复杂度衡量需满足的布卢姆公理证出,而无须牵涉具体的计算模型,故其适用于时间复杂度、空间复杂度,或任何其他合适的复杂度衡量。
关于时间复杂度的特例,定理可更简单复述成:
由于时限可以很大(且通常不可构),间隙定理无法推出有关复杂度类或的非平凡结果,[5]也不与时间阶层定理或空间阶层定理矛盾。[6]
证明
鲍罗丁[4]证明的关键是,函数在不同自然数的取值可以逐一选取,迫使所有复杂度都不能介乎和之间。具体而言:
- 定义;
- 对,定义为最小的自然数,使得,且对所有,有或。
首先,由于满足布卢姆公理,和两者皆是可判定的,故上述定义是的-递归定义,从而为(偏)可计算函数。
然后,为验证是全函数,需证明在定义时,满足条件的存在。对每个,
- 若,则总成立;
- 否则,希望成立。
所以只要大于之中有限的全部数便可。故有全可计算。
最后,由的定义知,递增,且对每个,当时,或有,或有,故编号为的可计算函数的复杂度不能介于和之间。
与加速定理的比较
原始的间隙定理比上述定理更强:
- 设是一个复杂度衡量。对任意满足的全可计算函数,都存在严格单调的全可计算函数,令和限制下的程式编号集相等。
这里的编号指的是附带的编号 (可计算性理论)。
由此可见,没有程式的复杂度在和之间。虽然能用复杂度和复杂度实现的程式的集合是一样的,但这只对某些的充分大的成立。因此,间隙定理与加速定理不同。[7]
诚实性定理
以不同的函数为限,可以得到同一个复杂度类。此种称为该复杂度类的名。时间阶层定理和空间阶层定理断言,若限定复杂度类的名具有某种好性质(可构),则不会有太大的间隙。对抽象复杂度而言,也有类似的性质,称为诚实性(honestness)。以具有此种性质的函数为名的复杂度类之间,并无间隙现象。[8]函数诚实是指其计算复杂度与输入和输出相比不太大(用词源自“函数的值诚实反映其复杂度”)。麦克雷特(E. M. McCraight)和迈耶(A. R. Meyer)证明,以可计算函数为名的复杂度类,总能改名为诚实函数,而不改变其实质。所以,间隙定理的实际源由,是复杂度类改坏名。[9]:86
算子间隙定理
以表示(一元)可计算偏函数的类。映射称为可(有效)计算算子,若存在全可计算函数,使得对所有成立。此处是编号为的函数。若将全函数映至全函数,则称保全。间隙定理可复述成:对于由定义的可计算保全算子,可找到令和之间有间隙。罗伯特·李·康斯特勃证明,同样的结论对其他可计算保全算子也成立,即:[10]
- 设为抽象复杂度衡量,则对任意满足的可计算保全算子,存在严格递增的可计算全函数,令以和为限的程式编号集相等。
参见
参考资料
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.