Combinatorial Aspects of Randomness and Complexity

随机性和复杂性的组合方面

• 批准号: 8912586
• 负责人: Michael Sipser
• 金额: --
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing grant
• 财政年份: 1989
• 资助国家: 美国
• 起止时间: 1989-08-01 至 1993-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8912586&HistoricalAwards=false
• 关键词: Combinatorial; Aspects; Randomness; Complexity

This project studies two related areas: 1. Lower bounds on the complexity of explicit Boolean functions and 2. The application and understanding of randomness in the context of complexity theory. In the first area the goal is to strengthen current methods for proving lower bounds on restricted computational models. New approaches are sought that may be used to analyze unrestricted models such as general Boolean circuits. The PI will draw upon infinitary analogs of these problems to apply concepts from descriptive set theory. In the second area several problems concerning randomness will be considered. In particular, the use in of expanded graphs as a type of universal random object, and the design and application of pseudorandom generation.

该项目研究两个相关领域： 1.显式布尔函数复杂度的下界及 2.随机性的应用和理解 复杂性理论 在第一个领域，目标是加强目前的方法， 证明受限计算模型的下界。 新 寻求可用于分析无限制模型的方法 例如一般的布尔电路。 PI将利用无穷大 这些问题的类似应用概念从描述集 理论 在第二个领域，将讨论与随机性有关的几个问题。 考虑了 特别是，使用扩展图作为一种类型的 普适随机对象，伪随机的设计与应用 一代