




Publications  The complexity of the Kth largest subset problem and related problems





Reference:
Christoph Haase and Stefan Kiefer. The complexity of the th largest subset problem and related problems. Information Processing Letters (IPL), 116(2):111–115, 2016.
Abstract:
We show that the th largest subset problem and the th largest tuple problem are in PP and hard for PP under polynomialtime Turing reductions. Several problems from the literature were previously shown NPhard via reductions from those two problems, and by our main result they become PPhard as well. We also provide complementary PPupper bounds for some of them.
Suggested BibTeX entry:
@article{16HKIPL,
author = {Christoph Haase and Stefan Kiefer},
journal = {Information Processing Letters (IPL)},
number = {2},
pages = {111115},
publisher = {Elsevier},
title = {The complexity of the ${K}$th largest subset problem and related problems},
volume = {116},
year = {2016}
}




