计算复杂性的各个方面-猫眼课题宝

计算复杂性的各个方面

批准号：

9301430

负责人：

Andrew Yao

金额：

$22.55万

依托单位：

Princeton University

依托单位国家：

美国

项目类别：

Continuing Grant

财政年份：

1993

资助国家：

美国

项目状态：

已结题

起止时间：

1993-08-01 至 1997-01-31

来源：

https://www.nsf.gov/awardsearch/showAward?AWD_ID=9301430&HistoricalAwards=false

关键词：

Aspects Computational Complexity

项目摘要

项目成果

Andrew Yao的其他基金

相似基金

相关文献

中文摘要

翻译

研究了计算和数据处理问题的内在复杂性。学习的具体主题包括布尔电路和通信的复杂性、决策树模型和数据结构的复杂性。集中力量解决一些长期悬而未决的问题。来自组合学、概率论和拓扑学的技术为该项目提供了主要的数学工具。

英文摘要

The inherent complexity of computational and data manipulation problems is investigated. Specific topics studied include Boolean circuit and communication complexity, decision tree models, and the complexity of data structures. A concentrated effort is made at resolving some of the long standing open problems. Techniques from combinatorics, probability theory, and topology provides the main mathematical tools for the project.

期刊论文(0)

专著(0)

科研奖励(0)

会议论文