Research Initiation: Applications of Kolmogorov Complexity:Pseudorandom Generators, Circuit Complexity, and One-Way Functions

研究启动：柯尔莫哥洛夫复杂度的应用：伪随机发生器、电路复杂度和单向函数

• 批准号: 8810467
• 负责人: Eric Allender
• 金额: $ 3.12万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1988
• 资助国家: 美国
• 起止时间: 1988-07-01 至 1990-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8810467&HistoricalAwards=false
• 关键词: Research; Initiation; Applications; Kolmogorov; Complexity

This research centers on the development of generalized Kolmogorov complexity theory as a tool to apply to problems in various areas of complexity theory including circuit complexity, pseudorandom generators, and one-way functions. Building on the principal investigator's work in circuit complexity, this work seeks to relate the size of the circuit's description to the complexity of producing the circuit. One goal of this work would be to indicate that there is a theoretical difference between efficient "general purpose" and "special purpose" parallel computation. Recent results have shown that probabilisitic techniques are useful in analyzing the Kolmogorov complexity of sets in certain well known classes. This research seeks to develop the link between probability theory and generalized Kolmogorov complexity. Different hypotheses on the existence of one- way functions have different necessary conditions in terms of generalized Kolmogorov complexity. Sometimes, these conditions conflict. This work investigates the nature of the conflict.

本研究的重点是发展广义Kolmogorov复杂性理论，将其作为一种工具应用于复杂性理论的各个领域，包括电路复杂性、伪随机发生器和单向函数。以首席研究员在电路复杂性方面的工作为基础，这项工作试图将电路描述的大小与生产电路的复杂性联系起来。这项工作的一个目标是指出在高效的“通用”和“专用”并行计算之间存在理论差异。最近的结果表明，概率技术在分析某些已知类集合的Kolmogorov复杂度方面是有用的。本研究旨在发展概率论与广义柯尔莫哥洛夫复杂度之间的联系。在广义柯尔莫哥洛夫复杂度方面，关于单向函数存在性的不同假设具有不同的必要条件。有时，这些条件会发生冲突。这项工作调查了冲突的本质。