On polynomial time kernel reductions

In this paper, we examine a recently introduced type of eective reduction which applies solely to problems of equivalence or isomorphism: the \kernel reduction". Specically, we examine reductions among languages in the complexity class consisting of all languages induced by equivalence relations for which membership can be decided by a non-deterministic polynomial time Turing machine. This class is called NPEq; the denitions for PEq and coNPEq are analagous. We prove a general theorem which provides a problem which is hard under polynomial time kernel reductions for several classes of equivalence relations, including kPEq and PSPACEEq. In fact, such a problem is complete for PSPACEEq under polynomial time kernel reductions. We also show that if there is a complete problem under kernel reductions in NPEq, then that problem is also complete under many-one reductions in NP. Finally we use a proof of Ladner’s theorem to show that if PEq6 NPEq and there are problems in NPEq which are complete under polynomial time kernel reductions then there are NPEq-intermediary problems|problems which are in NPEq, but not complete under kernel reductions and not in PEq.