Randomized Complexity Classes and Complexity in Finite Groups

随机复杂性类和有限群中的复杂性

• 批准号: 9014562
• 负责人: Laszlo Babai
• 金额: $ 20.73万
• 依托单位: University of Chicago
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1991
• 资助国家: 美国
• 起止时间: 1991-02-01 至 1995-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9014562&HistoricalAwards=false
• 关键词: Randomized; Complexity; Classes; Finite; Groups

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.

该项目继续研究人员的研究，有两个不同的 零件. 第一部分是探讨新低度的范围 多项式技术在复杂性类的模拟。 这些 最近发明了一些方法，取得了惊人的结果： 交互式证明和多重证明的能力的刻画 交互式证明 新的方法不相对化，一个事实， 结构复杂性理论中潜在的深远影响。 第二部分是进一步发展算法机制， 将基本置换群操作放入NC中并产生顺序 序列最坏情况渐近时间的幅度改进 复杂性 新方法的一个显著特点是 分析所需的理论。 事实上，即使 基本任务，如置换群中的成员资格测试， 有限单群分类的结果数 必须被调用。