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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

للحصول على تعريف دقيق لما يعنيه حل مشكلة ما باستخدام مقدار محدد من الوقت والمساحة، يُستخدم نموذج حسابي مثل آلة تورينج الحتمية . الوقت الذي تتطلبه آلة تورينج الحتمية${\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)}$يُرمز إلى زمن الاستجابة على آلة تورينج الحتمية بالرمز DTIME (${\displaystyle f(n)}$).

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

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

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

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

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

على سبيل المثال، تعالج خوارزمية الفرز الحتمية "الفرز السريع" مشكلة فرز قائمة من الأعداد الصحيحة. أسوأ حالة هي عندما يكون العنصر المحوري دائمًا هو أكبر أو أصغر قيمة في القائمة (وبالتالي لا يتم تقسيم القائمة أبدًا). ​​في هذه الحالة، تستغرق الخوارزمية وقتًا قدره 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)}$.

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

فئة التعقيد هي مجموعة من المسائل ذات التعقيد المترابط. وتُعرَّف فئات التعقيد الأبسط بالعوامل التالية:

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

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

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

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

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

مورد	الحتمية	فئة التعقيد	قيود الموارد
فضاء	غير حتمي	NSPACE (${\displaystyle f(n)}$)	${\displaystyle O(f(n))}$
		هولندا	${\displaystyle O(\log n)}$
		NPSPACE	${\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)})}$
وقت	غير حتمي	NTIME (${\displaystyle f(n)}$)	${\displaystyle O(f(n))}$
		NP	${\displaystyle O({\text{poly}}(n))}$
		نيكست تايم	${\displaystyle O(2^{{\text{poly}}(n)})}$
	حتمية	DTIME (${\displaystyle f(n)}$)	${\displaystyle O(f(n))}$
		P	${\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(${\displaystyle n}$) موجود في DTIME(${\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}$هناك العديد من أنواع الاختزالات المختلفة، بناءً على طريقة الاختزال، مثل اختزالات كوك، واختزالات كارب، واختزالات ليفين، والحد الأقصى لتعقيد الاختزالات، مثل الاختزالات ذات الوقت متعدد الحدود أو الاختزالات ذات المساحة اللوغاريتمية .

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

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

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

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

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

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

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

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

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

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

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

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

• أرورا، سانجيف ؛ باراك، بواز (2009)، التعقيد الحسابي: منهج حديث ، مطبعة جامعة كامبريدج، ISBN 978-0-521-42426-4، Zbl 1193.68112 
• داوني، رود؛ فيلوز، مايكل (1999)، التعقيد المُعَلم ، سلسلة دراسات في علوم الحاسوب، برلين، نيويورك: سبرينغر-فيرلاغ، ISBN 9780387948836
• دو، دينغ تشو؛ Ko، Ker-I (2000)، نظرية التعقيد الحسابي ، جون وايلي وأولاده، ISBN 978-0-471-34506-0
• غاري، مايكل ر .؛ جونسون، ديفيد س. (1979). الحواسيب والاستعصاء: دليل لنظرية اكتمال NP . سلسلة كتب في العلوم الرياضية (  الطبعة الأولى). نيويورك: دبليو إتش فريمان وشركاه . ISBN 9780716710455MR 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) ، نشرة الجمعية الأوروبية لعلوم الحاسوب والأنظمة ، 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