كيف تعرف ما إذا كانت المشكلة تنتمي إلى فئة NP؟

Question

ما أعرفه (لا يتحدث بدقة): أعرف أن هناك سؤالا مفتوحا حول مساواة فئات P و NP وطالمة عدم وجود خوارزمية معروفة تحل مشاكل NP في ف الوقت ثم نصفقنا حول قابلية وقت الفضاء لمثل هذه المشاكل. كما أعلم أنه يمكنك إجراء تخفيضات (من الوقت متعدد الحدود) بين المشاكل، لذلك إذا كنت تعلم أن المشكلة تنتمي إلى فئة معينة، فستتم إذن المشكلة الأخرى أيضا إلى هذه الفئة. أيضا، أعرف أن خوارزمية البسيط يحل مشاكل البرمجة الخطية

ما أود أن أعرف: أود أن أعرف كيفية "تخمين" إذا كانت هناك مشكلة تنتمي إلى فئة NP. هل يجب القيام به مع قيود المشكلة، وعدد القيود، "نوع" القيود؟

مثال في هذا الرابط https://www.geeksforgeeks.org/maximum-profit-by-buying-and-selling-a-share-share-k-k-times/ يمكننا أن نرى algorthm يحل "أقصى ربح عن طريق شراء وبيع حصة في معظم أوقات K" مع البرمجة الديناميكية.

ومع ذلك، ماذا لو قمنا بزيادة القيود. دعنا نقول أننا تقتصر أن نقتصر على القيمة الصافية (ليس لدينا أموال غير محدودة) أو يمكننا شراء وبيع أكثر من سهم واحد في وقت واحد، لكننا تقتصر على تفاصيل الأسهم التي يمكننا شراءها أو بيعها في وقت معين ، أو هناك مخزونات متعددة من مختلف الشركات التي يمكننا الاختيار من بينها، لكننا محدودون في إجمالي عدد الأسهم التي يمكن أن نحصل عليها.

كيف يمكننا أن نعرف أي نوع من القيود تجعل المشكلة أكثر صعوبة وأصعب "تحريك" من فئة P إلى NP؟ ما نوع القيود التي يجب أن تتأكد من أن هذه المشكلة تتأكد من أن هذه المشكلة تنتمي إما إلى فئة P أو NP؟

Answer 1

1. تأكد من استخدام NP بشكل صحيح. ليقول شيئا ينتمي إلى NP لا يقول حقا أي شيء، إلا أن الحل المناسب للمشكلة يمكن التحقق بسرعة.

2. من تجربتي، إنه أكثر عن نوع المشكلة مما هي القيود المحددة التي تعطيهها.
   على سبيل المثال مجموعة محتلة: بما في ذلك Vertex في نهاية الرسم البياني قد intpact إذا كنت تستطيع أن تأخذ قمة الرأس في الطرف الآخر من الرسم البياني. هذا النوع من الآثار الجانبية غير المتوقعة يجعل من المستحيل العثور على خوارزمية حقا، لأنك لا تستطيع أن تقرر أي شيء عن حلكم لأنك لا تعرف الآثار.

على العكس من ذلك هو الفرز: إذا كنت تستخدم QuickSort، فيمكنك اختيار محور وتقسيم العناصر إلى قسمين، والذين أقل والذين أكثر من المحور.
بهذه الطريقة قمت بها بالفعل المشكلة أسهل: تحتاج فقط إلى فرز هذه الأجزاء 2، وأنت تعرف أي منها ينتمي إلى أي جانب من المحور.

الحصول على مثل هذا المقبض على مشكلة NP-الصعبة لم تكن ناجحة بعد.

أعلم أن هذا كان غامضا في النهاية، في النهاية لا يمكنك تعميم سؤالك. يجوز لكل تغيير في مشكلة معينة أن يجعلها عموما NP-Hard، تحتاج إلى البحث بشكل فردي.

لإثبات أن هناك شيئا ما NP-Hard، يمكنك محاولة تقليل مشكلة NP الصعبة المعروفة إليها. هذه هي الطريقة التي يتم بها مع معظمها.

مثال على سؤالك سيكون أيضا:
مشكلة قصوى هو NP-Hard، ولكن إذا طلبت فقط إذا كان هناك قطع من الحجم | E |، ثم يصبح سهلا، لأنه يعادل طلب ما إذا كان الرسم البياني هو bipartite