كتب computational complexity theory
اذا لم تجد ما تبحث عنه يمكنك استخدام كلمات أكثر دقة.
نظرية التعقيد الحسابي (معلومة)
نظرية التعقيد هي فرع من فروع نظرية الحوسبة في علم الحاسوب النظري والرياضيات، وهذه النظرية تتركز في تصنيف المسائل الحاسوبية حسب صعوبتها وكذلك تعنى بربط أقسام التعقيد (complexity classes) ببعضها، والمسألة الحاسوبية هي مسألة يستطيع الحاسوب حلها.
ويمكن اعتبارها مسألة صعبة إذا استخدمت كمية مُعينة من الموارد أياً كانت ومهما كانت الخوارزمية. ولعل النماذج الحسابية هي الطريقة الأمثل في هذه النظرية لدراسة هذه المسائل وتحديد كمية الموارد اللازمة مثل: الوقت أو حجم المكان الإضافي اللازم، وتوجد كذلك معايير تعقيد أخرى مثل: الاتصال (مستخدم في نظرية تعقيد الاتصال) وعدد البوابات في الدارات المنطقية ( مستخدم في نظرية تعقيد الدارات المنطقية) وكذلك عدد المعالجات (مستخدم في الحساب المتوازي).
وأحد أهم أساسيات نظرية التعقيد الحسابي هي تبيين الحدود العملية لما يستطيع الحاسوب القيام به وما لا يستطيع القيام به .
المجالات القريبة في علم الحاسوب النظري هي تحليل الخوارزميات ونظرية الحاسوبية. ولعل الاختلاف بين تحليل الخوارزميات ونظرية التعقيد الحسابية هو أن الأول يسأل عن خوارزمية معينة لحل مسألة بينما الآخر يسأل عن كل الخوارزميات التي يمكنها حل المسألة، وبالتحديد فإن الأخير يحاول تصنيف المسائل التي يمكن حلها أو عدم حلها بوضع كمية مُحددة من الموارد، أما وضع الحدود للموارد الموجودة هو مايميز نظرية التعقيد الحسابي عن النظرية الحاسوبية أي أن النظرية الحاسوبية تسأل عن أية مسائل يمكن حلها (أو عدم حلها) بواسطة خوارزمية.
مسائل، مُدخل وطول المُدخل
تعريف المُدخل
بشكل عام مُدخل (instance) لمسألة حاسوبية هو مجموعة معطيات والمسألة الحاسوبية هي حساب دالة متعلقة بهذه المعطيات.
مثال حساب المُحدد لمصفوفة : المدخلات لهذه المسألة هي القيم في المصفوفة والمُخرج هو المحدد . وقد يُنظر إلى المسألة على انها مجموعة كل المدخلات والمُخرج الملائم للمُدخل . أما انه يمكن ان تكون المدخلات بأطوال مختلفة وطول المُدخل هو كمية البتات اللازمة لترميز المُدخل بشكل ملائم، أي أن المُدخل يكون سلسلة (string) تابعة ل- مثال يمكن ترميز العدد (مثال 15) بواسطة تمثيله بنظام العد الثنائي (الترميز الملائم ل-15 هو 1111)، مثال اخر هو ترميز مخطط والذي يمكن ترميزه بواسطة القيم في المصفوفة الملائمة له .
لغات أو مسائل التقرير
مسألة التقرير هي نوع خاص من المسائل الحاسوبية التي جوابها يكون إما نعم أو لا أو 0 و- 1، وهذا النوع من المسائل يُعرف أيضا باللغات في حين أن الأعضاء التابعة لهذه اللغة هي المُدخلات التي جوابها نعم، والهدف يكون بإعطائنا مُدخل يجب التقرير إذا ما المُدخل عضو في هذه اللغة أو لا وذلك بواسطة خوارزمية.
مثال : فلتكن مسألة تقرير إذا ما عدد معطى هو أولي اللغة هي كل الأعداد الأولية، ولتقرير إذا ما مُدخل معين هو أولي نشغل الخوارزمية التالية: "فحص كل الأعداد من 2 حتى هذا العدد وفحص إذا ما هذا العدد يمكن يقبل القسمة على أي عدد غير نفسه إذا نعم فالعدد ليس اوليا وخلاف ذلك العدد اولي" .
مسائل دالة
مسائل دالة (function problem) هي مسائل التي لكل مُدخل يكون هنالك مُخرج وحيد، وتختلف هذه المسائل عن مسائل التقرير في انها قد يكون مُخرجها غير الإجابة بنعم ولا.
مثال : تحليل لعوامل أولية، المُدخل هو عدد المُخرج هو التحليل لعوامل لهذا العدد، وقد يُعتقد أن مسائل الدالة أغنى من مسائل التقرير ولكن هذا غير صحيح بالضرورة، إذ انه يمكن تحويل كل مسألة دالة لمسألة تقرير مثال: تحليل لعوامل أولية. المدخل: عدد , x, وقائمة أعداد, x1,x2,...,xd والمُخرج هو نعم فقط إذا حاصل ضرب الأعداد هو ,x, وبالإضافة كل عدد بالقائمة هو اولي.
قياس تعقيد الخوارزمية
لقياس صعوبة مسألة حاسوبية وجب على المرء ان يقيس الوقت اللازم لافضل خوارزمية تحل المسألة، وبشكل عام الوقت قد يرتبط بطول المُدخل وبالتحديد مُدخلات طويلة حتما ستحتاج أكثر وقت للوصول للحل. لذا فان قياس الوقت اللازم لحل مسألة هو دالة بطول المُدخل، وبشكل عام طول المُدخل يكون بالبتات. لذا فان علم التعقيد بالأساس يبحث مدى قابلية توسع الخوارزمية.
فلنفرض أن n هو طول المُدخل حينها الوقت اللازم للخوارزمية يمكن التعبير عنه بواسطة n، وبما أن لكل مُدخل قد يكون الوقت اللازم لحل المسألة مختلف لذا فانه يُأخذ بالاعتبار تعقيد وقت الحالة الأسوأ , (T(n , والذي هو الوقت الأطول الذي ستحتاجه الخوارزمية بالنسبة لكل المدخلات.
إذا كان (T(n متعدد الحدود أي: يوجد ثابت c>0 بحيث أن (T(n)=O(nc حينها نقول أن الخوارزمية وقتها متعددة الحدود (polynomial time algorithm). أطروحة كوبهام تقترح أن مسألة يمكن حلها مع كمية معقولة من الموارد إذا يوجد خوارزمية تحلها بوقت متعدد الحدود.
