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

PSPACE

指数 PSPACE

PSPACE是计算复杂度理论中能被确定型图灵机利用多项式空间解决的判定问题集合,是Polynomial SPACE的简称。.

18 关系: 劍橋大學出版社多項式上下文有关语言交互式证明系统交替式图灵机井号P传递闭包形式语言图灵机EXPSPACEEXPTIME萨维奇定理非确定型图灵机計算複雜性理論赫里斯托斯·帕帕季米特里乌NP (複雜度)P (複雜度)PSPACE

劍橋大學出版社

劍橋大學出版社(Cambridge University Press)隸屬於英國劍橋大學,成立於1534年,是世界上僅次於牛津大學出版社的第二大大學出版社。.

新!!: PSPACE和劍橋大學出版社 · 查看更多 »

多項式

多项式(Polynomial)是代数学中的基础概念,是由称为未知数的变量和称为系数的常数通过有限次加减法、乘法以及自然数幂次的乘方运算得到的代数表达式。多项式是整式的一种。未知数只有一个的多项式称为一元多项式;例如x^2-3x+4就是一个一元多项式。未知数不止一个的多项式称为多元多项式,例如就是一個三元多项式。 可以写成只由一项构成的多项式也称为单项式。如果一项中不含未知数,则称之为常数项。 多项式在数学的很多分支中乃至许多自然科学以及工程学中都有重要作用。.

新!!: PSPACE和多項式 · 查看更多 »

上下文有关语言

在理论计算机科学中,上下文有关语言是可被上下文有关文法定义的形式语言。它是乔姆斯基层级中的四类文法之一。当然它在理论和实践中都是最少使用的。.

新!!: PSPACE和上下文有关语言 · 查看更多 »

交互式证明系统

在计算复杂性理论中,交互式证明体系(下简称交互证明)是一类计算模型。像其它计算模型一样,我们的目标是对一个语言L,和一个给定的输入x,判断x是否在L中。交互式证明体系由两个实体:验证者(verifier)和证明者(prover)组成,两者都可以看作是某类图灵机。而它的计算过程为:给定了输入x,通过验证者和证明者之间交换信息,最终,由验证者来根据证明者给出的信息,判断给定的输入是不是在语言L中。 交互证明的基本假设是:证明者在计算能力上是无限的,在概率多项式时间的图灵机。一般来说,对给定的L,我们关注的是交互证明中验证者V这一角色,并对它加以如下的要求:.

新!!: PSPACE和交互式证明系统 · 查看更多 »

交替式图灵机

交替式图灵机(, ATM)是计算复杂度理论中定义的一种非确定型图灵机(NTM)。与一般非确定型图灵机不同,交替式图灵机将接受语言的规则一般化到NP和反NP。交替式图灵机的概念由Chandra和于1976年提出。.

新!!: PSPACE和交替式图灵机 · 查看更多 »

井号P

在计算复杂性理论中,#P(英文读作sharp P,中文暂称为井号P,推荐读为计数P)是一组与NP中的判定性问题相关的计数问题。.

新!!: PSPACE和井号P · 查看更多 »

传递闭包

傳遞閉包、即在数学中,在集合 X 上的二元关系 R 的传递闭包是包含 R 的 X 上的最小的传递关系。 例如,如果 X 是(生或死)人的集合而 R 是关系“为父子”,则 R 的传递闭包是关系“x 是 y 的祖先”。再比如,如果 X 是空港的集合而关系 xRy 为“从空港 x 到空港 y 有直航”,则 R 的传递闭包是“可能经一次或多次航行从 x 飞到 y”。.

新!!: PSPACE和传递闭包 · 查看更多 »

形式语言

在数学、逻辑和计算机科学中,形式语言(Formal language)是用精确的数学或机器可处理的公式定义的语言。 如语言学中语言一样,形式语言一般有两个方面: 语法和语义。专门研究语言的语法的数学和计算机科学分支叫做形式语言理论,它只研究语言的语法而不致力于它的语义。在形式语言理论中,形式语言是一个字母表上的某些有限长字符串的集合。一个形式语言可以包含无限多个字符串。.

新!!: PSPACE和形式语言 · 查看更多 »

图灵机

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

新!!: PSPACE和图灵机 · 查看更多 »

EXPSPACE

