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

في علوم الكمبيوتر النظرية والرياضيات، تركز نظرية التعقيد الحسابي على تصنيف المشكلات الحسابية وفقًا لاستخدامها للموارد، وتستكشف العلاقات بين هذه التصنيفات. المشكلة الحسابية هي مهمة يحلها الكمبيوتر. يمكن حل المشكلة الحسابية من خلال التطبيق الميكانيكي للخطوات الرياضية، مثل الخوارزمية .

تعتبر المشكلة صعبة بطبيعتها إذا كان حلها يتطلب موارد كبيرة، أياً كانت الخوارزمية المستخدمة. تقوم النظرية بإضفاء الطابع الرسمي على هذه الحدس، من خلال تقديم نماذج رياضية للحساب لدراسة هذه المشاكل وقياس تعقيدها الحسابي ، أي مقدار الموارد اللازمة لحلها، مثل الوقت والتخزين. تُستخدم أيضًا مقاييس أخرى للتعقيد، مثل مقدار الاتصال (المستخدم في تعقيد الاتصالات )، وعدد البوابات في الدائرة (المستخدم في تعقيد الدائرة ) وعدد المعالجات (المستخدمة في الحوسبة المتوازية ). أحد أدوار نظرية التعقيد الحسابي هو تحديد الحدود العملية لما يمكن لأجهزة الكمبيوتر فعله وما لا يمكنها فعله. تعد مشكلة P مقابل NP ، إحدى مشاكل جائزة الألفية السبع ، ^[1] جزءًا من مجال التعقيد الحسابي.

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

يمكن النظر إلى المشكلة الحسابية على أنها مجموعة لا نهائية من الحالات مع مجموعة (ربما فارغة) من الحلول لكل حالة. يشار إلى سلسلة الإدخال للمشكلة الحسابية باسم حالة المشكلة، ولا ينبغي الخلط بينها وبين المشكلة نفسها. في نظرية التعقيد الحسابي، تشير المشكلة إلى السؤال المجرد الذي يتعين حله. على النقيض من ذلك، فإن حالة هذه المشكلة هي عبارة ملموسة إلى حد ما، والتي يمكن أن تكون بمثابة المدخلات لمشكلة القرار. على سبيل المثال، ضع في اعتبارك مشكلة اختبار الأولية . الحالة هي رقم (على سبيل المثال، 15) والحل هو "نعم" إذا كان الرقم أوليًا و"لا" بخلاف ذلك (في هذه الحالة، 15 ليس أوليًا والإجابة هي "لا"). وبعبارة أخرى، الحالة هي مدخل معين للمشكلة، والحل هو الناتج المقابل للمدخلات المحددة.

ولإلقاء المزيد من الضوء على الفرق بين المشكلة والمثال، فلنتأمل المثال التالي لإصدار القرار من مشكلة بائع المتجول : هل يوجد مسار يبلغ طوله 2000 كيلومتر على الأكثر ويمر عبر جميع أكبر 15 مدينة في ألمانيا؟ إن الإجابة الكمية على هذا المثال الخاص بالمشكلة لا تفيد كثيراً في حل أمثلة أخرى من المشكلة، مثل طلب رحلة ذهاب وعودة عبر جميع المواقع في ميلانو التي يبلغ طولها الإجمالي 10 كيلومترات على الأكثر. ولهذا السبب، تعالج نظرية التعقيد المشكلات الحسابية وليس أمثلة مشكلة معينة.

عند النظر في المشكلات الحسابية، تكون حالة المشكلة عبارة عن سلسلة فوق أبجدية . عادةً، يتم اعتبار الأبجدية هي الأبجدية الثنائية (أي المجموعة {0,1})، وبالتالي تكون السلاسل عبارة عن سلاسل بتات . كما هو الحال في الكمبيوتر في العالم الحقيقي ، يجب ترميز الكائنات الرياضية بخلاف سلاسل البتات بشكل مناسب. على سبيل المثال، يمكن تمثيل الأعداد الصحيحة في تدوين ثنائي ، ويمكن ترميز الرسوم البيانية مباشرة عبر مصفوفات مجاورتها ، أو عن طريق ترميز قوائم مجاورتها في ثنائي.

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

تعتبر مشاكل القرار أحد الأهداف المركزية للدراسة في نظرية التعقيد الحسابي. مشكلة القرار هي نوع من المشاكل الحسابية حيث تكون الإجابة إما نعم أو لا (أو بدلاً من ذلك، 1 أو 0). يمكن اعتبار مشكلة القرار لغة رسمية ، حيث تكون أعضاء اللغة هي الحالات التي يكون ناتجها نعم، وغير الأعضاء هي الحالات التي يكون ناتجها لا. الهدف هو تحديد ما إذا كانت سلسلة الإدخال المعينة عضوًا في اللغة الرسمية قيد النظر، بمساعدة خوارزمية . إذا أعادت الخوارزمية التي تحل هذه المشكلة الإجابة بنعم ، يُقال إن الخوارزمية تقبل سلسلة الإدخال، وإلا يُقال إنها ترفض الإدخال.

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

مشكلة الدالة هي مشكلة حسابية حيث من المتوقع وجود ناتج واحد (لدالة إجمالية ) لكل مدخل، ولكن الناتج أكثر تعقيدًا من ناتج مشكلة القرار - أي أن الناتج ليس مجرد نعم أو لا. تشمل الأمثلة البارزة مشكلة بائع السفر ومشكلة تحليل الأعداد الصحيحة .

من المغري أن نتصور أن مفهوم مسائل الدالة أغنى كثيراً من مفهوم مسائل القرار. ولكن هذا ليس صحيحاً حقاً، لأن مسائل الدالة يمكن إعادة صياغتها باعتبارها مسائل قرار. على سبيل المثال، يمكن التعبير عن عملية ضرب عددين صحيحين على أنها مجموعة من الثلاثيات بحيث تكون العلاقة صحيحة. ويتوافق تحديد ما إذا كانت ثلاثية معينة عضواً في هذه المجموعة مع حل مشكلة ضرب عددين. ${\displaystyle (أ،ب،ج)}$${\displaystyle a\times b=c}$

لقياس صعوبة حل مشكلة حسابية، قد يرغب المرء في معرفة مقدار الوقت الذي تتطلبه أفضل خوارزمية لحل المشكلة. ومع ذلك، قد يعتمد وقت التشغيل، بشكل عام، على الحالة. وبشكل خاص، تتطلب الحالات الأكبر وقتًا أطول للحل. وبالتالي، يتم حساب الوقت المطلوب لحل مشكلة (أو المساحة المطلوبة، أو أي مقياس للتعقيد) كدالة لحجم الحالة. يتم قياس حجم الإدخال عادةً بالبتات. تدرس نظرية التعقيد كيف تتدرج الخوارزميات مع زيادة حجم الإدخال. على سبيل المثال، في مشكلة معرفة ما إذا كان الرسم البياني متصلاً، ما مقدار الوقت الإضافي الذي يستغرقه حل مشكلة لرسم بياني به رؤوس مقارنة بالوقت المستغرق لحل رسم بياني به رؤوس؟ ${\displaystyle 2n}$${\displaystyle n}$

إذا كان حجم الإدخال هو ، فيمكن التعبير عن الوقت المستغرق كدالة لـ . نظرًا لأن الوقت المستغرق على مدخلات مختلفة من نفس الحجم يمكن أن يكون مختلفًا، فإن أسوأ تعقيد زمني يتم تعريفه على أنه الحد الأقصى للوقت المستغرق على جميع المدخلات ذات الحجم . إذا كانت متعددة الحدود في ، فيقال إن الخوارزمية هي خوارزمية زمنية متعددة الحدود . تزعم أطروحة كوبهام أنه يمكن حل المشكلة بكمية معقولة من الموارد إذا كانت تقبل خوارزمية زمنية متعددة الحدود. ${\displaystyle n}$${\displaystyle n}$${\displaystyle T(n)}$${\displaystyle n}$${\displaystyle T(n)}$${\displaystyle n}$

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

تُستخدم أنواع عديدة من آلات تورينج لتحديد فئات التعقيد، مثل آلات تورينج الحتمية ، وآلات تورينج الاحتمالية ، وآلات تورينج غير الحتمية ، وآلات تورينج الكمومية ، وآلات تورينج المتماثلة ، وآلات تورينج المتناوبة . وهي جميعًا قوية بنفس القدر من حيث المبدأ، ولكن عندما تكون الموارد (مثل الوقت أو المكان) محدودة، فقد تكون بعضها أقوى من غيرها.

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

تم اقتراح العديد من نماذج الآلات المختلفة عن آلات تورينج القياسية متعددة الأشرطة في الأدبيات، على سبيل المثال آلات الوصول العشوائي . ربما من المدهش أن كل من هذه النماذج يمكن تحويلها إلى نموذج آخر دون توفير أي قوة حسابية إضافية. قد يختلف الوقت واستهلاك الذاكرة لهذه النماذج البديلة. ^[2] ما تشترك فيه كل هذه النماذج هو أن الآلات تعمل بشكل حتمي .

ومع ذلك، فإن بعض المشكلات الحسابية أسهل في التحليل من حيث الموارد غير المعتادة. على سبيل المثال، تعد آلة تورينج غير الحتمية نموذجًا حسابيًا يُسمح له بالتفرع للتحقق من العديد من الاحتمالات المختلفة في وقت واحد. لا علاقة لآلة تورينج غير الحتمية بكيفية حساب الخوارزميات التي نريدها فعليًا، لكن تفرّعها يلتقط بدقة العديد من النماذج الرياضية التي نريد تحليلها، وبالتالي فإن الوقت غير الحتمي يعد موردًا مهمًا للغاية في تحليل المشكلات الحسابية.

للحصول على تعريف دقيق لما يعنيه حل مشكلة باستخدام مقدار معين من الوقت والمساحة، يتم استخدام نموذج حسابي مثل آلة تورنج الحتمية . الوقت المطلوب من قبل آلة تورنج الحتمية على الإدخال هو العدد الإجمالي لانتقالات الحالة، أو الخطوات، التي تقوم بها الآلة قبل أن تتوقف وتخرج الإجابة ("نعم" أو "لا"). يقال أن آلة تورنج تعمل في غضون الوقت إذا كان الوقت المطلوب من قبل على كل إدخال بطول هو على الأكثر . يمكن حل مشكلة القرار في الوقت المناسب إذا كانت هناك آلة تورنج تعمل في الوقت المناسب تحل المشكلة. نظرًا لأن نظرية التعقيد مهتمة بتصنيف المشكلات بناءً على صعوبتها، فيمكن للمرء أن يحدد مجموعات من المشكلات بناءً على بعض المعايير. على سبيل المثال، يتم الإشارة إلى مجموعة المشكلات التي يمكن حلها في غضون الوقت على آلة تورنج حتمية بواسطة DTIME ( ). ${\displaystyle M}$${\displaystyle x}$${\displaystyle M}$${\displaystyle f(n)}$${\displaystyle M}$${\displaystyle n}$${\displaystyle f(n)}$${\displaystyle A}$${\displaystyle f(n)}$${\displaystyle f(n)}$${\displaystyle f(n)}$${\displaystyle f(n)}$

يمكن وضع تعريفات مماثلة لمتطلبات المساحة. على الرغم من أن الوقت والمساحة هما أكثر موارد التعقيد شهرة، إلا أنه يمكن اعتبار أي مقياس للتعقيد موردًا حسابيًا. يتم تعريف مقاييس التعقيد بشكل عام جدًا من خلال بديهيات تعقيد بلوم . تشمل مقاييس التعقيد الأخرى المستخدمة في نظرية التعقيد تعقيد الاتصالات وتعقيد الدائرة وتعقيد شجرة القرار .

