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

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

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

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

تعاريف

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

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

الوقت والزمن

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

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

تصنيف

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

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

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

أمثلة:

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

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

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

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

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

أمثلة:

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

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

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

الاختصار

ليكن 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!)		عاملي

أنظر أيضا

• مسألة NP كاملة
• مسألة P-NP

ملف:Nuvola apps edu mathematics-ar.svg

بوابة رياضيات تصفح مقالات ويكيبيديا المهتمة بالرياضيات.

bn:গণনামূলক জটিলতা তত্ত্ব ca:Complexitat computacional cs:Teorie složitosti de:Komplexitätstheorie el:Θεωρία πολυπλοκότητας Computational complexity theory]] es:Teoría de la complejidad computacional et:Algoritmiline keerukus fa:نظریه پیچیدگی محاسباتی fi:Aikavaativuusluokka fr:Théorie de la complexité des algorithmes he:סיבוכיות hr:Računska teorija složenosti it:Teoria della complessità computazionale ja:計算複雑性理論 ko:계산 복잡도 이론 lt:Algoritmų sudėtingumas ms:Teori kekompleksan pengiraan nl:Complexiteitstheorie no:Kompleksitetsteori pl:Złożoność obliczeniowa pt:Complexidade computacional ro:Teoria complexității ru:Теория сложности вычислений sh:Računska teorija složenosti simple:Computational complexity theory sk:Teória zložitosti sr:Теорија комплексности sv:Komplexitetsteori th:ทฤษฎีความซับซ้อนในการคำนวณ uk:Теорія складності обчислень vi:Độ phức tạp thuật toán zh:計算複雜性理論