之间DTIME和EXPTIME相似
DTIME和EXPTIME有(在联盟百科)6共同点: 复杂性类,图灵机,非确定型图灵机,P (複雜度),決定性問題,時間譜系理論。
复杂性类
在計算複雜度理論中,一個複雜度類指的是一群複雜度類似的問題的集合。一個典型的複雜度類的定義有以下--: 例如'''NP'''類就是一群可以被一非確定型圖靈機以多項式時間解決的決定型問題。而P類則是一群可以被確定型圖靈機以多項式時間解決的決定型問題。某些複雜度類是一群函式問題(Function problem)的集合,例如'''FP'''。 許多複雜度類可被描述它的數學邏輯(mathematical logic)特徵化,請見可描述的複雜度(descriptive complexity)。 而Blum公理用於不需實際計算模型就可定義複雜度類的情況。.
图灵机
图灵机(),又称确定型图灵机,是英国数学家艾倫·图灵于1936年提出的一种抽象计算模型,其更抽象的意义为一种数学逻辑机,可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。.
DTIME和图灵机 · EXPTIME和图灵机 ·
非确定型图灵机
如果不加特殊说明,通常所说的图灵机都是确定型图灵机。非确定型图灵机和确定型图灵机的不同之处在于,在计算的每一时刻,根据当前状态和读写头所读的符号,机器存在多种状态转移方案,机器将任意地选择其中一种方案继续运作,直到最后停机为止。具体而言,其状态转移函数为 \delta: Q \times \Gamma \to 2^ 其中Q是状态集合,\Gamma是带字母表,L, R分别表示读写头向左和向右移动;符号2^ 表示集合A的幂集,即 2^A.
DTIME和非确定型图灵机 · EXPTIME和非确定型图灵机 ·
P (複雜度)
在計算複雜度理論中,P 是在複雜度類問題中可於決定性圖靈機以多項式量級(或稱多項式時間)求解的決定性問題。 P通常表示那類可以"有效率地解決"或"溫馴"的可計算型問題,就算指數級非常高也可以算作"溫馴",例如RP與BPP問題。當然P類存在很多現實處理上一點也不溫馴的問題,例如一些至少需要n1000000指令來解決的問題。很多情況下存在著更難的複雜度問.
DTIME和P (複雜度) · EXPTIME和P (複雜度) ·
決定性問題
在可計算性理論與計算複雜性理論中,所謂的決定性問題(Decision problem)是一個在某些形式系統回答是或否的問題。例如:「給兩個數字x與y,x是否可以整除y?」便是決定性問題,此問題可回答是或否,且依據其x與y的值。 決定性問題與功能性問題(Function problem,或複雜型問題)密切相關,功能性問題的答案內容,較簡單的是與非複雜許多。範例問題:「給予一個正整數x,則哪些數可整除x?」 另一個與上述兩類問題相關的是最佳化問題(Optimization problem),此問題關心的是尋找特定問題的最佳答案。 解決決定性問題的方法稱為決策程式或演算法。一個針對決定性問題的演算法將說明給予參數x和y的情況下如何決定x是否整除y。若是某些決定性問題可以被一些演算法所解決,則稱此問題可決定。 計算複雜度的領域中,分類可決定問題的依據在於此問題有多難被解決。在此標準下,所謂的難是以解決某問題最有效率的演算法所花費的計算資源為依據。在遞迴理論中,非決定性問題由圖靈度決定,指的是一種在任何解答中隱含的不可計算性量詞。 計算性理論的研究集中在決定性問題上。在與功能性問題的等值問題中,並沒有失去其普遍性。.
時間譜系理論
在計算複雜度理論內,時間譜系理論(Time hierarchy theorems)是一個有關圖靈機時間限制上面一個重要的理論。用不大正式的說法解釋,這理論告訴我們圖靈機在給予更多時間之後,保證能解決更多的問題。 舉例:必然存在問題是圖靈機可以用n2的時間解決,但是不能用n的時間解決。.
上面的列表回答下列问题
- 什么DTIME和EXPTIME的共同点。
- 什么是DTIME和EXPTIME之间的相似性
DTIME和EXPTIME之间的比较
DTIME有15个关系,而EXPTIME有22个。由于它们的共同之处6,杰卡德指数为16.22% = 6 / (15 + 22)。
参考
本文介绍DTIME和EXPTIME之间的关系。要访问该信息提取每篇文章,请访问: