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

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

مراجع
  1. Martello؛ Toth (1990)، "4 Subset-sum problem"، Knapsack problems: Algorithms and computer interpretations، Wiley-Interscience، ص. 105–136، ISBN 0-471-92420-2، MR 1086874.
  2. Koiliaris, Konstantinos؛ Xu, Chao (08 يوليو 2015)، "A Faster Pseudopolynomial Time Algorithm for Subset Sum"، arXiv:1507.02318.
  • بوابة تعمية
  • بوابة علم الحاسوب
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.