徽标
联盟百科
通讯
下载应用,请到 Google Play
新! 在您的Android™设备上下载联盟百科!
自由
比浏览器更快的访问!
 

NL完全

指数 NL完全

在计算复杂性理论中,NL完全是由全体对NL类完备的语言构成的复杂性类。也就是说,NL完全的语言是NL类中最“难解”和最“有力”的语言。如果有某个确定性的方法可以在对数空间内解决一个NL完全问题,那么就会有NL.

6 关系: 复杂性类图灵机非确定型图灵机計算複雜性理論L (複雜度)P (複雜度)

复杂性类

在計算複雜度理論中,一個複雜度類指的是一群複雜度類似的問題的集合。一個典型的複雜度類的定義有以下--: 例如'''NP'''類就是一群可以被一非確定型圖靈機以多項式時間解決的決定型問題。而P類則是一群可以被確定型圖靈機以多項式時間解決的決定型問題。某些複雜度類是一群函式問題(Function problem)的集合,例如'''FP'''。 許多複雜度類可被描述它的數學邏輯(mathematical logic)特徵化,請見可描述的複雜度(descriptive complexity)。 而Blum公理用於不需實際計算模型就可定義複雜度類的情況。.

新!!: NL完全和复杂性类 · 查看更多 »

图灵机

图灵机(),又称确定型图灵机,是英国数学家艾倫·图灵于1936年提出的一种抽象计算模型,其更抽象的意义为一种数学逻辑机,可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。.

新!!: NL完全和图灵机 · 查看更多 »

非确定型图灵机

如果不加特殊说明,通常所说的图灵机都是确定型图灵机。非确定型图灵机和确定型图灵机的不同之处在于,在计算的每一时刻,根据当前状态和读写头所读的符号,机器存在多种状态转移方案,机器将任意地选择其中一种方案继续运作,直到最后停机为止。具体而言,其状态转移函数为 \delta: Q \times \Gamma \to 2^ 其中Q是状态集合,\Gamma是带字母表,L, R分别表示读写头向左和向右移动;符号2^ 表示集合A的幂集,即 2^A.

新!!: NL完全和非确定型图灵机 · 查看更多 »

計算複雜性理論

计算复杂性理论(Computational complexity theory)是理论计算机科学和数学的一个分支,它致力于将可计算问题根据它们本身的复杂性分类,以及将这些类别联系起来。一个可计算问题被认为是一个原则上可以用计算机解决的问题,亦即这个问题可以用一系列机械的数学步骤解决,例如算法。 如果一个问题的求解需要相当多的资源(无论用什么算法),则被认为是难解的。计算复杂性理论通过引入数学计算模型来研究这些问题以及定量计算解决问题所需的资源(时间和空间),从而将资源的确定方法正式化了。其他复杂性测度同样被运用,比如通信量(应用于通信复杂性),电路中门的数量(应用于电路复杂性)以及中央处理器的数量(应用于并行计算)。计算复杂性理论的一个作用就是确定一个能或不能被计算机求解的问题的所具有的实际限制。 在理论计算机科学领域,与此相关的概念有算法分析和可计算性理论。两者之间一个关键的区别是前者致力于分析用一个确定的算法来求解一个问题所需的资源量,而后者则是在更广泛意义上研究用所有可能的算法来解决相同问题。更精确地说,它尝试将问题分成能或不能在现有的适当受限的资源条件下解决这两类。相应地,在现有资源条件下的限制正是区分计算复杂性理论和可计算性理论的一个重要指标:后者关心的是何种问题原则上可以用算法解决。.

新!!: NL完全和計算複雜性理論 · 查看更多 »

L (複雜度)

L也稱為LSPACE或DLOGSPACE,是计算复杂度理论中能被确定型图灵机利用對數空间解决的判定问题集合。, Definition 8.12, p. 295.

新!!: NL完全和L (複雜度) · 查看更多 »

P (複雜度)

在計算複雜度理論中,P 是在複雜度類問題中可於決定性圖靈機以多項式量級(或稱多項式時間)求解的決定性問題。 P通常表示那類可以"有效率地解決"或"溫馴"的可計算型問題,就算指數級非常高也可以算作"溫馴",例如RP與BPP問題。當然P類存在很多現實處理上一點也不溫馴的問題,例如一些至少需要n1000000指令來解決的問題。很多情況下存在著更難的複雜度問.

新!!: NL完全和P (複雜度) · 查看更多 »

传出传入
嘿!我们在Facebook上吧! »