比浏览器更快的访问！
22 关系: 复杂性类，國際象棋，國際跳棋，围棋，图灵机，稀疏語言，DTIME，EXPSPACE，非确定型图灵机，計算複雜性理論，邻接矩阵，集合，NEXPTIME，NP (複雜度)，P (複雜度)，P-完全，P/NP问题，PSPACE，決定性問題，指數譜系，時間譜系理論，2-EXPTIME。
复杂性类
在計算複雜度理論中，一個複雜度類指的是一群複雜度類似的問題的集合。一個典型的複雜度類的定義有以下--： 例如'''NP'''類就是一群可以被一非確定型圖靈機以多項式時間解決的決定型問題。而P類則是一群可以被確定型圖靈機以多項式時間解決的決定型問題。某些複雜度類是一群函式問題（Function problem）的集合，例如'''FP'''。 許多複雜度類可被描述它的數學邏輯（mathematical logic）特徵化，請見可描述的複雜度（descriptive complexity）。 而Blum公理用於不需實際計算模型就可定義複雜度類的情況。.
新！!: EXPTIME和复杂性类 · 查看更多 »
國際象棋
國際象棋（chess），又稱歐洲象棋或--，是一種二人對弈的戰略棋盘遊戲，也是世界上最流行的遊戲之一。世界各地數以百萬計的人在家中、中、網路上以或比賽形式对弈。 國際象棋的棋盤由64個黑白相間的八乘八網格組成。每位玩家开局时各有16個棋子：一王、一-后-、兩车、兩马、兩象和八兵，各具不同功能与走法。棋手行棋目标是將對方的王處在不可避免的威脅之下以將死對方，也可以通过對方自知无望、主动认输而獲勝，另有相当多的情况可导致和局。遊戲過程分三個階段：开局、中局、，共有1043至1050種棋局變化。 国际象棋棋子多用木或塑膠製成，也有用石材制作；较为精美的石頭、玻璃（水晶）或金屬製棋子常用作裝飾擺設。.
新！!: EXPTIME和國際象棋 · 查看更多 »
國際跳棋
#重定向 西洋跳棋.
新！!: EXPTIME和國際跳棋 · 查看更多 »
围棋
围棋是一種策略性棋類，使用格狀棋盤及黑白二色棋子進行對弈。起源于中国，中國古时有“弈”、“--”、“手谈”等多种称谓，屬琴棋书画四艺之一。西方稱之為“Go”，是源自日語「碁」的发音。 对弈双方在棋盘网格的交叉点上交替放置黑色和白色的棋子。Matthews, Charles.
新！!: EXPTIME和围棋 · 查看更多 »
图灵机
图灵机（），又称确定型图灵机，是英国数学家艾倫·图灵于1936年提出的一种抽象计算模型，其更抽象的意义为一种数学逻辑机，可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。.
新！!: EXPTIME和图灵机 · 查看更多 »
稀疏語言
在計算複雜性理論裡面, 稀疏語言是一種形式語言 (一堆字串的集合字串)，並且這語言內長度為n的字串個數，被一個n的多項式所限制住。 這種語言主要被用來研究NP這類語言與其他種類語言的關係。包含所有稀疏語言的複雜度類被稱作SPARSE。 稀疏語言會被叫做稀疏的原因是因為，對任何語言，長度為n的字串可能性個數總共有2n個，而如果某特定語言只有包含這一些字串裡面的多項式個數個，那這語言所包含字串的比例會隨著n的成長很快的減少。 所有一元語言都是稀疏語言。一個稀疏語言比較不單純的例子是，某個語言包含所有恰有k個1(k是某個常數)的二進位字串，; 對任何長度n, 這個語言僅包含\binomnk個字串, 而這個數字則被 nk給限制住。.
新！!: EXPTIME和稀疏語言 · 查看更多 »
DTIME
在計算複雜度理論內，DTIME（或者TIME）是一個圖靈機的計算資源或者計算時間的計量方式。它代表一個"普通"有實體的電腦解決特定計算問題，使用特定演算法，所要花費的時間。這個計算資源是最被廣泛研究的計算資源，因為它與真實世界所重視的資源（要花費多少時間才能計算出一個問題）息息相關。 DTIME這個資源常被使用來定義複雜度類，亦即，可以在特定時間內解決的決定性問題其集合。如果一個問題其輸入的大小為n，並且可要求f(n)的計算時間來解決，那我們說這問題在DTIME(f(n))（or TIME(f(n))）裡面。這裡沒有限制必須使用多少記憶體空間（參見計算資源），但是有可能會限制一些其他的計算資源（像是可否使用交替圖靈機）。.
新！!: EXPTIME和DTIME · 查看更多 »
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內。.
新！!: EXPTIME和EXPSPACE · 查看更多 »
非确定型图灵机
如果不加特殊说明，通常所说的图灵机都是确定型图灵机。非确定型图灵机和确定型图灵机的不同之处在于，在计算的每一时刻，根据当前状态和读写头所读的符号，机器存在多种状态转移方案，机器将任意地选择其中一种方案继续运作，直到最后停机为止。具体而言，其状态转移函数为 \delta: Q \times \Gamma \to 2^ 其中Q是状态集合，\Gamma是带字母表，L, R分别表示读写头向左和向右移动；符号2^ 表示集合A的幂集，即 2^A.
新！!: EXPTIME和非确定型图灵机 · 查看更多 »
計算複雜性理論
计算复杂性理论（Computational complexity theory）是理论计算机科学和数学的一个分支，它致力于将可计算问题根据它们本身的复杂性分类，以及将这些类别联系起来。一个可计算问题被认为是一个原则上可以用计算机解决的问题，亦即这个问题可以用一系列机械的数学步骤解决，例如算法。 如果一个问题的求解需要相当多的资源（无论用什么算法），则被认为是难解的。计算复杂性理论通过引入数学计算模型来研究这些问题以及定量计算解决问题所需的资源（时间和空间），从而将资源的确定方法正式化了。其他复杂性测度同样被运用，比如通信量（应用于通信复杂性），电路中门的数量（应用于电路复杂性）以及中央处理器的数量（应用于并行计算）。计算复杂性理论的一个作用就是确定一个能或不能被计算机求解的问题的所具有的实际限制。 在理论计算机科学领域，与此相关的概念有算法分析和可计算性理论。两者之间一个关键的区别是前者致力于分析用一个确定的算法来求解一个问题所需的资源量，而后者则是在更广泛意义上研究用所有可能的算法来解决相同问题。更精确地说，它尝试将问题分成能或不能在现有的适当受限的资源条件下解决这两类。相应地，在现有资源条件下的限制正是区分计算复杂性理论和可计算性理论的一个重要指标：后者关心的是何种问题原则上可以用算法解决。.
新！!: EXPTIME和計算複雜性理論 · 查看更多 »
邻接矩阵
邻接矩阵是表示一个图的常用存储表示。它用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。 距離矩陣可算是鄰接矩陣的擴充。.
新！!: EXPTIME和邻接矩阵 · 查看更多 »
集合
集合可以指：.
新！!: EXPTIME和集合 · 查看更多 »
NEXPTIME
在計算複雜度理論內，複雜度類NEXPTIME（有時叫做NEXP）是一個決定性問題的集合，包含可以使用非確定型圖靈機，使用O(2p(n))（這裡的p(n)是某個多項式）的時間可以解決的問題。另外這裡不限制空間的使用。 以NTIME作定義 一個很重要的NEXPTIME-完全問題集合與簡潔電路（succinct circuit）有關。簡潔電路是能以指數速率縮減的空間形容圖的一個機器。這個機器接收兩個頂點的號碼為輸入，輸出這兩個頂點是否有邊相連。如果有個問題，使用一般的圖表示法，像是連接矩陣，去解決時是個NP-完全問題，那麼使用簡潔電路的表示來解決這個問題是NEXPTIME-完全，因為輸入的大小跟前者相比是成指數速率縮小。舉個簡單的例子，使用簡潔電路的表示法找一張圖的哈密頓圖是NEXPTIME-完全。 如果'''P'''.
新！!: EXPTIME和NEXPTIME · 查看更多 »
NP (複雜度)
非定常多项式（non-deterministic polynomial，缩写：NP）时间复杂性类，或称非确定性多项式时间复杂性类，包含了可以在多项式时间内，对一个判定性算法问题的实例，一个给定的解是否正确的算法问题。 NP是计算复杂性理论中最重要的复杂性类之一。它包含复杂性类P，即在多项式时间内可以验证一个算法问题的实例是否有解的算法问题的集合；同时，它也包含NP完全问题，即在NP中“最难”的问题。计算复杂性理论的中心问题，P/NP问题即是判断对任意的NP完全问题，是否有有效的算法，或者NP与P是否相等。.
新！!: EXPTIME和NP (複雜度) · 查看更多 »
P (複雜度)
在計算複雜度理論中，P 是在複雜度類問題中可於決定性圖靈機以多項式量級（或稱多項式時間）求解的決定性問題。 P通常表示那類可以"有效率地解決"或"溫馴"的可計算型問題，就算指數級非常高也可以算作"溫馴"，例如RP與BPP問題。當然P類存在很多現實處理上一點也不溫馴的問題，例如一些至少需要n1000000指令來解決的問題。很多情況下存在著更難的複雜度問.
新！!: EXPTIME和P (複雜度) · 查看更多 »
P-完全
在計算複雜度理論內，標示了P-完全的決定型問題對於分析.
新！!: EXPTIME和P-完全 · 查看更多 »
P/NP问题
P/NP问题是在理论信息学中计算复杂度理论领域里至今未被解决的问题，也是克雷数学研究所七个千禧年大奖难题之一。P/NP问题中包含了复杂度类P与NP的关系。1971年史提芬·古克（Stephen A. Cook）和相对独立地提出了下面的问题，即复杂度类P和NP是否是恒等的（P.
新！!: EXPTIME和P/NP问题 · 查看更多 »
PSPACE
PSPACE是计算复杂度理论中能被确定型图灵机利用多项式空间解决的判定问题集合，是Polynomial SPACE的简称。.
新！!: EXPTIME和PSPACE · 查看更多 »
決定性問題
在可計算性理論與計算複雜性理論中，所謂的決定性問題（Decision problem）是一個在某些形式系統回答是或否的問題。例如：「給兩個數字x與y，x是否可以整除y？」便是決定性問題，此問題可回答是或否，且依據其x與y的值。 決定性問題與功能性問題（Function problem，或複雜型問題）密切相關，功能性問題的答案內容，較簡單的是與非複雜許多。範例問題：「給予一個正整數x，則哪些數可整除x？」 另一個與上述兩類問題相關的是最佳化問題（Optimization problem），此問題關心的是尋找特定問題的最佳答案。 解決決定性問題的方法稱為決策程式或演算法。一個針對決定性問題的演算法將說明給予參數x和y的情況下如何決定x是否整除y。若是某些決定性問題可以被一些演算法所解決，則稱此問題可決定。 計算複雜度的領域中，分類可決定問題的依據在於此問題有多難被解決。在此標準下，所謂的難是以解決某問題最有效率的演算法所花費的計算資源為依據。在遞迴理論中，非決定性問題由圖靈度決定，指的是一種在任何解答中隱含的不可計算性量詞。 計算性理論的研究集中在決定性問題上。在與功能性問題的等值問題中，並沒有失去其普遍性。.
新！!: EXPTIME和決定性問題 · 查看更多 »
指數譜系
在計算複雜性理論內，指數譜系是一個複雜度類的分類層級(hierarchy)，以EXPTIME開始： 然後接著 ，以下雷同。 我們已知P ⊂ EXPTIME ⊂ 2-EXPTIME ⊂ 3-EXPTIME ⊂ …。跟相類似的多項式譜系不同，時間譜系理論(Time hierarchy theorem)保證了這列關係都是真子集(proper)，意思是，存在語言在EXPTIME而不在P內，也存在語言在2-EXPTIME但不在EXPTIME內，以下類推。 將所有指數譜系的複雜度類作聯集，我們會得到一個大的複雜度類，名為ELEMENTARY。.
新！!: EXPTIME和指數譜系 · 查看更多 »
時間譜系理論
在計算複雜度理論內，時間譜系理論（Time hierarchy theorems）是一個有關圖靈機時間限制上面一個重要的理論。用不大正式的說法解釋，這理論告訴我們圖靈機在給予更多時間之後，保證能解決更多的問題。 舉例：必然存在問題是圖靈機可以用n2的時間解決，但是不能用n的時間解決。.
新！!: EXPTIME和時間譜系理論 · 查看更多 »
2-EXPTIME
在計算複雜度理論內，2-EXPTIME這個複雜度類 (有時寫作2-EXP)是在O(22p(n))時間內，可以使用決定型圖靈機解決掉決定型問題的集合，這裡 p(n) 是n的一個多項式 用DTIME的方式說明， 我們已經知道 2-EXPTIME也可以被重構成AEXPSPACE這個空間複雜度類(使用交替式圖靈機可以在指數空間內解決的問題)。因為交替式圖靈機至少有跟決定型圖靈機一樣的計算力，所以這也是一個看出EXPSPACE \subseteq 2-EXPTIME的方式。 2-EXPTIME這個複雜度類，是在一種可以不斷提昇時間上限的複雜度類層級裡面的其中一類。像3-EXPTIME 這個類別，類似於2-EXPTIME的定義方式，可以用三倍指數時間限制 2^來定義。用同樣的方法可以定義出更高的時間上限(4-EXP，5-EXP…之類)。.
新！!: EXPTIME和2-EXPTIME · 查看更多 »
重定向到这里：
EXP。
