15 关系: 复杂性类,图灵机,算法,美國數學學會,EXPTIME,非确定型图灵机,計算資源,計算時間,Institute for Advanced Study,NTIME,P (複雜度),決定性問題,漸進分析,指數時間,時間譜系理論。
复杂性类
在計算複雜度理論中,一個複雜度類指的是一群複雜度類似的問題的集合。一個典型的複雜度類的定義有以下--: 例如'''NP'''類就是一群可以被一非確定型圖靈機以多項式時間解決的決定型問題。而P類則是一群可以被確定型圖靈機以多項式時間解決的決定型問題。某些複雜度類是一群函式問題(Function problem)的集合,例如'''FP'''。 許多複雜度類可被描述它的數學邏輯(mathematical logic)特徵化,請見可描述的複雜度(descriptive complexity)。 而Blum公理用於不需實際計算模型就可定義複雜度類的情況。.
新!!: DTIME和复杂性类 · 查看更多 »
图灵机
图灵机(),又称确定型图灵机,是英国数学家艾倫·图灵于1936年提出的一种抽象计算模型,其更抽象的意义为一种数学逻辑机,可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。.
算法
-- 算法(algorithm),在數學(算學)和電腦科學之中,為任何良定义的具體計算步驟的一个序列,常用於計算、和自動推理。精確而言,算法是一個表示爲有限長列表的。算法應包含清晰定義的指令用於計算函數。 算法中的指令描述的是一個計算,當其時能從一個初始狀態和初始輸入(可能爲空)開始,經過一系列有限而清晰定義的狀態最終產生輸出並停止於一個終態。一個狀態到另一個狀態的轉移不一定是確定的。隨機化算法在内的一些算法,包含了一些隨機輸入。 形式化算法的概念部分源自尝试解决希尔伯特提出的判定问题,並在其后尝试定义或者中成形。这些尝试包括库尔特·哥德尔、雅克·埃尔布朗和斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的遞歸函數,阿隆佐·邱奇於1936年提出的λ演算,1936年的Formulation 1和艾倫·圖靈1937年提出的圖靈機。即使在當前,依然常有直覺想法難以定義爲形式化算法的情況。.
美國數學學會
美國數學學會(American Mathematical Society,缩写作 AMS)是美國進行數學研究和教育的組織,有不少出版品。前往英國時,受到倫敦數學學會的啟發而於1888年成立AMS。 AMS以TeX為基礎發展了。 AMS出版《數學評論》(Mathematical Reviews),這是數學出版品的評論資料庫。.
新!!: DTIME和美國數學學會 · 查看更多 »
EXPTIME
在計算複雜性理論裡面,EXPTIME(有時稱作EXP)這個複雜度類是一些決定型問題的集合,這些問題可以使用圖靈機在O(2p(n))的時間內解決,這裡的p(n)代表的是n的某個多項式。 用DTIME來定義,則是 我們已經知道 另外,根據時間譜系理論(time hierarchy theorem)以及空間譜系理論(space hierarchy theorem), 所以至少第一條包含關係中,前三個包含關係中的一個,以及後三個包含關係中的一個,必然是完整包含(沒有相等可能),但是我們還不知道那一個是。多數人相信這一些複雜度類全部都不相等。另外我們已知如果,則,這裡的NEXPTIME是在指數時間內可以使用非確定型圖靈機解決的問題。更精確的說,EXPTIME ≠ NEXPTIME若且唯若存在一個稀疏語言,在NP裡面且不在P內。 EXPTIME也可以用空間的方式來定義,等同於APSPACE這個複雜度類。APSPACE的意思是包含了所有可以用交替式圖靈機在多項式空間內解決的問題。這種定義方式也是一種看出PSPACE \subseteq EXPTIME的方式,因為已知交替式圖靈機至少跟確定型圖靈機計算能力一樣。 EXPTIME是指數譜系(exponential hierarchy)內的其中一個複雜度類。2-EXPTIME這個複雜度類則使用類似EXPTIME的定義方式,但是使用雙指數函數(Double exponential function)的時間限制2^。使用類似方式可以類推出更高的時間上限。.
新!!: DTIME和EXPTIME · 查看更多 »
非确定型图灵机
如果不加特殊说明,通常所说的图灵机都是确定型图灵机。非确定型图灵机和确定型图灵机的不同之处在于,在计算的每一时刻,根据当前状态和读写头所读的符号,机器存在多种状态转移方案,机器将任意地选择其中一种方案继续运作,直到最后停机为止。具体而言,其状态转移函数为 \delta: Q \times \Gamma \to 2^ 其中Q是状态集合,\Gamma是带字母表,L, R分别表示读写头向左和向右移动;符号2^ 表示集合A的幂集,即 2^A.
新!!: DTIME和非确定型图灵机 · 查看更多 »
計算資源
在計算複雜度理論內,計算資源(Computational resource)的意思是在特定計算模型之下,解決特定問題所要消耗的資源。 最簡單的計算資源是計算時間,計算解決特定問題需要花費的步驟數;以及記憶體空間,定義解決問題時所要花費的空間。不過,也有很多較為複雜的計算資源定義存在。 討論計算資源是非常有用的,因為我們可以用來研究哪些問題可以在給定的計算資源下得到解答。這樣,我們可以決定哪些演算法是最好的,並且有辦法討論演算法的效率。我們稱呼一個包含所有使用特定數量的資源能解決的題目之集合,為一個複雜度類。有關不同的複雜度類之間的關係,是計算複雜性理論內一個非常重要的研究領域。.
新!!: DTIME和計算資源 · 查看更多 »
計算時間
在計算複雜度理論中,計算時間是種計算抽象機器必須在某些特定計算中花費的步驟數。任何抽象機器花費的計算時間都是一種用以解決計算問題的計算資源。很多重要的複雜度類,都是依照在某些抽象機器上花費特定量級的計算時間而定義的。這些時間複雜度類別共想許多特徵,但它們的相互關係以及複雜度類對其他計算資源的影響仍未充份明瞭。 最常用以度量計算時間的抽象機器就是圖靈機。任何抽象機器,只要擁有.
新!!: DTIME和計算時間 · 查看更多 »
Institute for Advanced Study
#重定向 普林斯顿高等研究院.
新!!: DTIME和Institute for Advanced Study · 查看更多 »
NTIME
在計算複雜性理論裡面,複雜度類NTIME(f(n))是一種可以用非確定型圖靈機使用O(f(n))的時間和無限制的空間所能解決的所有決定性問題的集合。 NP這個有名的複雜度類,可以用NTIME來定義如下: 相同的,NEXPTIME這個複雜度類是由NTIME定義出來的,非決定型的時間譜系理論說明了非決定型的機器在使用更多時間的前提下可以解決更多的問題。.
新!!: DTIME和NTIME · 查看更多 »
P (複雜度)
在計算複雜度理論中,P 是在複雜度類問題中可於決定性圖靈機以多項式量級(或稱多項式時間)求解的決定性問題。 P通常表示那類可以"有效率地解決"或"溫馴"的可計算型問題,就算指數級非常高也可以算作"溫馴",例如RP與BPP問題。當然P類存在很多現實處理上一點也不溫馴的問題,例如一些至少需要n1000000指令來解決的問題。很多情況下存在著更難的複雜度問.
新!!: DTIME和P (複雜度) · 查看更多 »
決定性問題
在可計算性理論與計算複雜性理論中,所謂的決定性問題(Decision problem)是一個在某些形式系統回答是或否的問題。例如:「給兩個數字x與y,x是否可以整除y?」便是決定性問題,此問題可回答是或否,且依據其x與y的值。 決定性問題與功能性問題(Function problem,或複雜型問題)密切相關,功能性問題的答案內容,較簡單的是與非複雜許多。範例問題:「給予一個正整數x,則哪些數可整除x?」 另一個與上述兩類問題相關的是最佳化問題(Optimization problem),此問題關心的是尋找特定問題的最佳答案。 解決決定性問題的方法稱為決策程式或演算法。一個針對決定性問題的演算法將說明給予參數x和y的情況下如何決定x是否整除y。若是某些決定性問題可以被一些演算法所解決,則稱此問題可決定。 計算複雜度的領域中,分類可決定問題的依據在於此問題有多難被解決。在此標準下,所謂的難是以解決某問題最有效率的演算法所花費的計算資源為依據。在遞迴理論中,非決定性問題由圖靈度決定,指的是一種在任何解答中隱含的不可計算性量詞。 計算性理論的研究集中在決定性問題上。在與功能性問題的等值問題中,並沒有失去其普遍性。.
新!!: DTIME和決定性問題 · 查看更多 »
漸進分析
#重定向 渐近分析.
新!!: DTIME和漸進分析 · 查看更多 »
指數時間
在計算複雜度理論中,指數時間指的是一個問題求解所需要的計算時間m(n),依輸入--的大小n而呈指數成長(即輸入--的數量依線性成長,所花的時間將會以指數成長)。 以數學術語來說,便是若存在 k > 1,則此m(n).
新!!: DTIME和指數時間 · 查看更多 »
時間譜系理論
在計算複雜度理論內,時間譜系理論(Time hierarchy theorems)是一個有關圖靈機時間限制上面一個重要的理論。用不大正式的說法解釋,這理論告訴我們圖靈機在給予更多時間之後,保證能解決更多的問題。 舉例:必然存在問題是圖靈機可以用n2的時間解決,但是不能用n的時間解決。.
新!!: DTIME和時間譜系理論 · 查看更多 »