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.