在計算複雜度理論內,EXPSPACE是一個包含可以在O(2p(n))空間內解決的決定性問題的集合,這裡的p(n)是某個n的多項式。(有些作者認為p(n)應該限制為線性函數,但是多數的人把這這樣的複雜度類稱作ESPACE。)如果我們使用非決定性圖靈機,我們會得到複雜度類NEXPSPACE。根據薩維奇定理,這個複雜度類等同EXPSPACE。 以DSPACE和NSPACE表示: 我們說一個問題是EXPSPACE-完全,如果這問題本身在EXPSPACE內,而且存在多項式多對一歸約,令所有在EXPSPACE內的題目都可以歸約成這個題目。換句話說,存在一個多項式時間的演算法可以將一個狀況換成其他題目的另一個狀況,並且答案一樣。EXPSPACE-完全的題目也可以想做是EXPSPACE裡面最難的題目。 EXPSPACE是PSPACE,NP,和P的嚴格母集(前者包含且不等於後者)。並且也被相信是EXPTIME的嚴格母集。 一個EXPSPACE-完全的例子是分辨兩個正規表式是否是一樣的語言這個問題。這裡的表示限制使用四種操作子:聯集,串街,克萊尼星號(可以是零個或多個重複的表示式),和平方(兩份表示式)。 如果我們排除星號,則這個問題變成NEXPTIME-完全,這個複雜度類有點類似EXPTIME-完全,不過使用的機器是非決定性圖靈機而非一般的圖靈機。 L. Berman在1980年證明了,證明或反證任何有關實數並且牽涉加法和比較大小(但不牽涉乘法)的一階陳述,這個問題在EXPSPACE內。.

新!!: PSPACE和EXPSPACE · 查看更多 »

EXPTIME

在計算複雜性理論裡面,EXPTIME(有時稱作EXP)這個複雜度類是一些決定型問題的集合,這些問題可以使用圖靈機在O(2p(n))的時間內解決,這裡的p(n)代表的是n的某個多項式。 用DTIME來定義,則是 我們已經知道 另外,根據時間譜系理論(time hierarchy theorem)以及空間譜系理論(space hierarchy theorem), 所以至少第一條包含關係中,前三個包含關係中的一個,以及後三個包含關係中的一個,必然是完整包含(沒有相等可能),但是我們還不知道那一個是。多數人相信這一些複雜度類全部都不相等。另外我們已知如果,則,這裡的NEXPTIME是在指數時間內可以使用非確定型圖靈機解決的問題。更精確的說,EXPTIME ≠ NEXPTIME若且唯若存在一個稀疏語言,在NP裡面且不在P內。 EXPTIME也可以用空間的方式來定義,等同於APSPACE這個複雜度類。APSPACE的意思是包含了所有可以用交替式圖靈機在多項式空間內解決的問題。這種定義方式也是一種看出PSPACE \subseteq EXPTIME的方式,因為已知交替式圖靈機至少跟確定型圖靈機計算能力一樣。 EXPTIME是指數譜系(exponential hierarchy)內的其中一個複雜度類。2-EXPTIME這個複雜度類則使用類似EXPTIME的定義方式,但是使用雙指數函數(Double exponential function)的時間限制2^。使用類似方式可以類推出更高的時間上限。.

新!!: PSPACE和EXPTIME · 查看更多 »

萨维奇定理

萨维奇定理()是计算复杂性理论中的一个定理,由沃尔特·萨维奇(Walter Savitch)于1970年证明。定理的结论为对于任何函数f(n)满足f(n)\geq \log n,下列关系成立: 亦即,如果一台非确定型图灵机能够利用f(n)空间解决某个问题,那么一台确定型图灵机能够在至多f^2(n)空间解决相同的问题。尽管非确定性的引入能够在时间上带来指数的提升,但是,这种引入对于空间而言作用有限。.

新!!: PSPACE和萨维奇定理 · 查看更多 »

非确定型图灵机

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

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

計算複雜性理論

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

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

赫里斯托斯·帕帕季米特里乌

赫里斯托斯·哈里劳斯·帕帕季米特里乌(Χρίστος Χαρίλαος Παπαδημητρίου,羅馬化:Christos Harilaos Papadimitriou,)是一名生於希臘的電腦科學家,現任教於柏克萊加州大學。帕帕季米特里乌在演算法領域做出研究,並曾先後任教於哈佛大學、麻省理工學院、國立雅典理工大學、史丹佛大學、聖地牙哥加利福尼亞大學、與柏克萊加州大學。.

新!!: PSPACE和赫里斯托斯·帕帕季米特里乌 · 查看更多 »

NP (複雜度)

非定常多项式(non-deterministic polynomial,缩写:NP)时间复杂性类,或称非确定性多项式时间复杂性类,包含了可以在多项式时间内,对一个判定性算法问题的实例,一个给定的解是否正确的算法问题。 NP是计算复杂性理论中最重要的复杂性类之一。它包含复杂性类P,即在多项式时间内可以验证一个算法问题的实例是否有解的算法问题的集合;同时,它也包含NP完全问题,即在NP中“最难”的问题。计算复杂性理论的中心问题,P/NP问题即是判断对任意的NP完全问题,是否有有效的算法,或者NP与P是否相等。.

新!!: PSPACE和NP (複雜度) · 查看更多 »

P (複雜度)

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

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

PSPACE

PSPACE是计算复杂度理论中能被确定型图灵机利用多项式空间解决的判定问题集合,是Polynomial SPACE的简称。.

新!!: PSPACE和PSPACE · 查看更多 »

重定向到这里:

NPSPACE多项式空间

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