مسألة كثير حدود وكثير حدود غير قطعي: الفرق بين النسختين
| [نسخة منشورة] | [مراجعة غير مفحوصة] |
تم حذف المحتوى تمت إضافة المحتوى
ط استرجاع تعديلات Jobas (نقاش) حتى آخر نسخة بواسطة 46.230.67.184 |
لا ملخص تعديل |
||
سطر 1:
{{جوائز الألفية}}
في العلم الحاسوبي يوجد شيء اسمه (الزمن الخطّي – Polynomial Time) أو P-Time اختصاراً، وهو مبدأ معقد يمكن تبسيطه بتصور الزمن الذي يلزمنا لنمُر على الأعداد من 1 إلى عشرة.. نحن سنمر عليها بالتسلسل. والآن لنتصور زمناً هو مضاعف لهذا الزمن الخطي: مربع الزمن الخطي، أو الجذر التكعيبي للزمن الخطي. هذا الزمن المفترض في علم الرياضيات هو زمن لا-خطي: Non-Polynomial أو NP اختصاراً.
المسألة المعلَّقة، حديثة العهد نسبياً، قدَّمها عالم الحاسوب ستيفن كوك عام 1971م، وتتعلق بإيجاد حلول برمجية -خوارزميات- لحل المعضلات الرياضية. فنحن نكتب للحاسوب برامج على هيئة خطوات متسلسلة تصل في النهاية إلى ناتج هو حل للمسألة. لكن هناك مسائل أعقد من غيرها. بعض هذه المسائل قد لا يكون لها حل، وبعضها قد يكون لها حل، لكن ليس في وقت خطّي أو معقول. هذا يعني أننا نكتب للمشكلات البسيطة برامج تنتهي في وقت معقول وتصل بنا إلى النتيجة الحسابية. في الرياضيات فإن الوقت المستغرق لحل مسألة بشكل «معقول» لا يتجاوز حل معادلة كثيرة الحدود ذات مجهول واحد س.
إن العلاقة بين '''مسائل ال[[تعقيد]] [[كثير حدود (تعقيد)|كثيرة الحدود]] و[[مسألة NP كاملة|كثير حدود غير قطعي]]''' هي مسألة غير محلولة في [[المعلوماتية النظرية]]. وهي تعتبر من أهم المسائل في هذا الحقل وقد عرض [[معهد كلاي للرياضيات]] جائزة مقدارها مليون دولار أمريكي لأول برهان صحيح لهذه المسألة.
| |||