غالبًا ما يتم التعبير عن تعقيد الخوارزمية باستخدام تدوين O الكبير .

تشير أفضل وأسوأ ومتوسط ​​تعقيد الحالة إلى ثلاث طرق مختلفة لقياس تعقيد الوقت (أو أي مقياس تعقيد آخر) لمدخلات مختلفة بنفس الحجم. نظرًا لأن بعض المدخلات ذات الحجم قد تكون أسرع في الحل من غيرها، فإننا نحدد التعقيدات التالية: ${\displaystyle n}$

1. تعقيد أفضل حالة: هذا هو تعقيد حل المشكلة لأفضل إدخال للحجم .${\displaystyle n}$
2. تعقيد الحالة المتوسطة: هذا هو تعقيد حل المشكلة على متوسط. يتم تعريف هذا التعقيد فقط فيما يتعلق بتوزيع الاحتمالات على المدخلات. على سبيل المثال، إذا افترضنا أن جميع المدخلات ذات الحجم نفسه من المرجح أن تظهر على قدم المساواة، فيمكن تعريف تعقيد الحالة المتوسطة فيما يتعلق بالتوزيع الموحد على جميع المدخلات ذات الحجم .${\displaystyle n}$
3. التحليل المستهلك : يأخذ التحليل المستهلك في الاعتبار العمليات الأكثر تكلفة والأقل تكلفة معًا على مدار سلسلة عمليات الخوارزمية بأكملها.
4. تعقيد أسوأ الحالات: هذا هو تعقيد حل المشكلة لأسوأ مدخلات الحجم .${\displaystyle n}$

الترتيب من الأرخص إلى الأغلى هو: الأفضل، المتوسط ​​( للتوزيع المنتظم المنفصل )، المقسط، الأسوأ.

على سبيل المثال، تعالج خوارزمية الفرز الحتمية quicksort مشكلة فرز قائمة من الأعداد الصحيحة. أسوأ حالة هي عندما يكون المحور دائمًا هو القيمة الأكبر أو الأصغر في القائمة (لذا لا يتم تقسيم القائمة أبدًا). ​​في هذه الحالة، تستغرق الخوارزمية وقتًا O ( ). إذا افترضنا أن جميع التباديل الممكنة لقائمة الإدخال متساوية الاحتمال، فإن متوسط ​​الوقت المستغرق للفرز هو . تحدث أفضل حالة عندما يقسم كل محور القائمة إلى نصفين، مما يتطلب وقتًا أيضًا. ${\displaystyle n^{2}}$${\displaystyle O(n\log n)}$${\displaystyle O(n\log n)}$

لتصنيف وقت الحساب (أو الموارد المماثلة، مثل استهلاك المساحة)، من المفيد إظهار الحدود العليا والسفلى للحد الأقصى للوقت المطلوب من قبل الخوارزمية الأكثر كفاءة لحل مشكلة معينة. عادة ما يتم اعتبار تعقيد الخوارزمية على أنه أسوأ تعقيد لها ما لم يتم تحديد خلاف ذلك. يقع تحليل خوارزمية معينة ضمن مجال تحليل الخوارزميات . لإظهار الحد الأعلى لتعقيد وقت المشكلة، يحتاج المرء فقط إلى إظهار وجود خوارزمية معينة بوقت تشغيل لا يزيد عن . ومع ذلك، فإن إثبات الحدود الدنيا أصعب بكثير، لأن الحدود الدنيا تقدم بيانًا حول جميع الخوارزميات الممكنة لحل مشكلة معينة. لا تشمل عبارة "جميع الخوارزميات الممكنة" الخوارزميات المعروفة اليوم فحسب، بل وأي خوارزمية قد يتم اكتشافها في المستقبل. يتطلب إظهار الحد الأدنى لمشكلة ما إظهار أنه لا يمكن لأي خوارزمية أن يكون تعقيدها الزمني أقل من . ${\displaystyle T(n)}$${\displaystyle T(n)}$${\displaystyle T(n)}$${\displaystyle T(n)}$

عادةً ما يتم تحديد الحدود العليا والسفلى باستخدام ترميز O الكبير ، والذي يخفي العوامل الثابتة والمصطلحات الأصغر. وهذا يجعل الحدود مستقلة عن التفاصيل المحددة للنموذج الحسابي المستخدم. على سبيل المثال، إذا ، في ترميز O الكبير، نكتب . ${\displaystyle T(n)=7n^{2}+15n+40}$${\displaystyle T(n)=O(n^{2})}$

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

• نوع المشكلة الحسابية: المشاكل الأكثر استخدامًا هي مشاكل القرار. ومع ذلك، يمكن تعريف فئات التعقيد بناءً على مشاكل الوظيفة ، ومشاكل العد ، ومشاكل التحسين ، ومشاكل الوعد ، وما إلى ذلك.
• نموذج الحساب: النموذج الأكثر شيوعًا للحوسبة هو آلة تورينج الحتمية، ولكن العديد من فئات التعقيد تعتمد على آلات تورينج غير الحتمية، والدوائر المنطقية ، وآلات تورينج الكمومية ، والدوائر الرتيبة ، وما إلى ذلك.
• المورد (أو الموارد) التي يتم تحديدها والحد: عادةً ما يتم ذكر هاتين الخاصيتين معًا، مثل "الوقت الحدودي"، و"الفضاء اللوغاريتمي"، و"العمق الثابت"، وما إلى ذلك.

تحتوي بعض فئات التعقيد على تعريفات معقدة لا تتناسب مع هذا الإطار. وبالتالي، فإن فئة التعقيد النموذجية لها تعريف مثل التعريف التالي:

