基本介紹
- 中文名：
- 外文名：
- 所屬學科：
- 公布時間：
定義,公布時間,出處,
交替時間複雜性
相關詞條
- 交替時間複雜性
交替時間複雜性是2018年全國科學技術名詞審定委員會公布的計算機科學技術名詞。定義交替圖靈機的時間複雜性。令 M 是一個交替圖靈機，對函式 t ∶N→N，稱 M 是 t(n) 時間的交替圖靈機，如果對每一個輸入，和每一個...
- 交替對數空間複雜性類
交替對數空間複雜性類（alternating logspace complexity class）是2018年公布的計算機科學技術名詞。定義 在對數空間交替圖靈機所接受的語言做成的類，記為AL。已經證明AL = P，即交替對數空間複雜性類與多項式時間複雜性類相同。出處 《...
- 計算複雜性理論(2023年清華大學出版社出版的圖書)
《計算複雜性理論》是2023年清華大學出版社出版的圖書，作者是傅育熙。內容簡介 本書是一本介紹計算複雜性理論的基礎教材, 內容包括時間複雜性、空間複雜性、NP-理論、多項式譜 系、電路複雜性、隨機計算及去隨機、計數複雜性、互動證明...
- 交替式圖靈機
。一台2次交替圖靈機從一個存在狀態出發可以在多項式時間內解決這個問題（在存在狀態通過猜測電路 的 個門，此後進入全稱狀態，猜測輸入並檢查輸出是否和 相同）。一台從存在狀態（或者全稱狀態）出發的 次交替圖靈機可以在多項式時間...
