之间多項式時間和非确定型图灵机相似
多項式時間和非确定型图灵机有(在联盟百科)4共同点: 图灵机,NP (複雜度),P (複雜度),P/NP问题。
图灵机
图灵机(),又称确定型图灵机,是英国数学家艾倫·图灵于1936年提出的一种抽象计算模型,其更抽象的意义为一种数学逻辑机,可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。.
图灵机和多項式時間 · 图灵机和非确定型图灵机 ·
NP (複雜度)
非定常多项式(non-deterministic polynomial,缩写:NP)时间复杂性类,或称非确定性多项式时间复杂性类,包含了可以在多项式时间内,对一个判定性算法问题的实例,一个给定的解是否正确的算法问题。 NP是计算复杂性理论中最重要的复杂性类之一。它包含复杂性类P,即在多项式时间内可以验证一个算法问题的实例是否有解的算法问题的集合;同时,它也包含NP完全问题,即在NP中“最难”的问题。计算复杂性理论的中心问题,P/NP问题即是判断对任意的NP完全问题,是否有有效的算法,或者NP与P是否相等。.
NP (複雜度)和多項式時間 · NP (複雜度)和非确定型图灵机 ·
P (複雜度)
在計算複雜度理論中,P 是在複雜度類問題中可於決定性圖靈機以多項式量級(或稱多項式時間)求解的決定性問題。 P通常表示那類可以"有效率地解決"或"溫馴"的可計算型問題,就算指數級非常高也可以算作"溫馴",例如RP與BPP問題。當然P類存在很多現實處理上一點也不溫馴的問題,例如一些至少需要n1000000指令來解決的問題。很多情況下存在著更難的複雜度問.
P (複雜度)和多項式時間 · P (複雜度)和非确定型图灵机 ·
P/NP问题
P/NP问题是在理论信息学中计算复杂度理论领域里至今未被解决的问题,也是克雷数学研究所七个千禧年大奖难题之一。P/NP问题中包含了复杂度类P与NP的关系。1971年史提芬·古克(Stephen A. Cook)和相对独立地提出了下面的问题,即复杂度类P和NP是否是恒等的(P.
上面的列表回答下列问题
- 什么多項式時間和非确定型图灵机的共同点。
- 什么是多項式時間和非确定型图灵机之间的相似性
多項式時間和非确定型图灵机之间的比较
多項式時間有14个关系,而非确定型图灵机有5个。由于它们的共同之处4,杰卡德指数为21.05% = 4 / (14 + 5)。
参考
本文介绍多項式時間和非确定型图灵机之间的关系。要访问该信息提取每篇文章,请访问: