On Different Reducibility Notions for Function Classes

Heribert Vollmer

Abstract

This paper continues research of Toda (The Complexity of Finding Medians, 31st Symposium on Foundations of Computer Science (1990), pp. 778–787) on problems complete for function classes like FP#P and Mid P under Krentel's metric reductions. We first show that metric reductions wipe out the difference between Mid P and other related classes of functions which are probably different from Mid P. In order to obtain a more detailed classification of naturally arising functional problems we then define and examine a stricter notion of reducibility and show that a number of problems, among them those proved by Toda to be hard for Mid P under metric reductions, are complete for different classes of median functions related to Mid P under our stricter reducibility. Finally, we use these results to exhibit new natural complete sets for the well studied classes of sets PP, PPNP, and PPP.
BibTeX
@inproceedings{vollmer1994different,
  author = {Heribert Vollmer},
  title = {{On Different Reducibility Notions for Function Classes}},
  booktitle = {STACS},
  year = {1994},
  doi = {10.1007/3-540-57785-8\_162},
}

Loading related content...

Figure