مسألة مجموع المجموعات الجزئية

مسألة مجموع المجموعات الجزئية Subset sum problem هي مسألة هامة في نظرية التعقيد الحسابي وعلم التعمية.[1][2] يتم سرد المسألة على النحو التالي، من أجل مجموعة من الأعداد الصحيحة، هل يوجد بعض المجموعات الجزئية الغير خالية التي يكون مجموع عناصرها مساوياً للصفر؟ على سبيل المثال هل يوجد مجموعة جزئية من المجموعة التالية {−2, −3, 15, 14, 7, −10} يكون مجموع عناصرها مساوياً للصفر؟ الجواب بكل بساطة هو نعم، لأن المجموعة الجزئية {−2, −3, −10, 15} مجموعها صفر وهو أمر من الممكن التحقق منه بكل بساطة بجمع العناصر. لكن إن عملية إيجاد كل مجموعة جزئية من المجموعة الأساسية يكون مجموع جميع عناصرها ينتهي إلى الصفر يأخذ وقتاً طويلاً. هذه المسألة هي مسألة NP كاملة وربما هي من أبسط المسائل من المسائل المعقدة.

مراجععدل

  1. ^ Martello, Silvano; Toth, Paolo (1990). "4 Subset-sum problem". Knapsack problems: Algorithms and computer interpretations. Wiley-Interscience. صفحات 105–136. ISBN 0-471-92420-2. MR = 1086874 1086874. الوسيط |CitationClass= تم تجاهله (مساعدة)CS1 maint: ref=harv (link)
  2. ^ Koiliaris, Konstantinos; Xu, Chao (2015-07-08). "A Faster Pseudopolynomial Time Algorithm for Subset Sum". arXiv:1507.02318. الوسيط |CitationClass= تم تجاهله (مساعدة)


 
هذه بذرة مقالة عن الحاسوب أو العاملين في هذا المجال، بحاجة للتوسيع. شارك في تحريرها.