مجموعة مشاكل القرار التي يمكن حلها بواسطة آلة تورينج حتمية في غضون فترة زمنية . (تُعرف فئة التعقيد هذه باسم DTIME( ).)${\displaystyle f(n)}$${\displaystyle f(n)}$

لكن تحديد وقت الحساب أعلاه بواسطة بعض الوظائف الملموسة غالبًا ما ينتج فئات تعقيد تعتمد على نموذج الآلة المختار. على سبيل المثال، يمكن حل اللغة في وقت خطي على آلة تورينج متعددة الأشرطة، لكنها تتطلب بالضرورة وقتًا تربيعيًا في نموذج آلات تورينج ذات الشريط المفرد. إذا سمحنا بالاختلافات متعددة الحدود في وقت التشغيل، تنص أطروحة كوبهام-إدموندز على أن "تعقيدات الوقت في أي نموذجين معقولين وعامّين للحساب مرتبطة متعدد الحدود" (جولدريتش 2008، الفصل 1.2). يشكل هذا الأساس لفئة التعقيد P ، وهي مجموعة مشاكل القرار التي يمكن حلها بواسطة آلة تورينج حتمية في غضون وقت متعدد الحدود. المجموعة المقابلة من مشاكل الوظيفة هي FP . ${\displaystyle f(n)}$${\displaystyle \{xx\mid x{\text{ هو أي سلسلة ثنائية}}\}}$

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

الموارد	الحتمية	فئة التعقيد	قيود الموارد
فضاء	غير حتمية	إن سبيس ( ) ${\displaystyle f(n)}$	${\displaystyle O(f(n))}$
		هولندا	${\displaystyle O(\log n)}$
		إن بي سبيس	${\displaystyle O({\text{poly}}(n))}$
		نيكس سبيس	${\displaystyle O(2^{\text{poly}}(n)})}$
	حتمية	دي سبيس ( ) ${\displaystyle f(n)}$	${\displaystyle O(f(n))}$
		ل	${\displaystyle O(\log n)}$
		بي سبيس	${\displaystyle O({\text{poly}}(n))}$
		مساحة اضافية	${\displaystyle O(2^{\text{poly}}(n)})}$
وقت	غير حتمية	الوقت غير محدد ( ) ${\displaystyle f(n)}$	${\displaystyle O(f(n))}$
		ن ب	${\displaystyle O({\text{poly}}(n))}$
		الوقت القادم	${\displaystyle O(2^{\text{poly}}(n)})}$
	حتمية	الوقت ( ) ${\displaystyle f(n)}$	${\displaystyle O(f(n))}$
		ص	${\displaystyle O({\text{poly}}(n))}$
		الوقت المستغرق	${\displaystyle O(2^{\text{poly}}(n)})}$

لا تأخذ فئات المساحة اللوغاريتمية في الاعتبار المساحة المطلوبة لتمثيل المشكلة.

يتبين أن PSPACE = NPSPACE و EXPSPACE = NEXPSPACE حسب نظرية سافيتش .

تشمل فئات التعقيد المهمة الأخرى BPP و ZPP و RP ، والتي يتم تعريفها باستخدام آلات تورينج الاحتمالية ؛ و AC و NC ، والتي يتم تعريفها باستخدام الدوائر المنطقية؛ و BQP و QMA ، والتي يتم تعريفها باستخدام آلات تورينج الكمومية. #P هي فئة تعقيد مهمة لمشكلات العد (وليس مشاكل القرار). يتم تعريف فئات مثل IP و AM باستخدام أنظمة الإثبات التفاعلية . ALL هي فئة جميع مشاكل القرار.

بالنسبة لفئات التعقيد المحددة بهذه الطريقة، من المرغوب فيه إثبات أن تخفيف المتطلبات على (على سبيل المثال) وقت الحساب يحدد بالفعل مجموعة أكبر من المشكلات. على وجه الخصوص، على الرغم من أن DTIME( ) موجود في DTIME( )، سيكون من المثير للاهتمام معرفة ما إذا كان التضمين صارمًا. بالنسبة لمتطلبات الوقت والمكان، يتم تقديم الإجابة على مثل هذه الأسئلة من خلال نظريات التسلسل الهرمي للوقت والمكان على التوالي. تسمى نظريات التسلسل الهرمي لأنها تحفز التسلسل الهرمي المناسب للفئات المحددة من خلال تقييد الموارد المعنية. وبالتالي، توجد أزواج من فئات التعقيد بحيث يتم تضمين إحداها بشكل صحيح في الأخرى. بعد استنتاج مثل هذه التضمينات المناسبة للمجموعة، يمكننا المضي قدمًا في تقديم بيانات كمية حول مقدار الوقت الإضافي أو المساحة المطلوبة من أجل زيادة عدد المشكلات التي يمكن حلها. ${\displaystyle n}$${\displaystyle n^{2}}$

وبصورة أدق، تنص نظرية التسلسل الزمني على أن . ${\displaystyle {\mathsf {DTIME}}{\big (}o(f(n)){\big )}\subsetneq {\mathsf {DTIME}}{\big (}f(n)\cdot \log(f(n)){\big )}}$

تنص نظرية التسلسل الهرمي للفضاء على أن . ${\displaystyle {\mathsf {DSPACE}}{\big (}o(f(n)){\big )}\subsetneq {\mathsf {DSPACE}}{\big (}f(n){\big )}}$

تشكل نظريات التسلسل الهرمي للزمان والمكان الأساس لمعظم نتائج الفصل بين فئات التعقيد. على سبيل المثال، تخبرنا نظرية التسلسل الهرمي للزمان أن P محصور بشكل صارم في EXPTIME، وتخبرنا نظرية التسلسل الهرمي للمكان أن L محصور بشكل صارم في PSPACE.

