Research Initiation: Measure and Category in Complexity Classes

研究启动：复杂性类别中的度量和类别

• 批准号: 8809238
• 负责人: Jack Lutz
• 金额: $ 3.79万
• 依托单位: Iowa State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1988
• 资助国家: 美国
• 起止时间: 1988-09-01 至 1991-02-28
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8809238&HistoricalAwards=false
• 关键词: Research; Initiation; Measure; Category; Complexity

A number of problems in computational complexity and pseudorandomness are being investigated, using new extensions of Lebesgue measure theory and the Baire category method as tools. These techniques, recently developed by the principal investigator, assign probabilistic and topological "sizes" to subsets of complexity classes. This approach, which has already revealed new, quantitative information about the structure of these classes, is being used to investigate: (1) relationships between uniform and nonuniform complexity, with particular emphasis on circuit-size and program-size complexities; (2) quantitative relationships between the "span" of (i.e., the set of problems efficiently reducible to) a problem and its complexity properties, including approximation, complexity cores, and hard instances; (3) theoretical aspects of pseudorandomness; and (4) the adequacy of pseudorandom sources for efficient randomized algorithms. The complexity-theoretic measure and category methods themselves are being refined, strengthened, and extended to a wider variety of classes.

利用勒贝格测度理论的新扩展和贝尔范畴方法作为工具，研究了计算复杂性和伪随机性方面的一些问题。这些技术最近由首席研究员开发，为复杂性类的子集分配概率和拓扑“大小”。这种方法已经揭示了关于这些类结构的新的定量信息，正被用于研究：(1)均匀和非均匀复杂性之间的关系，特别强调电路大小和程序大小的复杂性；(2)一个问题的“范围”（即有效可约为一个问题的问题集）与其复杂性属性（包括近似、复杂性核心和硬实例）之间的定量关系；(3)伪随机性的理论方面；(4)伪随机源对高效随机化算法的充分性。复杂性理论的度量方法和范畴方法本身正在被改进、加强，并扩展到更广泛的类。