時間譜系理論

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP




在計算複雜度理論內，時間譜系理論（Time hierarchy theorems）是一個有關圖靈機時間限制上面一個重要的理論。用不大正式的說法解釋，這理論告訴我們圖靈機在給予更多時間之後，保證能解決更多的問題。


舉例：必然存在問題是圖靈機可以用n2的時間解決，但是不能用n的時間解決。



參考資料





  • Michael Sipser. Introduction to the Theory of Computation. PWS Publishing. 1997. ISBN 0-534-94728-X.  Pages 310–313 of section 9.1: Hierarchy theorems.


  • Christos Papadimitriou. Computational Complexity 1st. Addison Wesley. 1993. ISBN 0-201-53082-1.  Section 7.2: The Hierarchy Theorem, pp. 143–146.

-

Popular posts from this blog

用户:Ww71338ww/绘画

Image
Clash Royale CLAN TAG #URR8PPP 你好～！欢迎来到萌娘百科！ 如果您是第一次来到这里，点这里加入萌娘百科! 欢迎具有翻译能力的同学～有意者请点→Category:需要翻译的条目← 如果您在萌娘百科上发现某些内容 错误/空缺 ，请 勇于 修正/添加！ 编辑萌娘百科其实很容易！ 觉得萌娘百科有趣的话，请推荐给朋友哦...
Read more

自由群

Image
Clash Royale CLAN TAG #URR8PPP 由兩個元素a, b 生成的自由群的凱萊圖 在數學中，一個群 Gdisplaystyle G 被稱作 自由群 ，如果存在 Gdisplaystyle G 的子集 Sdisplaystyle S 使得 Gdisplaystyle G 的任何元素都能唯一地表成由 Sdisplaystyle S 中元素及其逆元組成之乘積（在此不論平庸的表法，例如 st−1=su−1ut−1displaystyle st^-1=su^-1ut^-1 之類）；此時也稱 Gdisplaystyle G 為集合 Sdisplaystyle S 上的 自由群 ，其群...
Read more

卑爾根

Image
Clash Royale CLAN TAG #URR8PPP 卑尔根 Bergen 城市 Kommune av Bergen 旗幟 徽章 卑爾根在霍达兰郡的位置 卑尔根 卑爾根在挪威的位置 坐标： 60°22′N 05°24′E  /  60.367°N 5.400°E  / 60.367; 5.400 坐标： 60°22′N 05°24′E  /  60.367°N 5.400°E  / 60.367; 5.400 國家   挪威 郡 霍达兰郡 建立 1070年之前 政府  • 市長 Marita Moltu （KrF） 面积  • 城市 464.71 平方公里（179.43 平方英里）  • 陸地...
Read more