دليل على صلابة NP التقليل المتزامن وتعظيم مجموعة فرعية مرجحة

Question

أنا أعمل في مشكلة محددة على أنها التالية

نظرا لمجموعة من $ n $ العناصر المسماة $ r \ subseteq \ mathbb {n} \ times \ mathbb { n} $ والأرقام $ z، g \ in \ mathbb {n} $ ، حيث $ z $ z هو مقياس لمواردنا و $ G $ هو مكافأة الحد الأدنى اللازمة لدينا، هل هناك مجموعة $ r '\ subseteq r $ ، بحيث $ \ sum _ {(z، g) \ in r'} z \ leq z z $ و $ \ sum _ {(z، g) \ in r '} g \ geq g $ ؟

أريد إظهار اكتمال NP وأظهر أنه في NP بالفعل. أنا تكافح مع صلابة NP. مشكلاتي المعروفة الصلبة هي السبت، 3SAT، التقسيم، مجموع الفرع الفرعي وحزم بن.

يبدو أن كفاحي هو في الغالب مع حقيقة أننا يتعين علينا تحقيق التوازن بين قيمين مختلفة الآن، والتكلفة والمكافأة. هذا ليس هو الحال في أي من المشكلات المتعددة ذات الصلة التي ذكرتها وأنا غير قادر على التفكير في كيفية طراز هذا في SAT أو 3SAT. ما أنا في عداد المفقودين هنا؟ كيف يمكنني إظهار صلابة NP وكهذه اكتمال NP هذه المشكلة باستخدام هذه المشكلات المعينة فقط؟

Answer 1

هذا يبدو لي مثل napsack مشكلة أين

• $ z $ هو الوزن لكل عنصر،
• $ Z $ هو السعة من الحرف،
• $ g $ قيمة العنصر، و
• $ g $ القيمة المراد تحقيقها.

المشكلة هي np-complete ولكن القابلة للحل، باستخدام البرمجة الديناميكية، في وقت متعدد الحدود الزائفة $ O (n \ CDOT W) $ حيث $ w=max _ {(z، g) \ in r} (g) $ .

يمكنك إثبات أن مشكلة NEAPTACK هي NP-Complete عن طريق تقليل من مشكلة المجموع الفرعي . في الواقع، مجموع الفرعي هو حالة خاصة من الحرفية حيث $ z= g $ ؛ "الوزن" لكل مشكلة هو نفسه "قيمة".