逼近于BPP和PP的概率复杂性语言类的多项式有界线路复杂性研究

本文通过图灵机多项式"?"输出有界和多项式错误输出有界概念的引入,研究了逼近于BPP和PP的一些概率复杂性语言类的多项式有界线路复杂性。

关于 BPP 的等价描述

讨论了概率复杂性类中的重要语言类ＢＰＰ，给出了ＢＰＰ的几个等价命题。

随机性及其应用研究

本文首先讨论“随机性”与“高效计算”之间的关系,并强调引入“随机性”于问题求解的意义与重要性。随后给出产生“随机性”的现实途径及为计算引入“随机性”的两种不同方式,即“在线”方式与“离线”方式;通过对概率图灵机求解判定问题的讨论,来说明两种引入“随机性”方式之间的等价关系。最后,本文指出现实的随机算法设计与实现并没有为计算引入真正的“随机性”。