تحويل مشكلة مجموعة فرعية مختلطة إلى الحالة الإيجابية

Question

دعنا نقول أن لدينا مشكلة مجموعة فرعية مع قائمة { $ x_1، x_2، x_3، ... x_n $ } والوزن $ W $ ، مع بعض من $ x_i <0 $ .هل هناك طريقة معروفة، في وقت متعدد الحدود، لتحويل هذه المشكلة إلى مشكلة معادلة، ولكن مع كل $ x_i \ geq 0 $ ؟وإذا لم يكن هناك أي، هل من الممكن أن تكون هناك مثل هذه الخوارزمية؟

Answer 1

كل من المتغيرات كاملة، لذلك يوجد مثل هذا التخفيض بالتأكيد: تعريفNP-covereness يضمن ذلك.

إذا كنت تريد تخفيضا واضحا، فيمكنك تقليل واحدة إلى أخرى (تقليل 3SAT باستخدام نظرية كوك، ثم تقليل 3SAT إلى الآخر باستخدام اكتمال NP الخاص به).سيكون التخفيض الناتج قبيحا، لذلك أظن أن هذا قد لا يكون ما تبحث عنه.

إذا كنت تريد تخفيض بسيطا وطبيعيا، فأنا لست متأكدا من كيفية تحقيق ذلك.