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.
