کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10331032 686440 2016 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The complexity of the Kth largest subset problem and related problems
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
The complexity of the Kth largest subset problem and related problems
چکیده انگلیسی
We show that the Kth largest subset problem and the Kth largestm-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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 116, Issue 2, February 2016, Pages 111-115
نویسندگان
, ,