^ 1.01.11.2Goldreich, Oded. Computational Complexity: A Conceptual Perspective. Cambridge University Press. 2008: 130, 139. ISBN 978-0-521-88473-0.
十月 31, 2023
可構函數, 複雜度理論裡, 函數f, displaystyle, mathbb, mathbb, 時間可構, 英語, time, constructible, 意即存在運行時間規模在f, displaystyle, 內的圖靈機, 當輸入n, displaystyle, 圖靈機輸出f, displaystyle, 定義此類函數是為了排除一些無法成為圖靈機運行時間上界的函數, 目录, 時間, 空間, 例子, 應用, 參考文獻時間, 编辑有兩種不同的方式去定義時間, 第一種定義裡, 函數f, displaystyle, . 複雜度理論裡 函數f N N displaystyle f mathbb N to mathbb N 時間可構 英語 time constructible 意即存在運行時間規模在f n displaystyle f n 內的圖靈機 當輸入n displaystyle n 時 圖靈機輸出f n displaystyle f n 定義此類函數是為了排除一些無法成為圖靈機運行時間上界的函數 1 目录 1 時間可構函數 2 空間可構函數 3 例子 4 應用 5 參考文獻時間可構函數 编辑有兩種不同的方式去定義時間可構函數 第一種定義裡 函數f displaystyle f nbsp 時間可構 當且僅當存在正整數n 0 displaystyle n 0 nbsp 和圖靈機M displaystyle M nbsp 使得對所有n n 0 displaystyle n geq n 0 nbsp 在輸入字串1 n displaystyle 1 n nbsp n displaystyle n nbsp 個1 後 該圖靈機恰好f n displaystyle f n nbsp 步後停機 第二種定義裡 函數f displaystyle f nbsp 時間可構 當且僅當存在圖靈機M displaystyle M nbsp 在輸入字串1 n displaystyle 1 n nbsp n displaystyle n nbsp 個1 後 它會在O f n displaystyle O f n nbsp 時間內輸出f n displaystyle f n nbsp 的二進制 亦可以用輸出一進制 兩種表示的定義等價 因為可以用O f n displaystyle O f n nbsp 時間轉換兩種表示 1 另外 還有整體時間可構函數 函數f displaystyle f nbsp 時間全可構當且僅當存在圖靈機M displaystyle M nbsp 對所有自然數n displaystyle n nbsp 輸入字串1 n displaystyle 1 n nbsp 後 恰好在f n displaystyle f n nbsp 步後停機 這個定義比前兩個定義更狹窄 但在多數應用裡 使用哪種定義都無傷大雅 來源請求 空間可構函數 编辑類似地 函數f displaystyle f nbsp 空間可構 當且僅當存在正整數n 0 displaystyle n 0 nbsp 和圖靈機M displaystyle M nbsp 使得對所有n n 0 displaystyle n geq n 0 nbsp 在輸入字串1 n displaystyle 1 n nbsp 後 該圖靈機恰好在使用了f n displaystyle f n nbsp 個格子後停機 等價地 函數f displaystyle f nbsp 空間可構 當且僅當存在圖靈機M displaystyle M nbsp 在輸入字串1 n displaystyle 1 n nbsp n displaystyle n nbsp 個1 後 它會在O f n 空間內輸出f n displaystyle f n nbsp 的二進制 或一進制 1 另外 函數f displaystyle f nbsp 空間全可構當且僅當存在圖靈機M displaystyle M nbsp 對所有自然數n displaystyle n nbsp 在輸入字串1 n displaystyle 1 n nbsp 後 恰好在使用了f n displaystyle f n nbsp 個格子後停機 來源請求 例子 编辑所有滿足f n c n displaystyle f n geq cn nbsp 其中c gt 0 displaystyle c gt 0 nbsp 是常數 的常見函數 例如n n k 2 n displaystyle n n k 2 n nbsp 都是時間和空間可構的 除了最終是常數的函數 o n displaystyle o n nbsp 裡的函數都不時間可構 因為圖靈機甚至没有時間完整讀入n displaystyle n nbsp 不過log n displaystyle log n nbsp 是空間可構的 應用 编辑複雜度理論的結論 例如時間階層定理使用了時間可構函數去刻劃複雜度層級 這是因為時間層級能成立的基石是能在O f n 時間內判斷其他算法是否已經用了超過f n displaystyle f n nbsp 步的圖靈機 假若f n displaystyle f n nbsp 不能在這麼多步以內計算 該圖靈機當然不可能存在 類似的複雜度定理一般對所有自然的函數f displaystyle f nbsp 都成立 但不一定對人為構造的f displaystyle f nbsp 成立 時間可構函數的嚴謹定義成功準確刻劃了這些滿足時間階層定理的函數 空間可構函數在空間階層定理裡亦有類似的應用 本條目含有来自PlanetMath constructible 的內容 版权遵守知识共享协议 署名 相同方式共享协议 參考文獻 编辑 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 取自 https zh wikipedia org w index php title 可構函數 amp oldid 68110538, 维基百科,wiki,书籍,书籍,图书馆,