يتم تعريف العديد من فئات التعقيد باستخدام مفهوم الاختزال. الاختزال هو تحويل مشكلة إلى مشكلة أخرى. إنه يلتقط المفهوم غير الرسمي للمشكلة التي تكون في أقصى حد بنفس صعوبة مشكلة أخرى. على سبيل المثال، إذا كان من الممكن حل مشكلة باستخدام خوارزمية لـ ، ليست أكثر صعوبة من ، ونقول إنها تُختزل إلى . هناك العديد من أنواع الاختزال المختلفة، بناءً على طريقة الاختزال، مثل اختزالات كوك واختزالات كارب واختزالات ليفين، والحد الأقصى لتعقيد الاختزالات، مثل الاختزالات في زمن كثير الحدود أو الاختزالات في مساحة اللوغاريتم . ${\displaystyle X}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle X}$ ${\displaystyle Y}$

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

هذا يحفز مفهوم كون المشكلة صعبة بالنسبة لفئة التعقيد. تكون المشكلة صعبة بالنسبة لفئة من المشاكل إذا كان من الممكن تقليل كل مشكلة في إلى . وبالتالي لا توجد مشكلة في أصعب من ، لأن الخوارزمية لـ تسمح لنا بحل أي مشكلة في . يعتمد مفهوم المشاكل الصعبة على نوع الاختزال المستخدم. بالنسبة لفئات التعقيد الأكبر من P، تُستخدم عادةً عمليات الاختزال في زمن كثير الحدود. وعلى وجه الخصوص، فإن مجموعة المشاكل الصعبة بالنسبة لـ NP هي مجموعة مشاكل NP-hard .${\displaystyle X}$${\displaystyle C}$${\displaystyle C}$${\displaystyle X}$${\displaystyle C}$${\displaystyle X}$${\displaystyle X}$${\displaystyle C}$

إذا كانت المشكلة في وصعبة بالنسبة لـ ، فيقال إنها مكتملة بالنسبة لـ . وهذا يعني أن هذه هي أصعب مشكلة في . (نظرًا لأن العديد من المشكلات يمكن أن تكون بنفس الصعوبة، فقد يقال إن هذه هي واحدة من أصعب المشكلات في .) وبالتالي فإن فئة المشكلات NP-complete تحتوي على أصعب المشكلات في NP، بمعنى أنها الأكثر احتمالاً ألا تكون في P. ولأن المشكلة P = NP لم يتم حلها، فإن القدرة على اختزال مشكلة معروفة NP-complete، ، إلى مشكلة أخرى، ، يشير إلى عدم وجود حل معروف في زمن كثير الحدود لـ . وذلك لأن الحل في زمن كثير الحدود لـ من شأنه أن يعطي حلاً في زمن كثير الحدود لـ . وبالمثل، نظرًا لأنه يمكن اختزال جميع مشكلات NP إلى المجموعة، فإن إيجاد مشكلة كاملة NP يمكن حلها في زمن كثير الحدود يعني أن P = NP. ^[3]${\displaystyle X}$${\displaystyle C}$${\displaystyle C}$${\displaystyle X}$${\displaystyle C}$${\displaystyle X}$${\displaystyle C}$${\displaystyle X}$${\displaystyle C}$${\displaystyle \Pi _{2}}$${\displaystyle \Pi _{1}}$${\displaystyle \Pi _{1}}$${\displaystyle \Pi _{1}}$${\displaystyle \Pi _{2}}$

غالبًا ما يُنظر إلى فئة التعقيد P على أنها تجريد رياضي يحاكي تلك المهام الحسابية التي تسمح بخوارزمية فعالة. تسمى هذه الفرضية أطروحة كوبهام-إدموندز . من ناحية أخرى، تحتوي فئة التعقيد NP على العديد من المشكلات التي يرغب الناس في حلها بكفاءة، ولكن لا توجد خوارزمية فعالة معروفة لها، مثل مشكلة قابلية الإرضاء البوليانية ومشكلة المسار الهاميلتوني ومشكلة غطاء الرأس . نظرًا لأن آلات تورينج الحتمية هي آلات تورينج غير حتمية خاصة، فمن السهل ملاحظة أن كل مشكلة في P هي أيضًا عضو في الفئة NP.

إن مسألة ما إذا كان P يساوي NP هي واحدة من أهم الأسئلة المفتوحة في علوم الكمبيوتر النظرية بسبب الآثار الواسعة للحل. ^[3] إذا كانت الإجابة بنعم، فيمكن إظهار أن العديد من المشكلات المهمة لها حلول أكثر كفاءة. وتشمل هذه أنواعًا مختلفة من مشاكل برمجة الأعداد الصحيحة في بحوث العمليات ، والعديد من المشكلات في اللوجستيات ، وتوقع بنية البروتين في علم الأحياء ، ^[5] والقدرة على إيجاد أدلة رسمية لنظريات الرياضيات البحتة . ^[6] تعد مشكلة P مقابل NP واحدة من مشاكل جائزة الألفية التي اقترحها معهد كلاي للرياضيات . هناك جائزة قدرها مليون دولار أمريكي لحل المشكلة. ^[7]

أظهر لادنر أنه إذا كانت هناك مشكلات في ليست كاملة ولا غير كاملة. ^[4] تسمى مثل هذه المشكلات بمشكلات وسيطة NP . تعد مشكلة تماثل الرسم البياني ومشكلة اللوغاريتم المنفصل ومشكلة تحليل العوامل الصحيحة أمثلة على المشكلات التي يُعتقد أنها وسيطة NP. وهي بعض من مشكلات NP القليلة جدًا التي لا يُعرف أنها كاملة أو غير كاملة. ${\displaystyle P\neq NP}$${\displaystyle NP}$${\displaystyle P}$${\displaystyle NP}$${\displaystyle P}$${\displaystyle NP}$

