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

نظرية التعقيد هي فرع من فروع نظرية الحوسبة في علم الحاسوب النظري والرياضيات، وهذه النظرية تتركز في تصنيف المسائل الحاسوبية حسب صعوبتها وكذلك تُعنى في ربط أقسام التعقيد (complexity classes) ببعضها، والمسألة الحاسوبية هي مسألة يستطيع الحاسوب حلها.
ويمكن اعتبار مسألة صعبة اذا استخدمت كمية مُعينة من الموارد أيا كانت ومهما كانت الخوارزمية. ولعل النماذج الحسابية هي الطريقة الأمثل في هذه النظرية لدراسة هذه المسائل وتحديد كمية الموارد اللازمة مثل: الوقت أو حجم المكان الاضافي اللازم. ويوجد كذلك معايير تعقيد أخرى مثل: الاتصال (مستخدم في نظرية تعقيد الاتصال) وعدد البوابات في الدارات المنطقية ( مُستخدم في نظرية تعقيد الدارات المنطقية) وكذلك عدد المعالجات (مستخدم في الحساب المتوازي). وأحد أهم اساسات نظرية التعقيد الحسابي هي تبيين الحدود العملية لما يستطيع الحاسوب القيام به وما لا يستطيع القيام به .
المجالات القريبة في علم الحاسوب النظري هي تحليل الخوارزميات ونظرية الحاسوبية. ولعل الاختلاف بين تحليل الخوارزميات ونظرية التعقيد الحسابية هو أن الأول يسأل عن خوارزمية معينة لحل مسألة بينما الاخر يسأل عن كل الخوارزميات التي يمكنها حل المسألة وبالتحديد فان الأخير يحاول تصنيف المسائل التي يمكن حلها أو عدم حلها بوضع كمية مُحددة من الموارد، اما وضع الحدود للموارد الموجودة هو ما يميز نظرية التعقيد الحسابي عن نظرية الحاسوبية أي أن نظرية الحاسوبية تسأل عن أية مسائل يمكن حلها (او عدم حلها) بواسطة خوارزمية.

تعريف المُدخل

بشكل عام مُدخل(instance) لمسألة حاسوبية هو مجموعة معطيات  والمسألة الحاسوبية هي حساب دالة متعلقة بهذه المعطيات . مثال حساب المُحدد لمصفوفة : المُدخلات لهذه المسألة هي القيم في المصفوفة والمُخرج هو المُحدد . وقد يُنظر إلى المسألة على انها مجموعة كل المدخلات والمُخرج الملائم للمُدخل . أما انه يمكن ان تكون المدخلات بأطوال مختلفة وطول المُدخل هو كمية البتات اللازمة لترميز المُدخل بشكل ملائم اي أن المُدخل يكون سلسلة (string) تابعة ل-  مثال يمكن ترميز العدد (مثال 15 ) بواسطة تمثيله بنظام العد الثنائي ( الترميز الملائم ل-15 هو 1111),مثال اخر هو ترميز مخطط والذي يمكن ترميزه بواسطة القيم في المصفوفة الملائمة له .

لغات او مسائل التقرير

مسألة التقرير هي نوع خاص من المسائل الحاسوبية التي جوابها يكون إما نعم او لا او 0 و- 1 وهذا النوع من المسائل يُعرف أيضا باللغات في حين أن الأعضاء التابعة لهذه اللغة هي المُدخلات التي جوابها نعم . والهدف يكون باعطائنا مُدخل يجب التقرير اذا ما المُدخل عضو في هذه اللغة او لا وذلك بواسطة خوارزمية , مثال : فلتكن مسألة تقرير اذا ما عدد معطى هو أولي اللغة هي كل الاعداد الاولية ولتقرير اذا ما مُدخل معين هو أولي نشغل الخوارزمية التالية : "فحص كل الاعداد من 2 حتى هذا العدد وفحص اذا ما هذا العدد يمكن يقبل القسمة على اي عدد غير نفسه اذا نعم فالعدد ليس اوليا وخلاف ذلك العدد اولي" .

مسائل دالة

مسائل دالة(function problem) هي مسائل التي لكل مُدخل يكون هنالك مُخرج وحيد وتختلف هذه المسائل عن مسائل التقرير في انها قد يكون مُخرجها غير الاجابة بنعم ولا . مثال : تحليل لعوامل اولية ,المُدخل هو عدد المخرج هو التحليل لعوامل لهذا العدد . وقد يُعتقد أن مسائل الدالة اغنى من مسائل التقرير ولكن هذا غير صحيح بالضرورة إذ انه يمكن تحويل كل مسألة دالة لمسألة تقرير مثال : تحليل لعوامل اولية , المدخل : عدد , x, وقائمة اعداد, x₁,x₂,...,xd والمخرج هو نعم فقط اذا حاصل ضرب الاعداد هو ,x, وبالاضافة كل عدد بالقائمة هو اولي .

قياس تعقيد الخوارزمية

