Productive functions and isomorphisms

Joseph and Young [5] conjectured that there are non-p-isomorphic NP-complete sets if ak-creative set in NP exists which has no p-invertible p-productive function. We prove that this conjecture is true for the exponential-time (deterministic and nondeterministic) complexity classes E and NE. In particular, we prove that non-p-isomorphic E-complete sets exist if and only if there is a p-creative set in E which has no p-invertible p-productive function. Similar result holds for NE as well.This work was supported in part by NSF Grants CCR-8814339 and CCR-9108899.