مشكلة تماثل الرسم البياني هي المشكلة الحسابية لتحديد ما إذا كان رسمان بيانيان منتهيان متماثلين . هناك مشكلة مهمة لم يتم حلها في نظرية التعقيد وهي ما إذا كانت مشكلة تماثل الرسم البياني في حالة , - كاملة أو NP- وسيطة. الإجابة غير معروفة، ولكن يُعتقد أن المشكلة على الأقل ليست NP- كاملة. ^[8] إذا كان تماثل الرسم البياني مكتملًا NP، فإن التسلسل الهرمي الزمني متعدد الحدود ينهار إلى مستواه الثاني. ^[9] نظرًا للاعتقاد السائد بأن التسلسل الهرمي متعدد الحدود لا ينهار إلى أي مستوى منتهٍ، فمن المعتقد أن تماثل الرسم البياني ليس NP- كامل. أفضل خوارزمية لهذه المشكلة، بسبب لازلو باباي ويوجين لوكس، هي وقت التشغيل للرسوم البيانية ذات الرؤوس، على الرغم من أن بعض الأعمال الأخيرة التي قام بها باباي تقدم بعض وجهات النظر الجديدة المحتملة حول هذا الموضوع. ^[10]${\displaystyle P}$${\displaystyle NP}$${\displaystyle O(2^{\sqrt {n\log n}})}$${\displaystyle n}$

مشكلة تحليل العوامل الصحيحة هي المشكلة الحسابية لتحديد التحليل الأولي لعدد صحيح معين. وبعبارة أخرى مشكلة اتخاذ قرار، فهي مشكلة تحديد ما إذا كان المدخل يحتوي على عامل أولي أقل من . لا توجد خوارزمية فعالة لتحليل العوامل الصحيحة معروفة، وتشكل هذه الحقيقة الأساس للعديد من أنظمة التشفير الحديثة، مثل خوارزمية RSA . مشكلة تحليل العوامل الصحيحة هي in و in (وحتى في UP وco-UP ^[11] ). إذا كانت المشكلة مكتملة، فإن التسلسل الهرمي لوقت كثير الحدود سينهار إلى مستواه الأول (أي يساوي ). أفضل خوارزمية معروفة لتحليل العوامل الصحيحة هي غربال حقل الأعداد العام ، والذي يستغرق وقتًا ^[12] لتحليل عدد صحيح فردي إلى عوامل . ومع ذلك، فإن أفضل خوارزمية كمية معروفة لهذه المشكلة، خوارزمية شور ، تعمل في وقت كثير الحدود. لسوء الحظ، لا تقول هذه الحقيقة الكثير عن مكان المشكلة فيما يتعلق بفئات التعقيد غير الكمومي. ${\displaystyle k}$${\displaystyle NP}$${\displaystyle كو{\text{-}}NP}$${\displaystyle NP}$${\displaystyle NP}$${\displaystyle كو{\text{-}}NP}$${\displaystyle O(e^{\left({\sqrt[{3}]{\frac {64}{9}}}\right){\sqrt[{3}]{(\log \log n)}}{\sqrt[{3}]{(\log \log n)^{2}}}})}$${\displaystyle n}$

يُشتبه في أن العديد من فئات التعقيد المعروفة غير متساوية، ولكن لم يتم إثبات ذلك. على سبيل المثال ، ولكن من الممكن أن . إذا لم تكن مساوية لـ ، إذن فهي ليست مساوية لأي منهما. نظرًا لوجود العديد من فئات التعقيد المعروفة بين و ، مثل ، ، ، ، ، ، إلخ، فمن الممكن أن تنهار كل فئات التعقيد هذه إلى فئة واحدة. إن إثبات أن أيًا من هذه الفئات غير متساوية سيكون تقدمًا كبيرًا في نظرية التعقيد. ${\displaystyle P\subseteq NP\subseteq PP\subseteq PSPACE}$${\displaystyle P=PSPACE}$${\displaystyle P}$${\displaystyle NP}$${\displaystyle P}$${\displaystyle PSPACE}$${\displaystyle P}$${\displaystyle PSPACE}$${\displaystyle RP}$${\displaystyle BPP}$${\displaystyle PP}$${\displaystyle BQP}$${\displaystyle MA}$${\displaystyle PH}$

على نفس المنوال، هي الفئة التي تحتوي على مشاكل المكمل (أي المشاكل التي تكون فيها إجابات نعم / لا معكوسة) للمشاكل. يُعتقد ^[13] أن لا يساوي ؛ ومع ذلك، لم يتم إثبات ذلك بعد. من الواضح أنه إذا لم تكن هاتان الفئتان المعقدتان متساويتين، فإن لا يساوي ، لأن . وبالتالي إذا كان لدينا من أين . ${\displaystyle كو{\text{-}}NP}$${\displaystyle NP}$${\displaystyle NP}$${\displaystyle كو{\text{-}}NP}$${\displaystyle P}$${\displaystyle NP}$${\displaystyle P=co{\text{-}}P}$${\displaystyle P=NP}$${\displaystyle co{\text{-}}P=co{\text{-}}NP}$${\displaystyle NP=P=co{\text{-}}P=co{\text{-}}NP}$

وبالمثل، ليس من المعروف ما إذا كانت (مجموعة جميع المشكلات التي يمكن حلها في الفضاء اللوغاريتمي) موجودة بدقة في أو تساوي . مرة أخرى، هناك العديد من فئات التعقيد بين الاثنين، مثل و ، وليس من المعروف ما إذا كانت فئات متميزة أو متساوية. ${\displaystyle L}$${\displaystyle P}$${\displaystyle P}$${\displaystyle NL}$${\displaystyle NC}$

يُشتبه في أن و متساويان. ومع ذلك، فهو مفتوح حاليًا إذا . ${\displaystyle P}$${\displaystyle BPP}$${\displaystyle BPP=NEXP}$

