On polynomial time kernel reductions

Date
2011-12-20
DOI
Authors
Hescott, Ben
Finkelstein, Jeffrey
Version
OA Version
Citation
Hescott, Ben; Finkelstein, Jeffrey. "On Polynomial Time Kernel Reductions", Technical Report BUCS-TR-2011-028, Computer Science Department, Boston University, December 20, 2011. [Available from: http://hdl.handle.net/2144/11385]
Abstract
In this paper, we examine a recently introduced type of effective reduction which applies solely to problems of equivalence or isomorphism: the "kernel reduction". Specifically, 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 definitions for PEq and coNPEq are analogous. We prove a general theorem which provides a problem which is hard under polynomial time kernel reductions for several classes of equivalence relations, including (Sigma_k)PEq 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 PEq does not equal 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.
Description
License