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.