المشكلة التي يمكن حلها نظريًا، ولكنها تتطلب موارد غير عملية ومحدودة (مثل الوقت) للقيام بذلك، تُعرف باسممشكلة مستعصية على الحل .^[14]وعلى العكس من ذلك، فإن المشكلة التي يمكن حلها عمليًا تسمىمشكلة قابلة للحل ، حرفيًا "مشكلة يمكن التعامل معها". يُستخدم مصطلحغير قابل للحل(حرفيًا "لا يمكن القيام به") أحيانًا بالتبادل معمستعصي،^[15]على الرغم من أن هذا قد يؤدي إلى الخلط معالحل القابل للحلفيالتحسين الرياضي.^[16]

غالبًا ما يتم التعرف على المشكلات القابلة للحل بالمشكلات التي لها حلول في زمن متعدد الحدود ( ، )؛ وهذا ما يُعرف بأطروحة كوبهام-إدموندز . تتضمن المشكلات المعروفة بأنها مستعصية على الحل بهذا المعنى تلك التي يصعب حلها باستخدام EXPTIME . إذا لم يكن هو نفسه ، فإن المشكلات الصعبة NP تكون أيضًا مستعصية على الحل بهذا المعنى. ${\displaystyle P}$${\displaystyle PTIME}$${\displaystyle NP}$${\displaystyle P}$

ومع ذلك، فإن هذا التعريف غير دقيق: فالحل في زمن كثير الحدود بدرجة كبيرة أو معامل رئيسي كبير ينمو بسرعة، وقد يكون غير عملي لمشاكل الحجم العملي؛ وعلى العكس من ذلك، فإن الحل في الزمن الأسي الذي ينمو ببطء قد يكون عمليًا على المدخلات الواقعية، أو قد يستغرق الحل الذي يستغرق وقتًا طويلاً في أسوأ الحالات وقتًا قصيرًا في معظم الحالات أو الحالة المتوسطة، وبالتالي لا يزال عمليًا. إن القول بأن المشكلة ليست في لا يعني أن جميع الحالات الكبيرة للمشكلة صعبة أو حتى أن معظمها كذلك. على سبيل المثال، ثبت أن مشكلة القرار في حساب بريسبرجر ليست في ، ومع ذلك فقد تمت كتابة خوارزميات تحل المشكلة في أوقات معقولة في معظم الحالات. وبالمثل، يمكن للخوارزميات حل مشكلة حقيبة الظهر الكاملة NP على نطاق واسع من الأحجام في أقل من الوقت التربيعي، وتتعامل حلول SAT بشكل روتيني مع حالات كبيرة من مشكلة قابلية الإرضاء المنطقية الكاملة NP . ${\displaystyle P}$${\displaystyle P}$

ولكي نرى لماذا لا يمكن استخدام خوارزميات الزمن الأسي بشكل عام في الممارسة العملية، فلنتأمل برنامجًا يجري عمليات قبل التوقف. بالنسبة للكميات الصغيرة ، لنقل 100، وعلى سبيل المثال، بافتراض أن الكمبيوتر يجري عمليات في كل ثانية، فإن البرنامج سيعمل لمدة تقارب 100 عام، وهو نفس ترتيب حجم عمر الكون . وحتى مع وجود كمبيوتر أسرع كثيرًا، فإن البرنامج لن يكون مفيدًا إلا في الحالات الصغيرة جدًا، وبهذا المعنى فإن صعوبة حل المشكلة لا تعتمد إلى حد ما على التقدم التكنولوجي. ومع ذلك، فإن خوارزمية الزمن الأسي التي تجري عمليات تكون عملية حتى تصبح كبيرة نسبيًا. ${\displaystyle 2^{n}}$${\displaystyle n}$${\displaystyle 10^{12}}$${\displaystyle 4\times 10^{10}}$${\displaystyle 1.0001^{n}}$${\displaystyle n}$

على نحو مماثل، لا تكون خوارزمية الوقت متعدد الحدود عملية دائمًا. فإذا كان وقت تشغيلها، على سبيل المثال، ، فمن غير المعقول اعتبارها فعّالة ولا تزال عديمة الفائدة إلا في الحالات الصغيرة. والواقع أن الخوارزميات التي يبلغ طولها أو غالبًا ما تكون غير عملية في التعامل مع أحجام واقعية من المشكلات. ${\displaystyle n^{15}}$${\displaystyle n^{3}}$${\displaystyle n^{2}}$

يمكن أن تشير نظرية التعقيد المستمر إلى نظرية التعقيد للمشاكل التي تنطوي على وظائف مستمرة يتم تقريبها عن طريق التقديرات، كما هو مدروس في التحليل العددي . أحد الأساليب المستخدمة في نظرية التعقيد للتحليل العددي ^[17] هو التعقيد القائم على المعلومات .

يمكن أن تشير نظرية التعقيد المستمر أيضًا إلى نظرية التعقيد لاستخدام الحوسبة التناظرية ، والتي تستخدم الأنظمة الديناميكية المستمرة والمعادلات التفاضلية . ^{[18] يمكن اعتبار} نظرية التحكم شكلاً من أشكال الحوسبة، وتُستخدم المعادلات التفاضلية في نمذجة الأنظمة الهجينة المستمرة والمتقطعة المستمرة في الوقت. ^[19]

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

قبل أن تبدأ الأبحاث الفعلية المخصصة صراحة لتعقيد المشكلات الخوارزمية، وضع العديد من الباحثين أسسًا عديدة. وكان التعريف الذي قدمه آلان تورينج لآلات تورينج في عام 1936 هو الأكثر تأثيرًا، والذي تبين أنه تبسيط قوي ومرن للغاية للكمبيوتر.

يعود الفضل في بداية الدراسات المنهجية في التعقيد الحسابي إلى الورقة البحثية الرائدة التي نُشرت عام 1965 بعنوان "حول التعقيد الحسابي للخوارزميات" بقلم جوريس هارتمانيس وريتشارد إي ستيرنز ، والتي حددت تعريفات التعقيد الزمني وتعقيد المكان ، وأثبتت نظريات التسلسل الهرمي. ^{[20] بالإضافة إلى ذلك، اقترح} إدموندز في عام 1965 اعتبار الخوارزمية "الجيدة" هي الخوارزمية التي يكون وقت تشغيلها محددًا بكثيرة حدود لحجم الإدخال. ^[21]

