（计算机软件与理论专业论文）基于概率图灵机模型的复杂性类.pdf

摘要本文主要基于概率图灵机，研究随机复杂性类和交互式证明系统i i ，的一些有趣的 问题。概率工具在复杂性的研究中不仪是一个很有用的工具，同时也提出了新的研究课 题。所谓概率图灵机，它除了正常的输入以外，还具有投掷硬币的能力；最终的输出和 输入及掷硬币得到的随机串都有关。在这样的模型下，理论科学家们定义了一些相应的 语言类- - b p p ，z p p ，r p ，p p 。 交互式证明系统有两个很重要的特点一交互性和随机性。验证方的计算能力是多项 式的概率图灵机。证明方的能力不限，提供相应的证据给验证方。对于不同的输入，证 明方能够以4 i 同的概率去说服验证方；根据验证方被说服的概率，我们可以区分开一个 语言和它的补集，从而交互式证明系统接受了这个语言 本文首先介绍了复杂性研究中常用的模型和基本概念，对概率图灵机和交互式证 明系统做了基本的介绍。第二部分基于概率图灵机，给出了r p 的定义s d n p 的另外一 种定义：然后介绍z p p $ 1 p p 的等价定义；最后，详细讨论了两个介于b p p $ 口p p 之间的 语言类。第三部分对图不同构问题进行研究，提出了一个p e r f e c ta r t h u r m e r l i ng a m e s f p a m ) 协议。其中用到的主要丁具是i s o l a t i o n 定理，定理的证明会在附录中给出。第四 部分介绍了带竞争的证明系统岛，首先给出了b p p s 2 的另外一种证明，然后证明 了p s p a c e p p o l y = p s p a c e s 2 k e y w o r d s ： 概率图灵机，扩大法，交互式证明系统，a r t h u r m e r l i n 证明系统，图不同构问题，带竞 争的证明系统，i s o l a t i o n 定理，动态测试，c h e r n o f fb o u n d a b s t r a c tt h i st h e s i sf o c u s e so nt h el a n g u a g e sa n dp r o b l e m sb a s e do np r o b a b i l i s t i ct u r - i n gm a c h i n e ，a sw e l la si n t e r a c t i v ep r o o fs y s t e m s p r o b a b i l i s t i cm e t h o di sap o w e r f u l t o o l ，a n di tp r o v i d e sn e ws u b j e c t st os t u d y f o rp r o b a b i l i s t i ct u r i n gm a c h i n e ，b e s i d e s t h ef u n c t i o n so fn o r m a l1 h r i n gm a c h i n e ，i th a se x t r aa b i l i t y t o s sc o i n s t h e o u t p u t a n db e h a v eo fp r o b a b i l i s t i cn r i n gm a c h i n ew e r ed e t e r m i n e db yb o t hi n p u ta n dr a n d o m s t r i n g b a s e do nr a n d o m i z e dc o m p u t a t i o n s ，m a n yr a n d o ml a n g u a g ec l a s s e sw e r e d e f i n e d ，s u c ha sb p p ，z p p ，r p ，p pe t c a st oi n t e r a c t i v ep r o o fs y s t e n l st h e r ea r et w o i m p o r t a n tr o l e s - - r a n d o m n e s sa n d i n t e r a c t i o n w ee m p h a s i z i n gr a n d o m n e s s f i r s tt h i st h e s i si n t r o d u c es o m eb a s i cn o t i o n sa n dm o d e l sa b o u tc o m p l e x i t y , i n c l u d i n gt h ep r o b a b i l i s t i ct u r i n gm a c h i n e ( p t m ) a n d i n t e r a c t i v ep r o o fs y s t e m s i nt h e s e c o n dp a r t b a s e do np t m w ei n t r o d u c et h ed e n n i t i o no fn pa n de q u i v a l e n td e f i n i t i o n s a b o u tr pa n dz p p ；t h e nt w ol a n g u a g ec l a s s e sb e t w e e nb p pa n dp pw i l lb ed i s c u s s e d i nt h et h i r dp a r t ，w eg i v ea ne x a m p l ea b o u ti n t e r a c t i v ep r o o fs y s t e m s - - g r a p hn o n i s o m o r p h i cp r o b l e m ；m o r e o v e r ，w ei n t r o d u c e dt h ei d e ao fa r t h u rm e r l i ng a m e sa n d p e r f e c ta r t h u rm e r l i ng a n m s ( p a m ) ；f i n a l l yw eg i v eap a mp r o t o c o la b o u tg r a p h n o n i s o m o r p h i cp r o b l e m i nt h ef o r t hp a r tt h ec o n c e p to fs 2w i l lb ed i s c u s s e d ；t h e nw e g i v ea n o t h e rp r o o f o fb p p c 岛；ap o w e r f u lt o o l d y n a m i cc o n t e s ta b o u t & w i l l b e i n t r o d u c e d u s i n g t h et o o l l w ep r o v e dt h a ti f p s p a c e c p p o l y ，t h e n p s p a c e s 2 k e y w o r d s ： p r o b a b i l i s t i ct u r i n gm a c h i n e ，a m p l i f ym e t h o d ，i n t e r a c t i v ep r o o fs y s t e m s ，a r t h u r m e r l i ng a m e s ，g r a p hn o n - i s o m o r p h i cp r o b l e m ，岛，i s o l a t i o nl e m m a ，c h e r n o f fb o u n d ， d y n a m i c c o n t e s t 2 第一章 已i 言 ji 口 1 1 复杂性研究的历史 人们对计算理论的研究起源于上个世纪初。在1 9 0 0 年崮际数学家大会上，希尔波 特( h i l b e r t ) 提出了著名的2 3 个世纪难题。其中第十个问题是：找到一个系统化的程序， 判定一个整系数多变元的多项式是否有整数解。更进一步，希尔波特开始了对判定问题 的研究，研究的目标是找到一个算法来判定一个问题的所有实例。而希尔波特的第十个 问题就是图灵的下作的出发点，图灵提出了著名的计算模型一一图灵机，从而奠定了计 算理论的基础。在解决希尔波特的问题的过程中，可计算理论诞生了。 h a r t m a n i s $ 1 s t e a r n s 在1 9 6 5 年最先开始了复杂性理论的研究，2 0 1 ，在他们共同发 表了篇文章里，提出计算机在更多的时间内能做更多的事情。他们不仅仅研究个 问题是否可以计算，而且迸一步研究一个问题能在多少代价内计算。之后，c o o k 给出 了p 的定义，也就是我们现在所熟知的”能在多项式时问内判定的所有语言类的集合”。 非确定计算的模型起源于有限自动机和下推自动机基于非确定的计算模型，人们 给出t n p 的定义。c o o kf 1 0 1 首先提出并证明了一个自然的n p 完全问题一可满足问 题，k e a p 【2 2 1 迸一步证明了很多组合问题都是n p 完全的。如今p 是否等于n p 是复杂性 理论里最重要的一个问题，已经成为了一个千年难题。 s 0 1 0 v a y 和s t r s e n 2 9 1 在1 9 7 7 年设计了。个概率多项式的算法来测试一个数是否是 素数，他们的工作开创个新的天地，就是概率计算模型。g i l l 1 2 1 定义了概率多项式 时间内接受的语言类一- - b p p 。从此随机复杂性类在复杂性领域也占有了席之地，概 率方法也成为了复杂性研究个很重要的_ 具。 交互式证明系统从开始就与复杂性的研究有非常密切的关系。1 9 8 5 年，g o l d w a s s e r ， i 引言 m i c a l i $ 日r a c k o f f 【1 3 共同提出了交互式证明系统的模型。同样在1 9 8 5 年，b a h a i 1 2 】引入 a r t h u r m e r l i n 证明系统， 。个带有公共随机串的交互式证明系统。1 9 9 6 肆：，m i t 限j 三个学生在改进b p p p 日的证明h 提出了一个有竞争的证明系统s 2 。s 2 作为个 很有趣的模型，吸引了很多注意。到目前为止，关于s 2 最重要的工作包括【5 】和 6 1 。 1 2 计算模型一图灵机( t l l r i n gm a c h i n e ) 简单来说，图灵机是这样的一个模型：它包括输入带，输出带，及若干工作带；每条带 上都有相应的读写头，在带上可以读出或者写入一些字符，这些字符是属于某个字母 表；图灵机还包括一个有限的状态控制系统。 在本文一 j ，所有的字母表= o ，1 ，所有的对数函数都以2 为底。我们用p 。z 来表 示所有多项式函数的集合。 定义1 1 严格来说，图灵机包括以下几个部分： 1 有限个状态的集合q ； 2 初始状态q o q ； 3 接受状态集合f q ； 4 带字母表r 、； 5 输入字母表，r b ，b 是一个特殊的空自字符。 6 状态转移函数d ，6 是一个部分函数：( q f ) r - 一q f ( l ，r ) ； 图灵机的每一步运行有以下几种可能的操作： 在读写头所在的位置读入个字符： 在读写头所在的位置写入个字符； 向左或者向右移动读写头； 改变当前的状态； 每次运行，图灵机首先进行在读写头当前位置的读入一个字符，根据凄取的字符和 当前的状态，参照状态转移函数，来确定是否需要写入字符，写入哪个字符：是否移动 2 1 引言 读写头并且往那个方向移动；改变当前的状态到哪一个新的状态1 。需要注意的是，状 态转移函数是个部分函数。 知道了图灵机的运行规则，我们可以讨论图灵机是如何接受个语言或者计算一 个函数了。以接受一个语占为例，初始时，输入串u 是放在输入带上，其他带的内容 均为空。图灵机的状态为初始状态帅，读写头停在输入带上输入串的最左边的字符。 每次图灵机根据读写头读入的字符和当前的状态，来决定采取那些操作。这样一直继 续，或者图灵机永不停机，或者图灵机读入的字符s 和当前的状态口在状态转移函数中没 有定义( 即6 ( 吼s ) 没定义) 。在这种情况里，我们认为图灵机拒绝了u ，即图灵机认为u 不 属于这个语言类。而如果图灵机最终停机并且进入了个接受状态，我们认为图灵机 接受了u ，即图灵机认为u 属于这个语苦类。图灵机接受个语言l ，当且仪当对于所有 的u l ，图灵机接受u 。 我们在前面讨论过，图灵机是非常重要的计算模型。它很简单，但是能力非常强。 下面的c h u r c h - 1 5 1 r i n g 命题证明了这点。 定理11c h u r c ht u r i n g 命题：任何一个可咀被台理的计算模型计算( 接受) 的函数( 语 言) 都能被图灵机所计算f 接受) 。 还有一类很重要的计算模型必须要提到的一非确定图灵机( n o n d e t e r m i n i s t i ct u r i n gm a c h i n e ) 。前面我们介绍的是一般称之为( 确定) 图灵机( d e t e r m i n i s t i ct u r i n gm a - c h i n e l 。非确定图灵机和确定图灵机很类似，区别在于状态转移函数。非确定图灵机的 状态转移函数是一个集合( q f ) r q r l ，r 。每个五元2 l t ( q l ，8 1 ，啦，s 2 ，d ) 对 应了图灵机一步可能的运行。同样的( q 1 ，s 1 ) 可能对应于多个( 啦，s 2 ，d ) ，也就是说图灵 机的每个当前状态都可能会有多个可能的运行，进入多个可能的后继状态。 这样我们可以把非确定图灵机的运行看作是一颗计算树，每个分支对应于非确定圈 灵机对这个输入可能的一系列运行。那么我们说非确定图灵机接受一个输入u ，是指在 这个树中，至少有一个分支停机并且最终进入了接受状态。同样，非确定图灵机接受。 个语音，当且仪当所有的u l ，图灵机接受u 。 关于这些模型的详细的定义，可以参阅1 1 。 1 3 时间和空间代价 复杂性理论不仪要关心到一个语苦是否可以被所接受，更要关心的是能以多少的代价 被接受。我们通常所指的代价包括时间，空间。在概率图灵机模型下面还需要考虑随 3 1 引言 机串的长度，在交互式的证明系统中就必须考虑交互的次数。这些都是我们衡量一个 语言类难度的重要的标准。作为理论计算机科学家而言，证明。个问题容易很重要， 但是更重要的是证明个问题很难，即在给定的代价条件下4 i 能被解决。这类问题就 是常说的s e p e r a t i o n l 日题，也就是我们证明一个语言类和另外个语言类之间互不相 等，这样更难的语言类中的部分问题不能以较低的资源解决。很遗憾的是，目前这方面 的工作进展甚微，成果也不多；而且未解决的问题中大部分都是非常难。最著名的就 是p p 的问题。如果这个基本的问题得到了解决，复杂性理论的研究将会进入一个 全新的阶段。 在前面我们已经讨论过了确定图灵机和非确定图灵机的运行及接受一个语言的规 则，下面我们将要讨论( - t p 确定) 图灵机所需要的资源和根据所需要的资源我们对语言进 行的一些分类。 图灵机的计算复杂度是指图灵机在计算过程中所需要的资源的多少，一个语言的计 算复杂度是指所有接受这个语言的图灵机中，复杂度最低的那个图灵机所需要的资源的 多少。如前所诉，对于图灵机而言，最重要的资源是时间和空间。 下面我们给出确定图灵机的时间和空间复杂度的定义。令m 为一个确定图灵机， 对于任一字符串x ，m 对于x 所需要的运行时间是从开始到停机m 运行的步数，标记 ：t j t i m e m ( x ) 。我们令t m ( n ) = m a x t i m e m ( x ) ：对于所有h = n ) 。我们就能比较两 个图灵机的时问复杂度，是说对这两个图灵机m ，m ；我们比较函数t m ( n ) t m ，( n ) ， 当n 趋向于无穷大时它们增长的速度，我们说图灵机m 的时间复杂度更低，是指当n 趋向 于无穷大时，n f ( n ) 增长的速度更慢。 类似的，我们给出空间复杂度的定义。只不过我们在考虑空间复杂度时，图灵机的 模型散为三带图灵机( 输入带，输出带和工作带) 。计算空间复杂度时只考虑工作带 上所用的空间。同样我们也可以给出s p a c e m ( x ) i l s m ( n ) 的定义。比较两个图灵机的空 间复杂度是通过比较s m ( n ) 当n 趋向于无穷大时增长的速度。 有了时间和空间复杂度的定义，我们就能对语言进行分类： 定义1 2 令t ：n n 是定义在整数上的函数。c 表示一组这样的函数。 1 d t i m e ( t ) 是这样的- 类- n g ：对于任意在d t i m e ( t ) 内的语言l ，都存在一个确定 图灵机m ，m 接受l ，并且死f ( n ) 曼t ( n ) ，对绝大多数n 都成立。 d t i m e ( c ) = u t c d t i m e ( t ) ； 2d s p a c e ( t ) j 一类语苦：对于任意在d s p a c e ( t ) 内的语言l ，都存在一个确 4 1 引言 定图灵机m ，m 接受l ，t t ：a s m ( n ) 茎t ( n ) ，对绝大多数n 都成立。d s p a c e ( c ) = u t c d s p a c e ( t ) ； 下面我们要给出非确定图灵机的时间和空间复杂度的定义，非确定图灵机的时 间和空间复杂度的定义要比确定图灵机复杂些。令m 为个非确定图灵机，给定输 入x ，如前所诉，可以把m 在x 上的运行看成是。棵计算树。对于这棵计算树的每条有限 ( 即m 停机) 的路径，定义这条路径的时间为m 从开始到结束运行的步数：我们需要考 虑的是这棵计算树所有接受的路径中所需时间最少的那条路径，定义t i r r t e m ( x ) 为这条 路径接受x 时所用的时问。同样的，令t i ( n ) = m n z ( n + 1 ) u t i m e m ( x ) ：= n ，m 接受。) 。( 当m 小接受任何长度为n 的字符串时，此时t m ( n ) = + 1 ，n + l 为图灵机把 输入读一遍的时间，这是为什么要加八 n + l 的原因) 。 我们可以按照类似的方法给出非确定图灵机的空问复杂度的定义。和确定图灵机一 样，考虑空间复杂度的时候，需要把工作带单独考虑，即不考虑输入和输出带上所用的 空问。非确定图灵机的空间复杂度同样考虑的是整棵计算树所有路径r i t 所用空间最少的 那条路径，s p a c e m ( x ) ) j 这条路径所用的空间的多少。s m ( n ) = m a x ( s p 。c e m ( z ) ：对于 所有= n ) 有了非确定图灵机的时间和空间复杂度的定义，就可以定义一些以非确定图灵机为 计算模型的语言类。 定义1 3 令tn 一是定义在整数上的整数函数。令c 为一类这样的函数。 1 n t i m e ( t ) 是这_ 样的一类语言：对于任意在n t i m e ( t ) 内的语言l ，都存在一个非确 定图灵机m ，m 接受l ，并且死f ( n ) ( n ) ，对绝大多数1 2 都成立。 n t i m e ( c ) = u g n t i m e ( t ) ； 2 n s p a c e ( t ) 是这样的一类语言：对于任意在n s p a c e ( t ) 内的语言l ，都存在一个非 确定图灵机m ，m 接受l ，并且s m ( n ) t ( n ) ，对绝大多数n 都成立。 n s p a c e ( c ) = u t e c n s p a c e ( t ) ； 下面我们给出的是多项式可计算的概念，也就是人们最初提出的“有效的算法”。 前面我们提到，用p o l y 来标记所有多项式整数函数的集合。 p = d t i m e ( p o l y ) n p = n t i m e ( p o l y ) p s p a c e = d s p a c e ( p o l y ) 5 以后我们说 于p ( p s p a c e ) i # i 。 下面给出的是 1 引言 n p s p a c e = n s p a c e ( p o z y ) 个语言是多项式时间( 空间) ) 可计算的，也就是说这个语言是属 些常见的语言类的定义： l o g s p a c e = d s p a c e ( 1 0 9 n ) n l o c - s p a c e = n s p a c e ( 1 0 9 m ) e x p = u 。 o d t i m e ( 2 c n ) n e x p = u 。 o n t i m e ( 2 “) e x p s p a c e = u 。 o d s p a c e ( 2 “) 下面是一些结构复杂性类研究l l _ f 比较重要的的结果： p 暑e x p 工o g s p a g e p s p a c e p s p a c e ce x p s p a g e e x p p s p a g e p s p a g e = n s p a c e d t i m e ( f ( n ) ) n t i m e ( ( n ) ) d s p a c e ( f ( n ) ) d s p a c e ( f ( n ) ) n s p a c e ( f ( n ) ) u c o d t i m e ( 2 c i ( “) ) ) l o g s p a g e l o g s p a g e p p p s p a c e 1 4 归约和完全性 归约和完全性在复杂性领域是很重要的两个概念，尤其在语言的分类中是很有用的工 具。我们将要介绍两种归约：多项式时问多一归约和多项式时z 、l r i n g 归约，在这两种 归约下，我们简单介绍了一种重要的完全性语言类n p 完全语言类。 首先我们给出n p 的另外一种定义： 定义14f n p ) ：一个语言a 是n p 语言类，当且仅当存在一个属于p 语言类的语言b ，和一 个多项式函数p ，对于每一个输a x ， x a 甘( 3 y ，l y i 曼p ( i x l ) ) b 可以证明，这样的定义和前面雕j n t i m e ( p o l y ) 的定义是等价的。所以，我们经常 把一个非确定多项式的计算过程说成足。个”先猜测后验证”的计算过程。 6 1 引言 定义15 ( 多项式时间多归约) ：令a + b r 是两个语言，我们说a 多。 归约到b ，如果存在。个可计算函数f ：+ + r ，对任意的z + o a 当且仪 当，( z ) b 。如果f 是多项式时间可计算的，我们就说a 多项式时间多归约到b ， 用a 景b 来表示。 n p 完全语言，顾名思义，是这样的语言：所有的n p 语言都可以多项式时间多一 归约到它；也就是说，如果个n p 完全语言能有多项式的算法，那么n p r 所有的语 言都能在多项式内解决。n p 完全语言的重要意义在于证明p p 时；n p 完全语占 是n p 语言类中最难的那些语言，如果一个n p 完全语言可以在多项式时问内解决，那 么p ：p ：如果p p ，那么所有的n p 完全语言必然都不可能存在多项式时间的 算法。目前我们所遇到的大部分的问题都是n p 完全的；c o o k 首先提出了完全语言的概 念，并且证叫了第一个实际的n p 完全语言一可满足问题。这也是复杂性研究巾一个很 重要的突破。随后，k a r p 证明了很多组合问题都是n p 完全的。到现在为止，人们发现 并证明的n p 完全问题多达几千个，详细的情况可以参阅【1 5 】 n l r i n g 归约要弱于c o o k 归约，t u r i n 9 1 ) j 约可以是问题之间，问题和语言的归约，它 的适用范围比c o o k 归约要广一些。并且和c o o k 归约一样，丑卫r i n g 归约对于p 的语言类是 封闭的：也就是说一个语言或问题t u f i n g 规约到一个p 语言，那么这个语言或问题也是 多项式时间之内可以解决的。 定义1 6 ( 多项式时f 司t u r i n g 归约) ：我们说一个问题a 可以t t t r i n g 规约到问题b ，如 果存在一个算法m ，m 可以计算a 。m 在计算过程中会提出一些问题，这些问题是关于 某些字符串是否属于b 的。进步说，如果m 所用的时间是输入长度的多项式( 提问算 作一步) ，并且每次提问的字符串的长度也是输入长度的多项式那么我们说a 多项式 时间t u r i n g 归约到b 。 在多项式t u r i n g 归约下，n p 完全问题有一个很好的性质一自归约。所谓自归约是 指一个语言对应的问题能够多项式t m , i n g 归约到这个语言：这个性质非常重要，在以后 的证明中我们还会提到。 1 5 概率图灵机 我们可以给图灵机增加一个额外的功能，就是投掷硬币，把得到的随机串也作为一个输 入，和给定的输入起进行计算。这样在给定输入的条件下，图灵机的输出也不是唯一 和确定的，是一+ 个和计算 t 得到的随机串相关的随机变量。这样的运算模型就是概率图 7 1 引言 灵机；概率图灵机为随机算法提供了一。个计算模型。在我们考虑的模型中，假定图灵机 在开始计算时就得到了所有的随机串。 显然，概率图灵机的代价也同样要考虑时间和空间，还必须考虑所用的随机串的长 度以及输出为正确的概率。一般研究的随机语言类的时间和空间代价都是输入长度的多 项式内的。根据图灵机输出正确的概率，我们可以把随机语言分为一些相应的语言类。 定义1 7 ( b p p ) ：语言类b p p 中包含所有这样的语言l ；l 属于b p p ，当且仅当存在 一个概率多项式图灵机m 接受l ，并且有 i ，如工一p r o b m ( x ) = 1 】兰； l 玎z 隹l p r o b m ( x ) = 1 】 目前我们所知的概率算法接受的语言大都是b p p 语言。 定义18 ( r p ) ：语言类r p 中包含所有这样的语占l ；l 属于r p ，当且仅当存在一个 概率多项式图灵机m 接受l ，并且有 i 玎。工一p r o b m ( x ) = 1 】； is f x 隹l p r o b m ( x ) = 1 】= 0 z p p 稍微有些特殊，对于一个z p p 语言l ，存在一个概率多项式图灵机m 接受l ，但 是m 的输出可以是? ，意思是m 4 i 知道输k x 是否属于l ：但是m 必须保证以相当大的概 率1 i 会输出? 。 定义1 9 ( z p p ) ：语言类z p p 中包含所有这样的语言l ；l 属于z p p ，当且仅当存在 一个概率多项式图灵机m 接受l ，并且有 ij 且l + p r o b m ( x ) = 1o r m ( z ) = ? 】_ 1a n d p r o b m ( x ) = 1 】 lj ，zg l p r o b m ( x ) = 0o r m ( 。) = ? = 1a n d p r o b m ( x ) = 0 1 1 6o r a c l e 图灵机年i i p h 前面我们提到了t u r i n g 归约，在t h r i n g 归约的过程t h 我们允许算法提问，但是不考虑 提问的代价。我们可以更加形式化一些，这样就必须要提l j o r a c l e 灵机的概念。 o r a c l e 图灵机比确定图灵机多根o r a c l e 带；在o r a c l e 灵机的运算过程中，可以 在o r a c l e 带上写些宁符串，然后o r a c l e 机进入一个特殊的状态一提问状态，这样表 8 1 引言 示o r a c l e 图灵机词问所写的字符串是否属于某个已知的语言类。o r a c l e 图灵机可以从提问 状态进入另外两个特殊的状态：接受状态或者拒绝状态，分别表示询问的字符串属于和 小属于这个已知的语言类；这样的计算过程只算一步，我们并不关心从提问状态到接受 或拒绝状态所需要的代价。所得到的计算模型就是o r a c l e 图灵机。 o r a c l e 图灵机主要的优势在于如果给定一个语言类a 作为o r a c l e ( 意思是计算过程的 提问是有关某些字符串是否属于a 的) ，那么在计算过程中我们忽略了原本计算a 的那 部分代价，而只考虑o r a c l e 图灵机本身的计算代价。 我们定义p 4 为所有以a 为o r a c l e ，确定图灵机多项式时间内能接受的所有语言的集 合。类似的可以给出n p a 的定义。更进一步，假定c 是个语言类， p e = u g p a 这样我们可以把t u r i n g 归约和o r a c l e 图灵机联系起来： b # ai f f b p 4 有 o r a c l e 图灵机的概念，我们还可以定义一些新的语言类- - p h ( p o l y n o m i a - t i m e h i e r a r c h y ) ； 定义11 0 ( p h ) ：对于任意的整数n ，嚣是这样的语言类： 芋= 孑= 掌= p ； e 鼻1 = p 2 ： p + 1 = 0 9 一0 1 n p + l = p e n p 这样我们有e f = 只e f = p p ， = p p p ； p h = u 。0 的集合，对于所有的n o ； 下面有些关于p h 的定理： n p p = p n p p s p a c e = p s p a c e 0 u # p + 1 。p + l n 鼻1 p s p a c e 关于p h ，还有另外。个等价定义，是通过谓词来给出的定义： 定义1 儿( p h ) ：n 1 ，一个语言a 属于：，当且仅当存在一个p 语言b ，和一个多项式 函数p ：对于任意的长度为n 的z + ， z a = = 亭( j n ，f 可1 l p ( n ) ) ( 奇饥，k 睦f p ( n ) ) ( h y n ，旧n fs p ( 咒) ) b 9 j 引言 q 。是这样的谓词，当n 是奇数是，q k 是l ；当n 是偶数时，q k 是v 。 1 0 第二章 随机复杂性语言类的研究与进展 2 1 引言 近3 0 年来，随着计算机科学的迅速发展结构复杂性理论( s t r u c t u r a lc o m p l e x i t y t h e o r y ) 的研究受到了越来越多的关注，也取得了许多很有价值和广泛应用的 研究成果。对结构复杂性理论的研究一般都基于一下几种计算模型：确定图灵 机( d e t e r m i n i s t i ct u r i n gm a c h i n e ) ，非确定图灵机( n o n - d e t e r m i n i s t c it u r i n gm a c h i n e ) 和概率图灵机( p r o b a b i l i s t i cn r i n gm a c h i n e ) ? ，2 6 。目前计算机科学家所作的大部分 工作都是以这两种模型为基础的。在这一章中，我们将以概率图灵机作为计算模型，讨 论一些介于p 和p s p a c e 之间的概率语言类。 概率图灵机与确定图灵机类似，不过概率图灵机允许额外的随机输入串。般说 来，概率图灵机的计算过程可以看作一棵计算树树的结点对应于概率图灵机的一个状 态( c o n f i g u r a t i o n ) 。对于概率图灵机m ，给定一个输入，m 的每步运行都会有若干 种可能，m 根据随机输入串随机选择其t 1r 一种可能进行计算。类似的，有一些特殊的状 态被称为终i h 状态。，m 的输出m ( x ) 是。个定义在所有可能的终止状态上的随机变 最。4 i 失一般性，我们令m f x 】- l 表示m 接受x ，否则m 输出0 。 基于概率图灵机模型，人们定义了很多介于p 和p s p a c e 之间的语言类：z pp r p , b p p ，p p ，关于它们之间的关系也已经有了很多工作。3 5 1 我们首先就z p p 和p p 展 开研究，考虑不同的出错概率，提出了两个与z p p f l p p 等价的定义。另外，我们 对b p p , p p 做更进一步的研究，引入了两类介于他们之问的复杂性类：b p l 和b p 2 。 在第二部分，我们基于概率图灵机给出了r p 的定义和n p 的另外种定义。第 三，四部分介绍z p p h p p 的等价定义，在第五部分，两个介于b p p 和p p 之间的语言类会 2 随机复杂性语言类的研究与进展 被详细的讨论。第六部分是对我们工作的总结以及对于今后的工作的展望。 2 2n p h r p 定义21 ：( n p ) n p 语言类包括所有这样的语言l ：对于l ，存在个多项式时间的非 确定图灵机m ，m 接受l 。 定义2 2 ：( n p l ) 【3 4 n p i ；, n 言类包括所有这样的语言l ：对于l ，存在个多项式时问 的概率图灵机m ， 定义23 ：( r p ) 【1 4 】r p 语言类包括所有这样的语言l ：对于l ，存在一个多项式时间 的概率图灵机m ， j 。工一p r o b m ( x ) = l 】j i 。掣l p r o b m ( x ) = o l = 1 需要注意的是常量1 2 并不唯一，我们可咀把1 2 换成【南，1 2 9 。 内的任意常 数，p ( ) 是任意的一个多项式函数，表示x 的长度。可以证明，这样改变了常数1 2 ， 我们并没有得到额外的能力，所得的新语言类都与r p 等价。( 有关细节，可以参阅 【1 4 】) 。 2 3z p p z p p 是个很有趣的语言类，它同样定义于概率图灵机上，并且z p p 允许概率图灵机的 输出可以是”? ”( ? 表示不知道) 。z p p 要求概率图灵机至多以1 2 的概率输出”? ”：而当概 率图灵机输出结果不是”? ”时，一定是正确的。 1 2 o 1 = | | = 如如 m m曲曲 r r p p t r 一 。 三l 略 掣 明 z z 匝 ，、i apn l | pn532理定 2 随机复杂性语言类的研究与进展 定义2 4 ：( z p p ) 【1 4 z p p 包括所有这样的语言l ：对于l ，存在一个多项式时间的概 率图灵机m + 有 。高：翼粥戋肛。 x l ( x ) 是语言l 的特征函数：x l ( x ) = 1 当z l ；x l ( x ) = 0 当。g l 。 定理2 2 ：【1 4 】z p p = n p n c o r p ；( c o - r p 是r p 的补语言) 定义2 5 ：( z p p l lz p p l 包括所有这样的语言l ：对于语言类l ，存在一个多项式时间 的概率图灵机m ，及一个多项式函数p ( ) ，有 k m v x , 。p r o b m 勘( x ) = m ? 1 。翥三意：。 定理23 ：z p p = z p p l 证明：z p pcz p p l ，我们只要令p ( ) 恒等于2 ，即可得出所需的结果 z p p3z p p l ，我们将采用”扩大”的方法来证明这个结果，”扩大”的方法是指我 们调用一个出错概率很大的图灵机足够多次来降低出错的概率，以达到我们的要求。 根据定义，对于任意一个属于z p p i 的语言l ，存在一个多项式的概率图灵机m ，及 一个多项式p ( ) ，满足定义233 。我们将构造一个新的多项式时间概率图灵机m ，m 按 照下面的规则运行：m 重复调用mq ( i x i ) 次；每次调用过程时，如果m 的输出不足? ， 则m 停机并把m 的结果作为输出返回。 q ( ) 是个多项式函数。如果m 的输入一直都是? ，则m 停机并返同? 。 为保证m 满足z p p 定义的要求，必须有 p r o b m 协) = ? 】i ( p r o b m ( x ) = ? 一刮( 1 - 赤蚓j 只要令：q ( i x l ) 一( f 凹( 1 一i 柄) ) _ 1 础 ，显然令口( ) = p ( ) 即可满足这个4 i 等式。 m 的运行时间仍然是的多项式次，所以有l z p p ，即z p p l z p p 证毕a 一 1 3 2 4p p 2 随机复杂性语言类的研究与进展 定义2 6 ( p p ) 1 4 p p 是这样的一个语吉类，对它其中的所有语言来说，都存在一个多 项式时间的概率图灵机m ，有 f 。工爿p r 。h i m ( z ) = 1 1z 掣工等p r o b m ( z ) = o 】 我们可以把上面两个概率式子中的任意一个的” ”号变成”号，但足我们不能把 两个” ”号都变成”号。类似的，对于下面的语言类p p l ，p p 2 都有这样的性质。 定义2 7 ( p p l ) 【1 4 jp p l 语言类包括所有的这样的语言l ：对于l ，存在个多项式时 i 日j 的概率图灵机m ，及个多项式p ( ) ，有 fz l p r o b m ( z ) = 1 1 2 一p ( 蚓) i z 岳l p r o b i m ( z ) = o 】 1 2 叫 定理2 4 3 5 1p p = p p l 我们提出了p p 的另外个等价定义p p 2 。 定义2 8 ( p p 2 ) p p 2 语言类包括了所有这样的语言l ：对于语言l ，存在一个多项式时间 的概率图灵机m ，及一个多项式p ( ) ，有 定理25p p = p p 2 。 。篆曼鬻眷蠡 证明：p p 2 p p ：对于任意的个语言l ，l 属于p p 2 ；根据定2 2 4 4 存在一个多 项式时间的概率图灵机m ，和一个多项式p ( ) 。我们构造一个新的多项式时间的概率图 灵机m ，m 按照下面的规则运行： 帆，】) ) ：掣a o = o ；。圳旷。 l 1o t h e r s 1 4 2 随机复杂性语言类的研究与进展 z l p r o b m 协) = 1 】= j 1s p r o b m ( z ) = 1 】+ j 1 ( 1 一赤) 。掣l ；p r o b m ( ) = o l = + p r o b m ( x ) = o l + + j 粕 + ( 1 一赤) + + 高 1 所以有l p p ，所以p p 2 p p 。 p p 2 p p ：对于任意的一个属于p p 的语言l ，根据定义2 4 1 ，存在一个多项式时 问的概率图灵机m 。我们构造个新的多项式时间的概率图灵机m ，m 按照下面的规则 运十： 盹，蚓硼胪 等赫锄m ：0 q ( ) 是一个多项式函数。我们有： l 哥p r o b m ( z ) = l 】= 而邢1 p r o b m ( x ) 2 1 】 瓣1 z 仨l j p r o b m ( ) = 0 1 = ( 1 f 1 = 1 而瓣1 ) + 而赤而 p r o b m ( x ) = o 】 高+ s 高) 面 令q ( ) = p ( i xl ) 2 ，这样我们就满足了p p 2 定义的要求。证毕。 _ 2 5b p p 定义2 9 ( b p p ) 【1 4 】语言类b p p 包括所有这样的语言l ：对于l ，存在一个多项式时间 的概率图灵机m ，有 e ：三：黝裴； 1 5 赤 一+ 赤 2 随机复杂性语言类的研究与进展 定义21 0 ( b p p l ) 【1 4 】语言类b p p l 包括所柯这样的语言l ：对于l ，存在个多项式时 问的概率图灵机m ，和个多项式函数p ( ) ，柯 小失一般性，我们可以假设对于所有的x 都成立p ( l x l ) 2 。对于任一属于b p p 的 语言l ，存在。个概率图灵机m ；我们可以同样构造出一个新的概率图灵机m ，：m 1 调 用m 足够多次，然后返回占多数的结果。 ( 具体细节，参阅【1 4 】) 众所周知，b p p p p ，我们想更深入的了解b p p 和p p 的联系基于这样的想 法，我们提出了两个新的语言类b p i ，b p 2 。这两个语言类都介于b p p 和p p 之间。 定义2 1 1 ( b p l ) 语言类b p l 包括所有这样的语言l ：对于l ，存在个多项式时间的 概率图灵机，和个多项式函数p o ，有 jz l p r o b m ( x ) = 1 】赤 lz g l p r o b m ( x ) = o 】1 2 - p ( i 。i ) 定义2 1 2 ( b p 2 ) 语言类b p 2 包括了所有这样的语