跳至內容

可構函數

維基百科,自由的百科全書

複雜度理論裏,函數時間可構(英語: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.