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

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

تعاريف

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

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

الوقت والزمن

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

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

تصنيف

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

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

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

أمثلة:

جداء عددين.
القاسم المشهجر لعددين.
فهم هل عدد أولي أم لا.

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

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

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

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

أمثلة:

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

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

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

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

الاختصار

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

تعريف

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

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

الاكتفاء (معروف ب SAT) مأزق تام .

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

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

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

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

لاندو

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

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

مثلا, عند تحليل خوارزمية ما, يمكن حساب عدد العمليات أوعدد المراحل اللازمة للحل, وقد نجد مثلا: T(n) = أربعة 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(n²)		رباعي
O(n^c)		حدودي
O(cⁿ)		أسي
O(n!)		عاملي