ما هي المشاكل "الأصعب" باستخدام الوقت متعدد الحدود؟

Question

قرأت مؤخرًا عمل ندوة الذي يقول:

يمكن توسيع خوارزمية المطابقة [للرسوم البيانية العامة] إلى الحالة المرجحة ، والتي يبدو أنها واحدة من مشاكل التحسين التوافقية "الأصعب" التي يمكن حلها في وقت متعدد الحدود.

ظهر السؤال التالي على الفور في ذهني:

هل تعرف مشاكل "p-hard" الأخرى؟

في الوقت الحالي ، أود تحديد p-hard على النحو التالي: "تم العثور على خوارزمية متعددة الحدود متأخرة جدًا (بعد عام 1950) في الأدب لهذه المشكلة". (أو كيف يمكن للمرء أن يحدد بشكل أفضل "صعبًا" إذا كانت هناك بالفعل خوارزميات حتمية تحل المشكلة في وقت متعدد الحدود؟)

Answer 1

هناك بالفعل مشاكل "P-Complete" ، مما يعني أنه يمكن تقليل كل مشكلة أخرى يمكن حسابها في وقت متعدد الحدود. نرى http://en.wikipedia.org/wiki/p-complete.

Answer 2

الأعداد الأولية في P.

Answer 3

مشكلة أخرى "صعبة" P هي حل "البرمجة الخطية":

http://en.wikipedia.org/wiki/Linear_Programming#algorithms

Answer 4

إذا كنت ترغب في ثني القواعد قليلاً ، إذن خوارزميات زمنية زائفة هي "الأصعب" التي يمكنك حلها في "الوقت متعدد الحدود".

مثال كلاسيكي لخوارزمية زائفة O(nW) حل البرمجة الديناميكية إلى مشكلة Quapsack.

Answer 5

مشكلة المهمة التي يمكن حلها في O (ن³) عن طريق تعديل الخوارزمية المجرية.