Journal article
The complexity of the Kth largest subset problem and related problems
- Abstract:
- We show that the Kth largest subset problem and the Kth largest m-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.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 256.6KB, Terms of use)
-
- Publisher copy:
- 10.1016/j.ipl.2015.09.015
Authors
- Publisher:
- Elsevier
- Journal:
- Information Processing Letters More from this journal
- Volume:
- 116
- Issue:
- 2
- Pages:
- 111-115
- Publication date:
- 2015-10-09
- Acceptance date:
- 2015-09-30
- DOI:
- ISSN:
-
0020-0190
- Language:
-
English
- Keywords:
- Pubs id:
-
pubs:581559
- UUID:
-
uuid:ed38e596-8482-478c-958a-b5747f1b2150
- Local pid:
-
pubs:581559
- Source identifiers:
-
581559
- Deposit date:
-
2016-01-10
- ARK identifier:
Terms of use
- Copyright holder:
- Elsevier BV
- Copyright date:
- 2015
- Rights statement:
- Copyright © 2015 Elsevier B.V.
- Notes:
- This is the accepted manuscript version of the article. The final version is available online from Elsevier at https://dx.doi.org/10.1016/j.ipl.2015.09.015
If you are the owner of this record, you can report an update to it here: Report update to this record