مسئله جمع زیرمجموعه‌ها

از ویکی‌پدیا، دانشنامهٔ آزاد

در علوم كامپيوترمسئله جمع زیرمجموعه‌ها (به انگلیسی: Subset_sum_problem) از اهميت مهمي در تئوري پيچيدگي و رمزنگاري برخوردار است، مسئله اين است كه اگر مجموعه اي از اعداد صحيح داشته باشيم ايا زيرمجموعه ناتهي وجود دارد كه جمع اعضايش برابر 0 شود؟ براي مثال در مجموعه {1,3,-2,-5,9,4} زيرمجموعه اي مانند {-5,-2,3,4} وجود دارد كه جمع اعضايش برابر 0 است. مسئله جمع زيرمجموعه‌ها NP است و احتمالا يكي از اسانترين انان است. صورت ديگر اين مسئله اين است كه ايا زيرمجموعه ناتهي از مجموعه اي از اعداد صحيح وجود دارد كه جمع اعضايش برابر عدد صحيح s شود؟ مسئله ديگري كه به نام subset sum problem معروف است اين مسئله است كه درمجموعه اي از اعداد طبيعي، اگر مجموع اعضاي زير مجموعه‌ها را در نظر گيريم،‌ عدد كه بيشترين تكرار را دارد، چند بار تكرار مي شود؟ پوركتر در سال 1982 اين مسئله را براي مجموعه ي {1,2,3…} حل كرد. براي n=1,2,… جواب برابر است با 1, 1, 2, 2, 3, 5, 8, 14, 23,… و تعداد اعداد متفاوت ايجاد شده براي n=1,2,… برابر است با 2, 4, 7, 11, 16, 22, 29, 37, 46, 56, .... براي مثال براي n=3، زير مجموعه هاي مجموعه {1,2,3}مي بينيم:

$\sum \varnothing \to 0$

$1 \to 1$

$2 \to 2$

$3 \to 3$

$1+2 \to 3$

$1+3 \to 4$

$2+3 \to 5$

$1+2+3 \to 6$

پس عددي كه بيشتر از همه ظاهر مي شود عدد 3 است كه 2 بار تكرار مي شود و 7 عدد متفاوت ايجاد مي شود. اين مسئله را مي توان با استفاده از توابع مولد حل نمود. اگر $c m, s$ تعداد روشهاي انتخاب m عدد از ميان Mعدد ${a 1, a 2 ... a M}$ باشد بصورتي كه جمعشان برابر s باشد و اگر تابع مولد زير را داشته باشيم:

$G(x,y)=\prod_{k=1}^M (1+x^{a_k}y)$