Note: This is an archvied version of our old webpage. Some links might be broken. The current one can be found here.
I7 Logo
Chair for Foundations of Software Reliability and Theoretical Computer Science
Informatik Logo TUM Logo
Publications - The complexity of the Kth largest subset problem and related problems


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.


We show that the th largest subset problem and the th largest -tuple problem are in PP and hard for PP under polynomial-time Turing reductions. Several problems from the literature were previously shown NP-hard via reductions from those two problems, and by our main result they become PP-hard as well. We also provide complementary PP-upper bounds for some of them.

Suggested BibTeX entry:

    author = {Christoph Haase and Stefan Kiefer},
    journal = {Information Processing Letters (IPL)},
    number = {2},
    pages = {111--115},
    publisher = {Elsevier},
    title = {The complexity of the ${K}$th largest subset problem and related problems},
    volume = {116},
    year = {2016}

PDF (254 kB)
See ...