之间E (複雜度)和EXPTIME相似
E (複雜度)和EXPTIME有(在联盟百科)3共同点: 复杂性类,DTIME,決定性問題。
复杂性类
在計算複雜度理論中,一個複雜度類指的是一群複雜度類似的問題的集合。一個典型的複雜度類的定義有以下--: 例如'''NP'''類就是一群可以被一非確定型圖靈機以多項式時間解決的決定型問題。而P類則是一群可以被確定型圖靈機以多項式時間解決的決定型問題。某些複雜度類是一群函式問題(Function problem)的集合,例如'''FP'''。 許多複雜度類可被描述它的數學邏輯(mathematical logic)特徵化,請見可描述的複雜度(descriptive complexity)。 而Blum公理用於不需實際計算模型就可定義複雜度類的情況。.
DTIME
在計算複雜度理論內,DTIME(或者TIME)是一個圖靈機的計算資源或者計算時間的計量方式。它代表一個"普通"有實體的電腦解決特定計算問題,使用特定演算法,所要花費的時間。這個計算資源是最被廣泛研究的計算資源,因為它與真實世界所重視的資源(要花費多少時間才能計算出一個問題)息息相關。 DTIME這個資源常被使用來定義複雜度類,亦即,可以在特定時間內解決的決定性問題其集合。如果一個問題其輸入的大小為n,並且可要求f(n)的計算時間來解決,那我們說這問題在DTIME(f(n))(or TIME(f(n)))裡面。這裡沒有限制必須使用多少記憶體空間(參見計算資源),但是有可能會限制一些其他的計算資源(像是可否使用交替圖靈機)。.
DTIME和E (複雜度) · DTIME和EXPTIME ·
決定性問題
在可計算性理論與計算複雜性理論中,所謂的決定性問題(Decision problem)是一個在某些形式系統回答是或否的問題。例如:「給兩個數字x與y,x是否可以整除y?」便是決定性問題,此問題可回答是或否,且依據其x與y的值。 決定性問題與功能性問題(Function problem,或複雜型問題)密切相關,功能性問題的答案內容,較簡單的是與非複雜許多。範例問題:「給予一個正整數x,則哪些數可整除x?」 另一個與上述兩類問題相關的是最佳化問題(Optimization problem),此問題關心的是尋找特定問題的最佳答案。 解決決定性問題的方法稱為決策程式或演算法。一個針對決定性問題的演算法將說明給予參數x和y的情況下如何決定x是否整除y。若是某些決定性問題可以被一些演算法所解決,則稱此問題可決定。 計算複雜度的領域中,分類可決定問題的依據在於此問題有多難被解決。在此標準下,所謂的難是以解決某問題最有效率的演算法所花費的計算資源為依據。在遞迴理論中,非決定性問題由圖靈度決定,指的是一種在任何解答中隱含的不可計算性量詞。 計算性理論的研究集中在決定性問題上。在與功能性問題的等值問題中,並沒有失去其普遍性。.
上面的列表回答下列问题
- 什么E (複雜度)和EXPTIME的共同点。
- 什么是E (複雜度)和EXPTIME之间的相似性
E (複雜度)和EXPTIME之间的比较
E (複雜度)有6个关系,而EXPTIME有22个。由于它们的共同之处3,杰卡德指数为10.71% = 3 / (6 + 22)。
参考
本文介绍E (複雜度)和EXPTIME之间的关系。要访问该信息提取每篇文章,请访问: