跳转到内容

可构函数

维基百科,自由的百科全书

复杂度理论里,函数时间可构(英语:time constructible),意即存在运行时间规模在内的图灵机,当输入时,图灵机输出。定义此类函数是为了排除一些无法成为图灵机运行时间上界的函数。[1]

时间可构函数

有两种不同的方式去定义时间可构函数。第一种定义里,函数时间可构,当且仅当存在正整数和图灵机,使得对所有,在输入字串个1)后,该图灵机恰好步后停机。第二种定义里,函数时间可构,当且仅当存在图灵机,在输入字串个1)后,它会在时间内输出的二进制(亦可以用输出一进制,两种表示的定义等价,因为可以用时间转换两种表示)。[1]

另外,还有整体时间可构函数:函数时间全可构当且仅当存在图灵机,对所有自然数,输入字串后,恰好在步后停机。这个定义比前两个定义更狭窄,但在多数应用里,使用哪种定义都无伤大雅[来源请求]

空间可构函数

类似地,函数空间可构,当且仅当存在正整数和图灵机,使得对所有,在输入字串后,该图灵机恰好在使用了个格子后停机。等价地,函数空间可构,当且仅当存在图灵机,在输入字串个1)后,它会在O(f(n))空间内输出的二进制(或一进制)。[1]

另外,函数空间全可构当且仅当存在图灵机,对所有自然数,在输入字串后,恰好在使用了个格子后停机[来源请求]

例子

所有满足(其中是常数)的常见函数(例如)都是时间和空间可构的。除了最终是常数的函数,里的函数都不时间可构,因为图灵机甚至没有时间完整读入。不过是空间可构的。

应用

复杂度理论的结论,例如时间阶层定理使用了时间可构函数去刻划复杂度层级。这是因为时间层级能成立的基石是能在O(f(n))时间内判断其他算法是否已经用了超过步的图灵机。假若不能在这么多步以内计算,该图灵机当然不可能存在。类似的复杂度定理一般对所有自然的函数都成立,但不一定对人为构造的成立。时间可构函数的严谨定义成功准确刻划了这些满足时间阶层定理的函数。

空间可构函数在空间阶层定理里亦有类似的应用。

本条目含有来自PlanetMathconstructible》的内容,版权遵守知识共享协议:署名-相同方式共享协议

参考文献

  1. ^ 1.0 1.1 1.2 Goldreich, Oded. Computational Complexity: A Conceptual Perspective. Cambridge University Press. 2008: 130, 139. ISBN 978-0-521-88473-0.