نظرية التعقيد الهيكلي

تُعد نظرية الضغط نظرية مهمة تتعلق بتعقيد الدوال القابلة للحساب .

تنص النظرية على أنه لا توجد فئة تعقيد أكبر ، ذات حدود قابلة للحساب، والتي تحتوي على جميع الدوال القابلة للحساب.

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

تُعدّ نظريات التسلسل الهرمي الزمني من أهمّ العبارات المتعلقة بالحسابات المحدودة زمنيًا على آلات تورينج . وبصورة مبسطة، تنصّ هذه النظريات على أنه إذا أُتيح لآلة تورينج وقتٌ أطول، فإنها تستطيع حلّ عددٍ أكبر من المسائل. فعلى سبيل المثال، هناك مسائل يمكن حلّها في زمن ^مقداره n²، ولكن لا يمكن حلّها في زمن مقداره n .

نظرية فاليانت-فازيراني هي نظرية في نظرية التعقيد الحسابي . وقد أثبتها ليزلي فاليانت وفيجاي فازيراني في بحثهما بعنوان "NP سهل كإيجاد حلول فريدة" المنشور عام 1986. ^{[ 2 ]} تنص النظرية على أنه إذا وُجدت خوارزمية زمنية متعددة الحدود لحل مسألة Unambiguous-SAT ، فإن NP = RP . ويستند البرهان إلى مبرهنة العزل لمولمولي-فازيراني ، والتي استُخدمت لاحقًا في عدد من التطبيقات المهمة في علوم الحاسوب النظرية .

تنص نظرية Sipser–Lautemann أو نظرية Sipser–Gács–Lautemann على أن وقت Bounded-error Propenilistic Polynomial (BPP) موجود في التسلسل الهرمي لوقت متعدد الحدود ، وبشكل أكثر تحديدًا Σ ₂ ∩ Π ₂ .

تُقدّم نظرية سافيتش، التي أثبتها والتر سافيتش عام 1970، علاقة بين تعقيد الفضاء الحتمي وغير الحتمي . وتنص على أنه لأي دالة${\displaystyle f\in \Omega (\log(n))}$،

${\displaystyle {\mathsf {NSPACE}}\left(f\left(n\right)\right)\subseteq {\mathsf {DSPACE}}\left(\left(f\left(n\right)\right)^{2}\right).}$

تُعدّ نظرية تودا نتيجةً أثبتها سينوسوكي تودا في بحثه "PP صعبٌ مثل التسلسل الهرمي متعدد الحدود" (1991)، وحصل على جائزة غودل عام 1998. تنصّ النظرية على أن التسلسل الهرمي متعدد الحدود PH بأكمله مُحتوى في P ^PP ؛ وهذا يستلزم عبارةً وثيقة الصلة، وهي أن PH مُحتوى في P ^#P .

تم إثبات نظرية إيمرمان-سيليبكسيني بشكل مستقل من قبل نيل إيمرمان وروبرت سيليبكسيني عام 1987، وحصلا على جائزة غودل عام 1995. تنص النظرية في صيغتها العامة على أن NSPACE ( s ( n )) = co-NSPACE( s ( n )) لأي دالة s ( n ) ≥ log n . ويمكن التعبير عن النتيجة بشكل مكافئ على أنها NL = co-NL؛ على الرغم من أن هذه حالة خاصة عندما s ( n ) = log n ، إلا أنها تستلزم النظرية العامة باستخدام حجة الحشو القياسية . وقد حلت هذه النتيجة مشكلة LBA الثانية .