之间PH (複雜度)和RP (複雜度)相似
PH (複雜度)和RP (複雜度)有(在联盟百科)4共同点: 反NP,复杂性类,NP (複雜度),P (複雜度)。
反NP
在計算複雜度理論上,反NP類是複雜度類的其中一類。.
复杂性类
在計算複雜度理論中,一個複雜度類指的是一群複雜度類似的問題的集合。一個典型的複雜度類的定義有以下--: 例如'''NP'''類就是一群可以被一非確定型圖靈機以多項式時間解決的決定型問題。而P類則是一群可以被確定型圖靈機以多項式時間解決的決定型問題。某些複雜度類是一群函式問題(Function problem)的集合,例如'''FP'''。 許多複雜度類可被描述它的數學邏輯(mathematical logic)特徵化,請見可描述的複雜度(descriptive complexity)。 而Blum公理用於不需實際計算模型就可定義複雜度類的情況。.
PH (複雜度)和复杂性类 · RP (複雜度)和复杂性类 ·
NP (複雜度)
非定常多项式(non-deterministic polynomial,缩写:NP)时间复杂性类,或称非确定性多项式时间复杂性类,包含了可以在多项式时间内,对一个判定性算法问题的实例,一个给定的解是否正确的算法问题。 NP是计算复杂性理论中最重要的复杂性类之一。它包含复杂性类P,即在多项式时间内可以验证一个算法问题的实例是否有解的算法问题的集合;同时,它也包含NP完全问题,即在NP中“最难”的问题。计算复杂性理论的中心问题,P/NP问题即是判断对任意的NP完全问题,是否有有效的算法,或者NP与P是否相等。.
NP (複雜度)和PH (複雜度) · NP (複雜度)和RP (複雜度) ·
P (複雜度)
在計算複雜度理論中,P 是在複雜度類問題中可於決定性圖靈機以多項式量級(或稱多項式時間)求解的決定性問題。 P通常表示那類可以"有效率地解決"或"溫馴"的可計算型問題,就算指數級非常高也可以算作"溫馴",例如RP與BPP問題。當然P類存在很多現實處理上一點也不溫馴的問題,例如一些至少需要n1000000指令來解決的問題。很多情況下存在著更難的複雜度問.
上面的列表回答下列问题
- 什么PH (複雜度)和RP (複雜度)的共同点。
- 什么是PH (複雜度)和RP (複雜度)之间的相似性
PH (複雜度)和RP (複雜度)之间的比较
PH (複雜度)有12个关系,而RP (複雜度)有13个。由于它们的共同之处4,杰卡德指数为16.00% = 4 / (12 + 13)。
参考
本文介绍PH (複雜度)和RP (複雜度)之间的关系。要访问该信息提取每篇文章,请访问: