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.