Saks和Wigderson推论的证明与Yao原理的拓展

特征值分布法是经典的Las Vegas计算下解析read-once波尔函数分布复杂性的有效方法。本项目一方面拓展特征值分布法至非read-once波尔函数，进而结合经典的Las Vegas计算下的Yao原理，探讨Saks 和Wigderson推论的最终证明。另一方面，分别基于经典的Monte Carlo计算下波尔函数分布复杂性及随机复杂性解析和不完全信息博弈论，探讨经典的Monte Carlo计算下等错误概率且具有等式关系的Yao原理是否存在。再之，拓展经典计算下的Yao原理至量子计算领域，开发一种非基于查询模型的量子复杂性限界解析方法。通过对经典的Monte Carlo计算及量子计算下的Yao原理的考察，为波尔函数随机复杂性和量子复杂性限界解析方法的开发提供新思路。研究Saks 和Wigderson推论的证明及Yao原理的拓展，对揭示随机算法和量子算法相对于确定算法的加速极限有重要意义。