لقياس صعوبة مسألة حاسوبية , وَجَب على المرئ ان يقيس الوقت اللازم لافضل خوارزمية تحل المسألة . وبشكل عام الوقت قد يرتبط بطول المُدخل وبالتحديد مُدخلات طويلة حتما ستحتاج أكثر وقت للوصول للحل ,لذا فان قياس الوقت اللازم لحل مسألة هو دالة بطول المُدخل , وبشكل عام طول المُدخل يكون بالبتات . لذا فان علم التعقيد بالاساس يبحث مدى قابلية توسع الخوارزمية .
فلنفرض أنَّ n هو طول المُدخل حينها الوقت اللازم للخوارزمية يمكن التعبير عنه بواسطة n , وبما أنَّ لكل مُدخل قد يكون الوقت اللازم لحل المسألة مختلف لذا فانه يُأخذ بالاعتبار تعقيد وقت الحالة الأسوأ , (T(n , والذي هو الوقت الأطول الذي ستحتاجه الخوارزمية بالنسبة لكل المُدخلات . اذا كان (T(n متعدد الحدود اي : يوجد ثابت c>0 بحيث أنَّ (T(n)=O(nᶜ حينها نقول أنَّ الخوارزمية وقتها متعددة الحدود (polynomial time algorithm) . اطروحة كوبهام تقترح أن مسألة يمكن حلها مع كمية معقولة من الموارد اذا يوجد خوارزمية تحلها بوقت متعدد الحدود .

قياس التعقيد

ولكي يكون قياس التعقيد , والذي هو استخدام كمية مُعينة من الموارد مثل : الوقت او المكان , دقيقا ومُعرفا بشكل رياضياتي سليم كانت الحاجة للنماذج الحاسوبية مثال : آلة تيورنج , وقد نعرف الوقت اللازم لحل مسألة بواسطة آلة تيورنج ,M , مع المدخل للالة ,x, هو عدد الخطوات او التحول من وضعية لوضعية اللازمة للالة حتى التوقف والاتيان بالنتيجة ( مثل : نعم او لا ) . ونقول أنَّ آلة تيورنج , M , وقت عملها هو (f(n اذا كان الوقت اللازم للالة M على كل مُدخل طولة n هو (f(n . ونقول أنَّ مسألة يمكن حلها بوقت (f(n اذا يوجد آلة تيورنج M الوقت الذي تحتاجه لحل مُدخل طوله n هو (f(n . وبما أنَّ نظرية التعقيد اهتمامها بتصنيف المسائل حسب صعوبتها لذا فالمرئ يمكنه تعريف مجموعة مسائل تحقق معيار مُعين مثال ذلك المجموعة ((DTIME(f(n وهي مجموعة المسائل التي يوجد آلة تيورنج قطعية التي تحلها بوقت (f(n .
هنالك عدة مقاييس للتعقيد ولعل اهمها هو الوقت والمكان , ولعل بديهيات بلم (Blum axioms) في نظرية التعقيد تُعرف هذه المقاييس . مقاييس اخرى مُستخدمة في نظرية التعقيد هي تعقيد الاتصال وتعقيد الدارات المنطقية وتعقيد شجرة التقرير . وبشكل عام في قياس تعقيد الخوارزميات شاع استخدام رمز O الكبير .

حدود عليا وحدود دنيا على تعقيد المسائل

لكي نصنف الوقت الحسابي للمسائل (اي الوقت اللازم لحل مسألة بواسطة نموذج حاسوبي مُعين) يجب على الشخص  ان يبرهن الحدود الدنيا والعليا لكمية الوقت الاقل التي تستلزمها أفضل خوارزمية لحل المسألة , وبشكل عام تعقيد الخوارزمية هو تعقيد الحالة الأسوأ الا اذا حُدد غير ذلك , ولكي نبرهن أن لمسألة حد أعلى (T(n وجب تبيين خوارزمية التي تستلزم وقت (T(n . ولكن لكي نبرهن حد ادنى المهمة أصعب بكثير إذ على المرء أن يبين ان كل خوارزمية ممكنة لحل المسألة لا يوجد أي منها وقتها اقل من (T(n . وللتوضيح : عندما نقول " كل خوارزمية " نعني أنه لا يمكن أن يكون هناك خوارزمية التي تستلزم وقتا اقل من (T(n حتى في المستقبل . والحدود الدنيا والعليا لمسألة يُعبر عنها بواسطة رمز O كبير .

مسائل غير محلولة

ظهرت مسائل في نظرية التعقيد ولعلها من أهم المسائل في الالفية , حيث ان تطور العلوم بشكل عام سيكون اسرع لو كان لها حل . أهم هذه المسائل هي :

مسألة NP-P

من السهل ملاحظة أن المسائل الحتمية الحدودية (P) هي ضمن المسائل غير حتمية حدودية (NP), لكن المسألة المقابلة والتي تسأل هل مجموعة المسائل غير حتمية مجموعة جزئية لمجموعة المسائل الحتمية ؟ ولم يتمكن من الجواب عنها علماء المعلوميات منذ سنة 1971 إلى الآن هو هل هناك تساو أو اختلاف بين المجموعتين ؟ وقد عُرض عام 2000 مكافئة قدرها مليون دولار لمن يحل المسألة وذلك بواسطة معهد كلاي .
تلقي هذه المسألة بظلها على كل مجالات العلوم الحديثة ولحل هذه المسألة اهمية بالغة على تطور مجال علم التشفير او انتكاسه حيث انه لو NP=P حينها علم التشفير الحديث لن يكون له اي اهمية من الناحية النظرية ! ولكن لو تحقق هذا فان مجال تصميم الشرائح الالكترونية , تحليل الصور الرقمية , الذكاء الصناعي ... وغيرها من المجالات ستتطور لتكون في أقصى تطورها .

مسائل التي لا تتبع P ولا تتبع NP كاملة

لقد بيَّن لاندر انه في حال انه  حينها يوجد مسائل التي لا تتبع P ولا تتبع NP كاملة , للان لم يبرهن أحد على وجود مثل هذه المسائل ولكن هنالك حدسيات عن بعض المسائل التي محتمل جدا ان تكون كذلك منها : تحليل لعوامل , تطابق المخططات (graph isomorphism) , ...