Randomized Complexity Classes and Complexity in Finite Groups

这个项目延续了研究者的研究，分为两个不同的部分。第一部分探讨了新的低次多项式技术在复杂类仿真中的应用范围。这些方法是最近才发明的，并产生了惊人的结果：描述了交互证明和多证明者交互证明的力量。新方法没有相对化，这一事实在结构复杂性理论中具有潜在的深远影响。第二部分是进一步发展算法机制，将基本置换群操作置于NC中，并在顺序最坏情况下渐近时间复杂度方面取得了数量级的改进。这些新方法的一个显著特点是分析它们所需要的群论的深度。实际上，即使对于基本的任务，如置换群中的隶属性测试，也必须调用有限简单群分类的许多结果。

This project continues the investigator's research, with two distinct parts. The first part is to explore the scope of the new low degree polynomial techniques in simulation of complexity classes. These methods were invented very recently, with striking results: characterizations of the power of interactive proofs and multiprover interactive proofs. The new methods do not relativize, a fact with potentially far reaching consequences in structural complexity theory. The second part is to further develop the algorithmic machinery that put basic permutation group manipulation in NC and yielded an order of magnitude improvement in sequential worst case asymptotic time complexity. A striking feature of the new methods is the depth of group theory required for their analysis. Indeed, even for rudimentary tasks such as membership testing in permutation groups, a number of consequences of the classification of finite simple groups have to be invoked.