تشمل الأوراق السابقة التي تدرس المشكلات التي يمكن حلها بواسطة آلات تورينج بموارد محدودة محددة ^[20] تعريف جون مايهيل للأتمتة المحدودة الخطية (مايهيل 1960)، ودراسة رايموند سموليان للمجموعات الأولية (1961)، بالإضافة إلى ورقة هيساو يامادا ^[22] حول الحسابات في الوقت الفعلي (1962). في وقت سابق إلى حد ما، درس بوريس تراختنبروت (1956)، وهو رائد في هذا المجال من الاتحاد السوفييتي، مقياس تعقيد محدد آخر. ^[23] كما يتذكر:

ومع ذلك، فقد تم تنحية اهتمامي الأولي [بنظرية الأتمتة] جانبًا بشكل متزايد لصالح التعقيد الحسابي، وهو اندماج مثير للطرق التوليفية، الموروثة من نظرية التبديل ، مع الترسانة المفاهيمية لنظرية الخوارزميات. كانت هذه الأفكار قد حدثت لي في وقت سابق في عام 1955 عندما صغت مصطلح "دالة الإشارة"، والتي تُعرف الآن باسم "مقياس التعقيد". ^[24]

في عام 1967، صاغ مانويل بلوم مجموعة من البديهيات (المعروفة الآن باسم بديهيات بلوم ) تحدد الخصائص المرغوبة لمقاييس التعقيد على مجموعة الدوال القابلة للحساب وأثبت نتيجة مهمة، وهي ما يسمى بنظرية التسريع . بدأ المجال في الازدهار في عام 1971 عندما أثبت ستيفن كوك وليونيد ليفين وجود مشاكل ذات صلة عملية وهي NP-complete . في عام 1972، أخذ ريتشارد كارب هذه الفكرة قفزة إلى الأمام من خلال ورقته البحثية الرائدة، "قابلية الاختزال بين المشاكل التوافقية"، حيث أظهر أن 21 مشكلة نظرية تركيبية ورسمية متنوعة ، كل منها سيئة السمعة بسبب صعوبة حلها الحسابية، هي NP-complete. ^[25]

• ووبولوري، شيام؛ دوريا، فرانسيسكو أ.، محرران (2020)، كشف التعقيد: حياة وعمل جريجوري تشايتين، وورلد ساينتيفيك، doi :10.1142/11270، ISBN 978-981-12-0006-9، S2CID  198790362

• أرورا، سانجيف ؛ باراك، بواز (2009)، التعقيد الحسابي: نهج حديث، مطبعة جامعة كامبريدج، رقم ISBN 978-0-521-42426-4، زبل  1193.68112
• داوني، رود؛ فيلوز، مايكل (1999)، التعقيد المعلمي ، دراسات في علوم الكمبيوتر، برلين، نيويورك: سبرينغر فيرلاغ، رقم ISBN 9780387948836
• دو، دينغ تشو؛ Ko، Ker-I (2000)، نظرية التعقيد الحسابي ، جون وايلي وأولاده، ISBN 978-0-471-34506-0
• جاري، مايكل ر .؛ جونسون، ديفيد س. (1979). أجهزة الكمبيوتر والتعقيد: دليل لنظرية اكتمال NP . سلسلة كتب في العلوم الرياضية (الطبعة الأولى). نيويورك: دبليو إتش فريمان وشركاه . رقم ISBN 9780716710455. السيد  0519066. OCLC  247570676.
• جولدريتش، أوديد (2008)، التعقيد الحسابي: منظور مفاهيمي، مطبعة جامعة كامبريدج
• فان ليوين، جان ، محرر (1990)، دليل علوم الكمبيوتر النظرية (المجلد أ): الخوارزميات والتعقيد ، مطبعة معهد ماساتشوستس للتكنولوجيا، رقم ISBN 978-0-444-88071-0
• باباديميتريو، كريستوس (1994)، التعقيد الحسابي (الطبعة الأولى)، أديسون ويسلي، ISBN 978-0-201-53082-7
• سيبسر، مايكل (2006)، مقدمة إلى نظرية الحوسبة (الطبعة الثانية)، الولايات المتحدة الأمريكية: تكنولوجيا دورة تومسون، رقم ISBN 978-0-534-95097-2

• خليل، حاتم؛ أوليري، دانا (1976)، "مراجعة للدراسات الحالية حول تعقيد الخوارزميات للمعادلات التفاضلية الجزئية"، وقائع المؤتمر السنوي حول - ACM 76، ص 197-201، doi :10.1145/800191.805573، ISBN 9781450374897، S2CID  15497394
• كوك، ستيفن (1983)، "نظرة عامة على التعقيد الحسابي"، اتصالات جمعية الحوسبة الآلية ، 26 (6): 400-408، doi : 10.1145/358141.358144 ، ISSN  0001-0782، S2CID  14323396
• فورتنو، لانس؛ هومر، ستيفن (2003)، "تاريخ موجز للتعقيد الحسابي" (PDF) ، نشرة EATCS ، 80 : 95–133
• ميرتنز، ستيفان (2002)، "التعقيد الحسابي للفيزيائيين"، الحوسبة في العلوم والهندسة ، 4 (3): 31-47، arXiv : cond-mat/0012185 ، Bibcode :2002CSE.....4c..31M، doi :10.1109/5992.998639، ISSN  1521-9615، S2CID  633346

• حديقة الحيوان المعقدة
• "فئات التعقيد الحسابي"، موسوعة الرياضيات ، EMS Press ، 2001 [1994]
• سكوت آرونسون: لماذا ينبغي للفلاسفة أن يهتموا بالتعقيد الحسابي