مسألة مجموع المجموعات الجزئية
مسألة مجموع المجموعات الجزئية Subset sum problem هي مسألة هامة في نظرية التعقيد الحسابي وعلم التعمية.[1][2] يتم سرد المسألة على النحو التالي، من أجل مجموعة من الأعداد الصحيحة، هل يوجد بعض المجموعات الجزئية الغير خالية التي يكون مجموع عناصرها مساوياً للصفر؟ على سبيل المثال هل يوجد مجموعة جزئية من المجموعة التالية {−2, −3, 15, 14, 7, −10} يكون مجموع عناصرها مساوياً للصفر؟ الجواب بكل بساطة هو نعم، لأن المجموعة الجزئية {−2, −3, −10, 15} مجموعها صفر وهو أمر من الممكن التحقق منه بكل بساطة بجمع العناصر. لكن إن عملية إيجاد كل مجموعة جزئية من المجموعة الأساسية يكون مجموع جميع عناصرها ينتهي إلى الصفر يأخذ وقتاً طويلاً. هذه المسألة هي مسألة NP كاملة وربما هي من أبسط المسائل من المسائل المعقدة.
مراجع
[عدل]- ^ 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. مؤرشف من الأصل في 2021-12-01.
- ^ Koiliaris، Konstantinos؛ Xu، Chao (8 يوليو 2015). "A Faster Pseudopolynomial Time Algorithm for Subset Sum". arXiv:1507.02318.
