The Structure of Complete Sets And Honest Polynomial Reducibilities

这个项目的目的是为了更好地理解几个被广泛研究的复杂类的完备集的性质和结构。特别要研究强多项式约简下的完备集以及这些集之间的p-同构的存在性。此外，还将研究诚实多项式的可约性和这些可约性的极小集。其目的是将复杂性理论中多项式可约性和公开问题的结构与递归理论的方法和结果联系起来。关于诚实多项式约简的极小集的存在性与P=？将研究NP问题。

This project is aimed at an improved understanding of properties and structure of complete sets for several, extensively studied complexity classes. In particular, complete sets under strong polynomial reductions and the existence of p-isomorphisms between these sets are to be studied. In addition, a study will be made of honest polynomial reducibilities and minimal sets for these reducibilities. The goal is to relate the structure of polynomial reducibilities and open problems in complexity theory to methods and results of recursion theory. The relationship between the existence of minimal sets with respect to honest polynomial reductions and the P=? NP problem will be studied.