Research Initiation: Measure and Category in Complexity Classes

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

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.