【摘 要】
：
该文主要基于概率图灵机,研究随机复杂性类和交互式证明系统中的一些有趣的问题.概率工具在复杂性的研究中不仪是一个很有用的工具,同时也提出了新的研究课题.所谓概率图灵机
论文部分内容阅读
该文主要基于概率图灵机,研究随机复杂性类和交互式证明系统中的一些有趣的问题.概率工具在复杂性的研究中不仪是一个很有用的工具,同时也提出了新的研究课题.所谓概率图灵机,它除了正常的输入以外,还具有投掷硬币的能力;最终的输出和输入及掷硬币得到的随机串都有关.在这样的模型下,理论科学家们定义了一些相应的语言类—BPP,ZPP,RP,PP.交互式证明系统有两个很重要的特点—交互性和随机性.验证方的计算能力是多项式的概率图灵机.证明方的能力不限,提供相应的证据给验证方.对于不同的输入,证明方能够以不同的概率去说服验证方;根据验证方被说服的概率,我们可以区分开一个语言和它的补集,从而交互式证明系统接受了这个语言该文首先介绍了复杂性研究中常用的模型和基本概念,对概率图灵机和交互式证明系统做了基本的介绍.第二部分基于概率图灵机,给出了RP的定义和NP的另外一种定义;然后介绍ZPP和PP的等价定义;最后,详细讨论了两个介于BPP和PP之间的语言类.第三部分对图不同构问题进行研究,提出了一个Perfect Arthur-Merlin Games(PAM)协议.其中用到的主要工具是Isolation定理,定理的证明会在附录中给出.第四部分介绍了带竞争的证明系统S2,首先给出了BPP(包含于符号 )S2的另外一种证明,然后证明了PSPACE( 包含于符号)P/poly→PSPACE(包含于符号 )S2
其他文献
该文通过分析目前网络监听及网络流量分析技术的发展、针对目前国税网络管理的现状和需求,提出了一个针对国税系统局域网络的windwos平台下的网络监控与分析系统.系统通过对
日益丰富的地学数据在一定程度上已超过了地球科学家能够处理的能力。从这些海量数据中发现地学知识的需要使得空间数据挖掘(Spatial Data Mining)的产生成为必然。空间数据
论文以数据仓库在移动通信中的应用为主题.首先说明了通信行业的背景以及移动面临的问题,提出了建立基于数据仓库的移动决策支持系统的必要性,接着介绍了数据仓库技术与理论,
日益庞大的网络及其异质性给网络管理和互操作提出了挑战，合理、有效地利用Internet上的信息资源是计算机应用的需要，也是当前计算机网络研究和开发的热点之一。目前，国内外研究
数据挖掘(Data Mining)是数据库领域的热门研究课题之一,它是随着数据仓库的出现而发展起来的一种决策支持过程,主要基于人工智能(AI)、机器学习、统计学等技术,高度自动化地
本文结合医疗保险部门分析决策的特点,提出了在SGDMDWS中的数据操作方法,并且对这些方法在数据仓库上的实现算法进行了研究.对于典型的OLAP操作(切片、切块、上卷、下钻和转
功能磁共振成像(functional Magnetic Resonance Imaging，fMRI)是神经影像学的研究热点之一，其原理是使用磁振造影技术测量神经元活动所引起的血液动力变化，从而获得大量的三维
该文提出了一种消除波纹失真的新方法:在视角变换矩阵中引入一个可调的系数γ来达到消除图像波纹失真的目的,该参数的引入只是在主视方向某些角度会改变Shear-Warp算法变形矩
本文根据界面工程设计和自动化的需要,给出一种支持界面和代码自动生成的扩展对象模型,并给出依据该扩展对象模型自动生成用户界面和代码的方法.本文所给出的扩展对象模型,在
TSP问题是组合优化问题的一个典型代表，数学家已经证明在图灵机上无法获得其精确的最优解，它属于NP难的问题。求解TSP问题无论在理论上还是在工农业生产或国民经济中都具有重大