The Structure of Complete Sets and Polynomial Reducibilities

本研究试图更好地理解许多自然复杂性类的完备集的内在性质。本研究将探讨完全集合的复杂性理论性质如何受到定义它们的可约性强度的影响，以及这些性质与复杂性理论的核心问题之间的关系。其中一个性质是免疫，它检验是否所有完全问题都有比完全问题更容易解决的更大的子问题。本研究涉及到这些棘手集的某些近似类型的存在性。另一个研究领域是完备集对之间有效约简的强度，以及从完备集到稀疏集或其他具有特定结构的集的约简的可能性。这些领域的复杂性理论结果与当前其他研究问题（如同构问题和某些类型的单向函数的存在性）之间的关系是本工作的中心焦点。

This research attempts to gain a better understanding of the intrinsic properties of complete sets for many natural complexity classes. The research will explore how the complexity-theoretic properties of complete sets are affected by the strength of the reducibilities defining them, and the relationships between these properties and the central problems in complexity theory. One such property is immunity, which examines whether all complete problems have larger subproblems which are easier to solve than the full problem. This research bears upon the existence of certain types of approximations to these intractable sets. Another area of study is the strength of efficient reductions between pairs of complete sets and the possibility of reductions from complete sets to sparse sets or other sets with a particular structure. The relationships between the complexity-theoretic results in these areas and other current research problems such as the isomorphism problem and the existence of certain types of one-way functions are a central focus of this work.