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

در علوم رایانه مسئلهٔ جمع زیرمجموعه‌ها (به انگلیسی: Subset_sum_problem) از اهمیت مهمی در تئوری پیچیدگی و رمزنگاری برخوردار است، مسئله این است که اگر مجموعه‌ای از اعداد صحیح داشته باشیم ایا زیرمجموعه ناتهی وجود دارد که جمع اعضایش برابر ۰ شود؟ برای مثال در مجموعه {۱٬۳،-۲،-۵٬۹٬۴} زیرمجموعه‌ای مانند {-۵،-۲٬۳٬۴} وجود دارد که جمع اعضایش برابر ۰ است. مسئله جمع زیرمجموعه‌ها NP است و احتمالا یکی از اسانترین انان است. صورت دیگر این مسئله این است که ایا زیرمجموعه ناتهی از مجموعه‌ای از اعداد صحیح وجود دارد که جمع اعضایش برابر عدد صحیح s شود؟ مسئله دیگری که به نام subset sum problem معروف است این مسئله‌است که درمجموعه‌ای از اعداد طبیعی، اگر مجموع اعضای زیر مجموعه‌ها را در نظر گیریم، عدد که بیشترین تکرار را دارد، چند بار تکرار می‌شود؟ پورکتر در سال ۱۹۸۲ این مسئله را برای مجموعهٔ {۱٬۲٬۳…} حل کرد. برای n=1٬۲،… جواب برابر است با ۱، ۱، ۲، ۲، ۳، ۵، ۸، ۱۴، ۲۳،… و تعداد اعداد متفاوت ایجاد شده برای n=1٬۲،… برابر است با ۲، ۴، ۷، ۱۱، ۱۶، ۲۲، ۲۹، ۳۷، ۴۶، ۵۶،.... برای مثال برای n=3، زیر مجموعه‌های مجموعه {۱٬۲٬۳}می بینیم:

${\displaystyle \sum \varnothing \to 0}$

${\displaystyle 1\to 1}$

${\displaystyle 2\to 2}$

${\displaystyle 3\to 3}$

${\displaystyle 1+2\to 3}$

${\displaystyle 1+3\to 4}$

${\displaystyle 2+3\to 5}$

${\displaystyle 1+2+3\to 6}$

پس عددی که بیشتر از همه ظاهر می‌شود عدد ۳ است که ۲ بار تکرار می‌شود و ۷ عدد متفاوت ایجاد می‌شود. این مسئله را می‌توان با استفاده از توابع مولد حل نمود. اگر ${\displaystyle c_{m,s}}$ تعداد روش‌های انتخاب m عدد از میان Mعدد ${\displaystyle \lbrace a_{1},a_{2}...a_{M}\rbrace }$ باشد بصورتی که جمعشان برابر s باشد و اگر تابع مولد زیر را داشته باشیم:

${\displaystyle G(x,y)=\prod _{k=1}^{M}(1+x^{a_{k}}y)}$

با نوشتن بر حسب توان‌های y داریم:

${\displaystyle G(x,y)=\prod _{m=1}^{M}G_{m}(x)y^{m}}$

${\displaystyle G_{m}(x)=\sum _{s}C_{m,s}x^{s}}$

برای مثال فرض کنید می‌خواهیم m شی را از {۱٬۲٬۳٬۴٬۵} انتخاب کنیم؛ تابع مولد به صورت زیر است:

و برای مثال انتخاب m=3 دارای تابع مولد زیر است:

${\displaystyle G(x,y)=y^{5}x^{1}5+(x^{1}4+x^{1}3+x^{1}2+x^{1}1+x^{1}0)y^{4}+(x^{1}2+x^{1}1+2x^{1}0+2x^{9}+2x^{8}+x^{7}+x^{6})y^{3}+}$

${\displaystyle (x^{9}+x^{8}+2x^{7}+2x^{6}+2x^{5}+x^{4}+x^{3})y^{2}+(x^{5}+x^{4}+x^{3}+x^{2}+x)y+1}$

پس تعداد روش‌های انتخاب ۳ عدد از میان ۵ عدد که جمعشان عددی بین ۱۲٬۱۱،…،۶ باشد ضرایب ${\displaystyle G_{3}(x)}$ است که همان ${\displaystyle C_{3,s}}$ می‌باشد که برابر ۱٬۱٬۲٬۲٬۲٬۱٬۱ است.

۶ ${\displaystyle \gets }$(۱، ۲، ۳)

۷ ${\displaystyle \gets }$(۱، ۲، ۴)

۸${\displaystyle \gets }$ (۱، ۲، ۵)، (۱، ۳، ۴)

۹${\displaystyle \gets }$ (۱، ۳، ۵)، (۲، ۳، ۴)

۱۰${\displaystyle \gets }$ (۱، ۴، ۵)، (۲، ۳، ۵)

۱۱${\displaystyle \gets }$ (۲، ۴، ۵)

۱۲${\displaystyle \gets }$ (۳، ۴، ۵)

منابع

http://mathworld.wolfram.com/SubsetSumProblem.html

http://www.math.sunysb.edu/~scott/blair/Subset_sum_problems_are.html

https://web.archive.org/web/20080307085025/http://www-fs.informatik.uni-tuebingen.de/~reinhard/krypto/English/4.5.1.e.html

لینک‌ها

www.cs.dartmouth.edu/~ac/Teach/CS۱۰۵-Winter۰۵/Notes/nanda-scribe-۳.pdf

www.cs.umass.edu/~barring/cs۶۱۱/lecture/۱۸.pdf