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

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

de:Untermengensumme Subset sum problem]] es:Problema de la suma de subconjuntos fa:مسئله جمع زیرمجموعه‌ها fr:Problème de la somme de sous-ensembles ja:部分和問題 ko:부분집합 합 문제 pl:Problem sumy podzbioru simple:Subset sum problem tr:Alt küme toplamı problemi zh:子集合加總問題