report · OpenBU/Boston University Institutional Repository (Boston University) · 2015
On polynomial time kernel reductions
Hescott, Ben, Finkelstein, Jeffrey
Cited by 0Abstract and details only
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. \nWe 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.
Cite this paper
Hescott, B., & Finkelstein, J. (2015). On polynomial time kernel reductions. OpenBU/Boston University Institutional Repository (Boston University).
Hescott, Ben, and Jeffrey Finkelstein. “On polynomial time kernel reductions.” OpenBU/Boston University Institutional Repository (Boston University), 2015.
Hescott, Ben, and Jeffrey Finkelstein. 2015. “On polynomial time kernel reductions.” OpenBU/Boston University Institutional Repository (Boston University).
Hescott, B. and Finkelstein, J. (2015) ‘On polynomial time kernel reductions’, OpenBU/Boston University Institutional Repository (Boston University).
@article{hescott2015polynomial,
title = {{On polynomial time kernel reductions}},
author = {Hescott, Ben and Finkelstein, Jeffrey},
journal = {OpenBU/Boston University Institutional Repository (Boston University)},
year = {2015}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.