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.