Title: On Polynomial Time Kernel Reductions
Authors: Ben Hescott and Jeffrey Finkelstein
Date: December 20, 2011
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.