متفرقات

NP- مشكلة كاملة | الرياضيات

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

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

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