Research Initiation: Investigations into the Structure of Intractable Sets

这个项目是对难处理集的计算复杂性的研究。其目的是获得对诸如NP， EXP和TIME （2poly）等单个类似乎具有的丰富数学结构的新见解，并增加我们对这些类之间结构关系的理解。为了达到这些目的，将采用新的概念和证明技术。在几乎所有参数上难以计算的集合在复杂性类的结构分析中起着重要作用。这些集合可以证明各种确定性、非确定性和广义Kolmogorov复杂度类之间的分离结果。在绝对结果难以捉摸的情况下，可以获得相对化结果。这些结果的应用将用于研究NP和EXP中的完备集的结构。一个与可计算集的多项式复杂度相关的新的非构造可约性将用于研究NP和EXP类的结构。获得了这些类的精细结构的新结果和见解；建议对这些领域进行进一步的研究。

This project is an investigation of the computational complexity of intractable sets. The object is to gain new insight into the rich mathematical structure that individual classes such as NP, EXP and TIME (2poly) appear to have, and to increase our understanding of the structural relationship between these classes. To these ends new concepts and proof techniques will be employed. Sets that are difficult to compute on almost all arguments play an important role in the structural analysis of complexity classes. Separation results between various deterministic, nondeterministic, and generalized Kolmogorov complexity classes can be witnessed by these sets. In cases where absolute results are elusive, relativization results will be achieved. Application of these results will be used to study the structure of complete sets in NP and EXP. A new nonconstructive reducibility that relates the polynomial complexity of computable sets will be used to investigate the structure of the classes NP and EXP. New results and insights into the fine structure of these classes have been obtained; further research into these areas is proposed.