基于概率图灵机模型的复杂性类.pdf

复旦大学
硕士学位论文
基于概率图灵机模型的复杂性类
姓名:孟杰
申请学位级别:硕士
专业:计算机软件与理论
指导教师:朱洪
20040422
语言类琙,,。交互式证明系统有两个很重要的特点一交互性和随机性。验证方的计算能力是多项本文首先介绍了复杂性研究中常用的模型和基本概念,对概率图灵机和交互式证椤F渲杏玫降闹饕6【呤荌定理,定理的证明会在附录中给出。第四了￡痯阺摘要本文主要基于概率图灵机,研究随机复杂性类和交互式证明系统,的一些有趣的问题。概率工具在复杂性的研究中不仪是一个很有用的工具,同时也提出了新的研究课题。所谓概率图灵机,它除了正常的输入以外,还具有投掷硬币的能力;最终的输出和输入及掷硬币得到的随机串都有关。在这样的模型下,理论科学家们定义了一些相应的式的概率图灵机。证明方的能力不限,提供相应的证据给验证方。对于不同的输入,证明方能够以同的概率去说服验证方;根据验证方被说服的概率,我们可以区分开一个语言和它的补集,从而交互式证明系统接受了这个语言明系统做了基本的介绍。第二部分基于概率图灵机,给出了的定义的另外一种定义:然后介绍的等价定义;最后,详细讨论了两个介于口之间的语言类。第三部分对图不同构问题进行研究,提出了一个部分介绍了带竞争的证明系统岛,首先给出了蕇牧硗庖恢种っ鳎缓笾っ概率图灵机,扩大法,交互式证明系统,—证明系统,图不同构问题,带竞争的证明系统,ɡ恚馐裕珻—
;猼.—,甀珻,.瑂琙,,,珹珿瓼畐籺,
已第一章复杂性研究的历史特岢隽酥鍪兰湍烟狻F渲械谑鑫侍馐牵赫业揭桓鱿低郴某绦颍问题就是图灵的下作的出发点,图灵提出了著名的计算模型一一图灵机,从而奠定了计首先提出并证明了一个自然的完全问题~一可满足问蚐∞在年设计了。个概率多项式的算法来测试一个数是否是人们对计算理论的研究起源于上个世纪初。在年崮际数学家大会上,希尔波判定一个整系数多变元的多项式是否有整数解。更进一步,希尔波特开始了对判定问题的研究,研究的目标是找到一个算法来判定一个问题的所有实例。而希尔波特的第十个算理论的基础。在解决希尔波特的问题的过程中,可计算理论诞生了。在年最先开始了复杂性理论的研究,『谒枪餐表了‘篇文章里,提出计算机在更多的时间内能做更多的事情。他们不仅仅研究‘个问题是否可以计算,而且迸一步研究一个问题能在多少代价内计算。之后,,人们给出亩ㄒ濉题,迸‘一步证明了很多组合问题都是完全的。如今欠竦扔贜歉丛有素数,他们的工作开创‘个新的天地,就是概率计算模型。『ㄒ辶烁怕识嘞钍时间内接受的语言类一4哟怂婊丛有岳嘣诟丛有粤煊蛞舱加辛恕は兀率方法也成为了复杂性研究‘个很重要的具。交互式证明系统从开始就与复杂性的研究有非常密切的关系。年,,了亩ㄒ澹簿褪俏颐窍衷谒熘5摹蹦茉诙嘞钍绞蔽誓谂卸ǖ乃杏镅岳嗟募稀薄理论里最重要的一个问题,已经成为了一个千年难题。
计算模型一图灵机誖【餐岢隽私换ナ街っ飨低车哪P汀M辏珺】引入很有趣的模型,吸引了很多注意。到目前为止,关于最重要的工作包括【亢蚚。简单来说,图灵机是这样的一个模型:它包括输入带,输出带,及若干工作带;每条带表;图灵机还包括一个有限的状态控制系统。在本文一,所有的字母表∑械亩允家为底。我们用Ⅳ来表刺R坪齞,且桓霾糠趾狥羠籕×琑图灵机的每一步运行有以下几种可能的操作:·在读写头所在的位置读入~个字符:当前的状态,参照状态转移函数,来确定是否需要写入字符,写入哪个字符:是否移动。个带有公共随机串的交互式证明系统。肆:,辥三个学生在改进蔖日的证明·岢隽艘桓鲇芯赫闹っ飨低硈魑!じ上都有相应的读写头,在带上可以读出或者写入一些字符,这些字符是属于某个字母示所有多项式函数的集合。定义严格来说,图灵机包括以下几个部分:邢薷鲎刺募螿;跏甲刺琿蔘;邮茏刺螰∈淙胱帜副怼疲啤阹—珺是一个特殊的空自字符。·在读写头所在的位置写入’个字符;·向左或者向右移动读写头;每次运行,图灵机首先进行在读写头当前位置的读入一个字符,根据凄取的字符和/狹っ飨低常帜副韗、;·改变当前的状态;
时间和空间代价还有一类很重要的计算模型必须要提到的一非确定图灵机。前面我们介绍的是一般称之为范图灵机状态转移函数是一个集合—×罳×罫,C扛鑫逶玻瑂珼应了图灵机一步可能的运行。同样的瑂可能对应于多个玻琒珼簿褪撬低剂这样我们可以把非确定图灵机的运行看作是一颗计算树,每个分支对应于非确定圈读写头并且往那个方向移动;改变当前的状态到哪一个新的状态P枰W⒁獾氖牵知道了图灵机的运行规则,我们可以讨论图灵机是如何接受‘个语言或者计算一个函数了。以接受一个语占为例,初始时,输入串欠旁谑淙氪希渌哪谌均为空。图灵机的状态为初始状态帅