إثبات مشكلة Troid Trader هي NP-Complete

Question

هذا السؤال هو من الفصل 8، وممارسة 35، من تصميم الخوارزمية من Kleinberg و Tardos.

لاعب في اللعبة يتحكم في سفينة الفضاء وحاول كسب المال شراء وشراء الرعد على كواكب مختلفة. هناك $ n $ أنواع مختلفة من Droids و $ K $ الكواكب المختلفة. كل كوكب $ p $ لديه الخصائص التالية: هناك $ s (j، p) \ geq 0 $ droids of اكتب $ j $ متاح للبيع، بسعر ثابت من $ x (j، p) \ geq 0 $ كل، ل $ J= 1، 2، dots، n $ ، وهناك طلب للحصول على $ D (J ، ص) \ GEQ 0 $ droids من النوع $ J $ ، بسعر ثابت من $ y ( J، P) \ GEQ 0 $ كل منها. (سنفترض أن الكوكب لا يوجد في وقت واحد كلاهما العرض الإيجابي والطلب الإيجابي لنوع واحد من الروبوت؛ وبالتالي لكل $ J $ ، واحد على الأقل من $ s (j، p) $ أو $ d (j، p) $ يساوي $ 0 $ .)

يبدأ اللاعب على الكوكب $ s $ مع $ Z $ وحدات المال ويجب أن تنتهي في Planet $ T $ ؛ هناك رسم بياني Acyclic الموجه $ g $ على مجموعة من الكواكب، بحيث $ S $ - $ t $ المسارات في $ G $ تتوافق مع طرق صالحة من قبل اللاعب. (يتم اختيار G أن يكون أكريكيا لمنع طويلة تعسفا ألعاب.) للحصول على $ S $ - $ T $ المسار $ p $ في $ G $ ، يمكن للاعب الانخراط في المعاملات على النحو التالي. كلما وصل اللاعب إلى كوكب $ P $ على المسار $ P $ ، يمكنها شراء ما يصل إلى $ s (j، p) $ droids of اكتب $ J $ ل $ x (j، p) $ وحدات المال لكل منها (شريطة الحصول على أموال كافية اليد) و / أو بيع حتى $ D (J، P) $ droids من النوع $ J $ ل $ y (j، p) $ وحدات من المال (لذلك أنا أفترض أنه يمكنك إجراء شراء / بيع متعددة في كل كوكب). النتيجة النهائية للاعب هي المبلغ الإجمالي للمال لديها في متناول اليد عندما تصل إلى الكوكب $ T $ .

أحاول إثبات هذه المشكلة أصعب من بعض مشكلة NP كاملة، لكنني عالق تماما. نظرا لأن الكواكب يتم تنظيمها في DAG، أعتقد أن "صلابة" المشكلة تأتي من حقيقة أنه يمكنك شراء وبيع العديد من أنواع مختلفة من الرعد في كل كوكب. أيضا، هذه المشكلة مشكلة كبيرة، ولا أعرف العديد من مشاكل تعظيم NP-Complete بخلاف التعيين التربيعي.

عملية التفكير الخاصة بي هي أن الروبوت يجب أن تمثل شيئا، على سبيل المثال اختيار رؤوس الرسم البياني. ثم يعكس سعر الروبوت "القيمة" بطريقة ما؛ على سبيل المثال في تخفيض غطاء الرأس، يمثل Droid تمثل قمة الرأس $ I $ لديه سعر بيع يساوي درجة قمة الرأس $ i $ على سبيل المثال.

شيء يعمل بشكل جيد بالنسبة لي لممارسة 30 السابقة هو النظر في نسخة بسيطة للغاية من المشكلة. لذلك في هذه الحالة، فكرت في الحالات التي كانت فيها الكواكب مجرد رسم بياني خطي، أو لا يوجد نوعان فقط من الرعدات، أو كل كواكب تبيع نوعا بالضبط 1 من الروبوت وتشتري نوع 1 من الروبوت (حتى تتمكن من إجبار اللاعب على الشراء / بيع بدلا من مجرد التمسك بنقدهم). أحاول أن أبسط بهذه الطريقة ومعرفة ما إذا كان يبدأ في تشبه مشاكل NP-Hard الأخرى، وهذا هو السبب في أنني أظن أنه يجب أن يكون غطاء الرأس أو تخفيض 3-SAT.

