نظرية التعقيد الحسابي

مسائل جوائز الألفية
نظرية التعقيد
حدسية هودج
حدسية پوانكاريه
فرضية ريمان
وجود يانگ-ميلز وفجوة الكتلة
معادلات ناڤييه-ستوكس
حدسية بيرش وسوينرتون-داير
عدل

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

تختلف نظرية التعقيد عن نظرية الحسوبية في أن نظرية الحسوبية تدرس فيما إذا كانت المسألة قابلة للحساب ام لا بشكل مطلق ، اما نظرية التعقيد فتدرس كيفية إنجاز الحسابات بكفاءة و سرعة .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

 تعاريف

في المعلومياتة تصنف المشاكل حسب صعوبة الحل, في هذه الحالة المقياس المستعمل هو الوقت و المساحة.

لإيجاد حلول للمشاكل الرياضية يتم اللجوء إلى الخوارزميات, إلا أن هناك مشاكل لها خوارزميات تحتاج لوقت كبير جدا لتعطي الحل, في حين هناك مشاكل أخرى يتم حلها بسهولة.

 الوقت و الزمن

من المعلوم أن معظم المشاكل يتم محاولة حلها باستعمال الحاسوب, و مع التطور التكنولوجي تتطور سرعة الأداء و يصبح الحاسوب قادرا على إجراء عمليات أكثر تعقيدا, لهذا وجب تحديد تعريف مستقل عن التكنولوجيا, مرتبط فقط بالخوارزميات, فمثلا إذا أخدنا عددين كل منهما مكون من 100 رقم, فإجراء عملية الجمع و الضرب بالحاسوب ستكون تقريبا آنية, فالمستعمل لن يشعر بأي فارق زمني.

إذن نعرف الزمن هنا على أنه عدد العمليات الأولية التي يحتاجها برنامج (خوارزمية) لإجراء العمليات.

 تصنيف

 المشاكل الحدودية المحددة

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

عادة ما يرمز للمشاكل الحدودية المحددة ب: P

أمثلة:

1. جداء عددين.
2. القاسم المشترك لعددين.
3. معرفة هل عدد أولي أم لا.

 المشاكل الحدودية غير المحددة

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

كما أنه إذا كان من الصعب إيجاد الحل, فإنه من السهل التأكد من صحة أو خطأ الجواب, فعملية التأكد و التحقق من الجواب تجرى في وقت حدودي.

عادة ما يرمز للمشاكل الحدودية غير المحددة ب: NP

أمثلة:

1. مشكلة تلوين المخطط.
2. مشكلة التفكيك إلى جداء عوامل أولية.
3. مشكلة المخطط الكامل ضمن مخطط.

 المشاكل الحدودية المحددة مقابل المشاكل الحدودية غير المحددة

من السهل ملاحظة أن المشاكل المحددة هي ضمن المشاكل غير المحددة, لكن المشكلة العظمى والتي لم يتمكن من الجواب عنها علماء المعلوميات مند سنة 1971 إلى الآن هو هل هناك تساو أو اختلاف بين الصنفين؟ و أول من يتمكن من الإجابة على هذا السؤال يأخد جائزة مالية قدرها 100000$.

 الاختصار

ليكن P و Q مشكلتين من صنف C)Cاعتباطي), نقول أن المشكل P يُختصر إلى المشكل Q, إذا وُجدت دالة f تحول كل هيئة من P إلى هيئة من Q. نقول أن حل المشكل Q يؤدي إلى حل المشكل P. أو كل خوارزمية تحل Q, تحل P.

 تعريف

نقول أن المشكل P, مشكل حدودي غير محدد كامل NP-complet إذا كان أصعب من جميع المشاكل المنتمية إلى صنف المشاكل الحدودية غير المحددة NP. أو كان هناك اختصار حدودي من أي مشكل من صنف NP إلى المشكل P.

 مبرهنة كوك و ليفين

الاكتفاء (معروف ب SAT) مشكل كامل .

 مشاكل كاملة أخرى

1. مشكلة تلوين المخطط.
2. مشكلة التفكيك إلى جداء عوامل أولية.
3. مشكلة المخطط الكامل ضمن مخطط.
4. مشكلة الرحالة التاجر.

 خاصية مهمة للمشاكل الكاملة

وجود خوارزمية حدودية لأي مشكل كامل يعني أن P=NP. و عكسيا عدم وجود خوارزمية حدودية لأي مشكل كامل يعني أن P#NP.

 لاندو

ترميز لاندو خاص بالمشاكل ويرمز له ب O (الحرف اللاتيني), يقدم فكرة عن سرعة دالة تتزايد أو تتناقص.

مثلا, عند تحليل خوارزمية ما, يمكن حساب عدد العمليات أو عدد المراحل اللازمة للحل, و قد نجد مثلا: T(n) = 4 n² - 2 n + 2. بالنسبة للبعد n.

هنا يمكن اهمال الثوابت و نقول أن T(n) تتزايد من الرتبة أو الدرجة n², و نكتب: >T(n) = O(n²).

ترميز		التعقيد
O(1)		ثابت
O(log(n))		لوغاريثمي
O(n log(n))		لوغاريثمي-خطي
O((log(n))c)		لوغاريثمي-متعدد
O(n)		خطي
O(n2)		رباعي
O(nc)		حدودي
O(cn)		أسي
O(n!)		عاملي