比浏览器更快的访问！
11 关系: 复杂性类，DTIME，ELEMENTARY，EXPSPACE，EXPTIME，雙重指數，NEXPTIME，NP (複雜度)，P (複雜度)，PSPACE，決定性問題。
复杂性类
在計算複雜度理論中，一個複雜度類指的是一群複雜度類似的問題的集合。一個典型的複雜度類的定義有以下--： 例如'''NP'''類就是一群可以被一非確定型圖靈機以多項式時間解決的決定型問題。而P類則是一群可以被確定型圖靈機以多項式時間解決的決定型問題。某些複雜度類是一群函式問題（Function problem）的集合，例如'''FP'''。 許多複雜度類可被描述它的數學邏輯（mathematical logic）特徵化，請見可描述的複雜度（descriptive complexity）。 而Blum公理用於不需實際計算模型就可定義複雜度類的情況。.
新！!: 2-EXPTIME和复杂性类 · 查看更多 »
DTIME
在計算複雜度理論內，DTIME（或者TIME）是一個圖靈機的計算資源或者計算時間的計量方式。它代表一個"普通"有實體的電腦解決特定計算問題，使用特定演算法，所要花費的時間。這個計算資源是最被廣泛研究的計算資源，因為它與真實世界所重視的資源（要花費多少時間才能計算出一個問題）息息相關。 DTIME這個資源常被使用來定義複雜度類，亦即，可以在特定時間內解決的決定性問題其集合。如果一個問題其輸入的大小為n，並且可要求f(n)的計算時間來解決，那我們說這問題在DTIME(f(n))（or TIME(f(n))）裡面。這裡沒有限制必須使用多少記憶體空間（參見計算資源），但是有可能會限制一些其他的計算資源（像是可否使用交替圖靈機）。.
新！!: 2-EXPTIME和DTIME · 查看更多 »
ELEMENTARY
在計算複雜度理論裡面，複雜度類ELEMENTARY是所有指數譜系裡面的複雜度類聯集： 這名稱最早是為了探討可計算函數和不可判定問題，由László Kalmár所提出；most problems in it are far from elementary。Some natural recursive problems lie outside ELEMENTARY, and are thus NONELEMENTARY。相當值得注意的，有一些原始遞歸函數問題不在ELEMENTARY內。我們已知： LOWER-ELEMENTARY \subsetneq EXPTIME \subsetneq ELEMENTARY \subsetneq PR 與ELEMENTARY僅包含有限的冪（例如，O(2^)）比較，PR使用的 超運算更一般化（例如，tetration），因此PR不包含於ELEMENTARY。 1,..., xn).
新！!: 2-EXPTIME和ELEMENTARY · 查看更多 »
EXPSPACE
在計算複雜度理論內，EXPSPACE是一個包含可以在O(2p(n))空間內解決的決定性問題的集合，這裡的p(n)是某個n的多項式。（有些作者認為p(n）應該限制為線性函數，但是多數的人把這這樣的複雜度類稱作ESPACE。)如果我們使用非決定性圖靈機，我們會得到複雜度類NEXPSPACE。根據薩維奇定理，這個複雜度類等同EXPSPACE。 以DSPACE和NSPACE表示： 我們說一個問題是EXPSPACE-完全，如果這問題本身在EXPSPACE內，而且存在多項式多對一歸約，令所有在EXPSPACE內的題目都可以歸約成這個題目。換句話說，存在一個多項式時間的演算法可以將一個狀況換成其他題目的另一個狀況，並且答案一樣。EXPSPACE-完全的題目也可以想做是EXPSPACE裡面最難的題目。 EXPSPACE是PSPACE，NP，和P的嚴格母集（前者包含且不等於後者）。並且也被相信是EXPTIME的嚴格母集。 一個EXPSPACE-完全的例子是分辨兩個正規表式是否是一樣的語言這個問題。這裡的表示限制使用四種操作子：聯集，串街，克萊尼星號（可以是零個或多個重複的表示式），和平方（兩份表示式）。 如果我們排除星號，則這個問題變成NEXPTIME-完全，這個複雜度類有點類似EXPTIME-完全，不過使用的機器是非決定性圖靈機而非一般的圖靈機。 L. Berman在1980年證明了，證明或反證任何有關實數並且牽涉加法和比較大小（但不牽涉乘法）的一階陳述，這個問題在EXPSPACE內。.
新！!: 2-EXPTIME和EXPSPACE · 查看更多 »
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^。使用類似方式可以類推出更高的時間上限。.
新！!: 2-EXPTIME和EXPTIME · 查看更多 »
雙重指數
#重定向 雙重指數函數.
新！!: 2-EXPTIME和雙重指數 · 查看更多 »
NEXPTIME
在計算複雜度理論內，複雜度類NEXPTIME（有時叫做NEXP）是一個決定性問題的集合，包含可以使用非確定型圖靈機，使用O(2p(n))（這裡的p(n)是某個多項式）的時間可以解決的問題。另外這裡不限制空間的使用。 以NTIME作定義 一個很重要的NEXPTIME-完全問題集合與簡潔電路（succinct circuit）有關。簡潔電路是能以指數速率縮減的空間形容圖的一個機器。這個機器接收兩個頂點的號碼為輸入，輸出這兩個頂點是否有邊相連。如果有個問題，使用一般的圖表示法，像是連接矩陣，去解決時是個NP-完全問題，那麼使用簡潔電路的表示來解決這個問題是NEXPTIME-完全，因為輸入的大小跟前者相比是成指數速率縮小。舉個簡單的例子，使用簡潔電路的表示法找一張圖的哈密頓圖是NEXPTIME-完全。 如果'''P'''.
新！!: 2-EXPTIME和NEXPTIME · 查看更多 »
NP (複雜度)
非定常多项式（non-deterministic polynomial，缩写：NP）时间复杂性类，或称非确定性多项式时间复杂性类，包含了可以在多项式时间内，对一个判定性算法问题的实例，一个给定的解是否正确的算法问题。 NP是计算复杂性理论中最重要的复杂性类之一。它包含复杂性类P，即在多项式时间内可以验证一个算法问题的实例是否有解的算法问题的集合；同时，它也包含NP完全问题，即在NP中“最难”的问题。计算复杂性理论的中心问题，P/NP问题即是判断对任意的NP完全问题，是否有有效的算法，或者NP与P是否相等。.
新！!: 2-EXPTIME和NP (複雜度) · 查看更多 »
P (複雜度)
在計算複雜度理論中，P 是在複雜度類問題中可於決定性圖靈機以多項式量級（或稱多項式時間）求解的決定性問題。 P通常表示那類可以"有效率地解決"或"溫馴"的可計算型問題，就算指數級非常高也可以算作"溫馴"，例如RP與BPP問題。當然P類存在很多現實處理上一點也不溫馴的問題，例如一些至少需要n1000000指令來解決的問題。很多情況下存在著更難的複雜度問.
新！!: 2-EXPTIME和P (複雜度) · 查看更多 »
PSPACE
PSPACE是计算复杂度理论中能被确定型图灵机利用多项式空间解决的判定问题集合，是Polynomial SPACE的简称。.
新！!: 2-EXPTIME和PSPACE · 查看更多 »
決定性問題
在可計算性理論與計算複雜性理論中，所謂的決定性問題（Decision problem）是一個在某些形式系統回答是或否的問題。例如：「給兩個數字x與y，x是否可以整除y？」便是決定性問題，此問題可回答是或否，且依據其x與y的值。 決定性問題與功能性問題（Function problem，或複雜型問題）密切相關，功能性問題的答案內容，較簡單的是與非複雜許多。範例問題：「給予一個正整數x，則哪些數可整除x？」 另一個與上述兩類問題相關的是最佳化問題（Optimization problem），此問題關心的是尋找特定問題的最佳答案。 解決決定性問題的方法稱為決策程式或演算法。一個針對決定性問題的演算法將說明給予參數x和y的情況下如何決定x是否整除y。若是某些決定性問題可以被一些演算法所解決，則稱此問題可決定。 計算複雜度的領域中，分類可決定問題的依據在於此問題有多難被解決。在此標準下，所謂的難是以解決某問題最有效率的演算法所花費的計算資源為依據。在遞迴理論中，非決定性問題由圖靈度決定，指的是一種在任何解答中隱含的不可計算性量詞。 計算性理論的研究集中在決定性問題上。在與功能性問題的等值問題中，並沒有失去其普遍性。.
新！!: 2-EXPTIME和決定性問題 · 查看更多 »
