U.S.-Germany Cooperative Research on Structure in ComplexityTheory

美德复杂性理论结构合作研究

• 批准号: 9513368
• 负责人: Lane Hemaspaandra
• 金额: $ 1.6万
• 依托单位: University of Rochester
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1996
• 资助国家: 美国
• 起止时间: 1996-05-01 至 1999-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9513368&HistoricalAwards=false
• 关键词: U.S.; Germany; Cooperative; Research; Structure

This award supports Professors Lane and Edith Hemaspaandra, of the University of Rochester and Le Moyne College, respectively, to collaborate in computer science with Professor Gerd Wechsung of the Friedrich Schiller University of Jena, Germany. Together they will study several topics of current interest in computational complexity theory These include (1) rigorous studies of the effect of query order on complexity (i.e., whether and when the order of access to multiple information sources matters) and (2) certificate complexity (calculating the conditions that control the size of classes of sets which always have acceptance certificates that can be easily computed.) The U.S. and German participants in this collaboration bring to bear complementary strengths in the creative theoretical aspects and the rigorous mathematical aspects of computational complexity. The joint effort of these talented and prolific researchers should produce significant contributions to the study of structural aspects of complexity theory. Results will have implications in many aspects of computer and information science.

该奖项分别为罗切斯特大学和勒莫恩学院的莱恩教授和伊迪丝·赫马斯帕拉（Edith Hemaspaandra）提供了支持，分别与德国耶拿的弗里德里希·席勒大学的弗里德里希·施莱尔大学的格德·韦希斯（Gerd Wechsung）合作。 他们将共同研究一些当前对计算复杂性理论兴趣的主题，其中包括（1）对查询顺序对复杂性的影响（即是否以及何时访问多个信息源的顺序很重要）和（2）证书的复杂性（计算始终具有易于计算的阶级构成的阶级大小的条件）的严格研究。计算复杂性的严格数学方面。 这些才华横溢和多产的研究人员的共同努力应为研究复杂性理论的结构方面的研究做出重大贡献。 结果将在计算机和信息科学的许多方面具有影响。