سيكون موضع تقدير أي تلميحات مثل المشكلة (X) التي يجب علي اختيارها للحد من مشكلة Trader Droid، أو كيف يمكنني عرض هذه المشكلة (مثل 3-SAT يمكن عرضها على أنها اختيار واحد من $ 2 ^ n $ الخيارات، ثم التحقق من أن الاختيار يرضي بعض مجموعة من غير طرف)

Answer 1

يمكنك العثور على تخفيض بسيط من Neapsack أو من مشكلة القسم (والتي تقلل إلى Napsack).

دعونا نفعل ذلك من مشكلة القسم:

معطى $ n $ أعداد صحيحة $ s={a_1، a_2 \ ldots، a_n \} $ مع إجمالي المبلغ، هل يوجد مجموعة فرعية تبلغ مجموعها نصف مجموع جميع العناصر؟

حتى نفترض أنك تعطى مثال لمشكلة القسم. نبني مثالا لمشكلة Troid Trader كما يلي:

• سيكون هناك $ n $ أنواع الرعدات، واحدة لكل عدد صحيح في $ S $ . سيكون هناك كواكتين $ S $ و $ T $ ، مع حافة موجهة من $ S $ إلى $ t $ .
• على الكوكب $ S $ ، يمكن للاعب شراء دروس واحد من كل نوع $ i $ $ للحصول على سعر $ a_i $ ، ويمكن بيع أي شيء.
• على الكوكب $ t $ ، يمكن للاعب بيع الدروع من كل نوع $ i i $ ل سعر $ 2 \ cdot a_i $ ، ويمكن شراء أي شيء.
• اللاعب يبدأ مع $ z $ يساوي نصف مجموع جميع العناصر في $ S $ .

بعد ذلك، من السهل أن نرى ذلك، لا يمكن أن ينتهي المشغل أبدا بأموال أكثر من $ \ sum s $ . علاوة على ذلك، يمكنه تحقيق $ \ sum $ إذا وفقط إذا كان يمكن شراء $ \ frac {1} {2} \ مبلغ $ قيمتها على الكوكب الأول، أي هناك مجموعة فرعية من $ s $ مع مجموع $ \ FRAC {1} {2} \ مبلغ S $ .

لذلك فإن السؤال الأصلي في مثيل مشكلة القسم يعادل طرح عما إذا كان يمكن أن ينتهي اللاعب مع $ \ sum $ money في مشكلة المتداول الروبوت المقابل.

لأن هذا هو تخفيض وقت متعدد الحدود، وهذا يثبت المطالبة.

Answer 2

المشكلة هي NP-Complete حتى إذا كان يمكن للاعب شراء / بيع عدد من الكسر من الروبوت. نحن تقلل من غير متساوي التساوي 3SAT (NAE3SAT) إلى هذه المشكلة.

نظرا مثيل NAE3SAT مع $ n $ المتغيرات $ x_1، \ Ldots، x_n $ و $ m $ claus، نحن نبني رسم بياني مثل يلي.

giveacodicetagpre.

هذا هو، في كل خطوة، يختار اللاعب الذهاب إلى واحد بالضبط من الكواكب $ x_i ^ 0 $ و $ x_i ^ 1 $ .

نحن نبني نوعين من Droids $ d_j $ و $ d_j '$ لكل جملة $ J $ . إذا جملة $ J $ هو، على سبيل المثال، $ x_1 \ vee \ neg x_3 \ vee x_4 $ ، ثم هناك 1 droid من النوع $ d_j $ في الكوكب $ x_1 ^ 0، x_3 ^ 1 $ for بيع و 1 Droid من النوع $ d_j '$ في الكوكب $ x_1 ^ 1، x_3 ^ 0 $ for بيع، وهناك طلب 1 الطلب على Droids من النوع $ d_j $ في الكوكب $ x_4 ^ 0 $ و 1 الطلب على Droids من النوع $ d_j '$ في الكوكب $ x_4 ^ 1 $ . لكل نوع، ثمن المشغل لشراء الروبوت واحد هو دائما 1، والسعر للاعب لبيع الروبوت هو دائما 2. اللاعب لديه $ m $ المال في البداية حيث $ m $ هو عدد كبير جدا.

الآن يمكننا أن نرى fomula هو مثيل صالح من nae3sat إذا وفقط إذا كان اللاعب يمكن أن يحمل $ m + m $ $ T $ .

بالمناسبة، يوضح هذا التخفيض أن مشكلتك، بغض النظر عما إذا كان اللاعب يمكنه شراء / بيع عدد من الكسر من الروبوت، هو بقوة np-complete .