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

点击翻译按钮获取中文摘要

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.