مشكلة غير أولية

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

عادةً ما يتم عرض التسلسل الهرمي للمشاكل القابلة للحل التي تتجاوز المستوى الابتدائي على طول التسلسل الهرمي سريع النمو . ^{[ 2 ]}

لنفترض أن وظائف التسلسل الهرمي هي${\displaystyle F_{0},F_{1},\dots ,F_{\omega },F_{\omega +1},\dots }$لكل عدد ترتيبي${\displaystyle \alpha }$، نُعرّف الفئة${\displaystyle {\mathcal {F}}_{\alpha }}$أن تكون فئة الدوال القابلة للحساب في الزمن${\displaystyle F_{\alpha }^{(k)}(n)}$، لبعض الثوابت الموجبة${\displaystyle k}$هنا، الترميز${\displaystyle F^{(k)}}$يشير إلى تكرار الدالة : وهي الدالة التي يتم الحصول عليها بتطبيق${\displaystyle F}$مرارا،${\displaystyle k}$مرات. أي،$${\displaystyle {\mathcal {F}}_{\alpha }:=\bigcup _{k=1}^{\infty }{\mathsf {FDTIME}}(F_{\alpha }^{(k)}(n))}$$والآن، حدد${\displaystyle {\mathsf {F}}_{\alpha }}$أن تكون فئة التعقيد${\displaystyle \bigcup _{\beta <\alpha ,p\in {\mathcal {F}}_{\beta }}{\mathsf {DTIME}}(F_{\alpha }(p(n)))}$.

بهذا التعريف، لدينا

• المرحلة الابتدائية: فئة المشكلات التي يمكن حلها في وقت محدد${\displaystyle f(n)}$، أين${\displaystyle f(n)}$هي دالة برجية أسية ذات ارتفاع ثابت. بعبارة أخرى،${\displaystyle {\mathsf {ELEMENTARY}}={\mathsf {DTIME}}(n)\cup {\mathsf {DTIME}}(2^{n})\cup {\mathsf {DTIME}}(2^{2^{n}})\cup \cdots }$.
• برج:${\displaystyle f(n)={\;}^{p(n)}2}$، أين${\displaystyle p(n)}$هي دالة برجية أسية ذات ارتفاع ثابت، ويشير الرمز العلوي إلى التكرار . بعبارة أخرى،${\displaystyle f(n)=F_{3}(p(n))}$. بعبارة أخرى،${\displaystyle {\mathsf {TOWER}}={\mathsf {DTIME}}({}^{n}2)\cup {\mathsf {DTIME}}({}^{2^{n}}2)\cup {\mathsf {DTIME}}({}^{2^{2^{n}}}2)\cup \cdots }$. بعبارة أخرى،${\displaystyle {\mathsf {TOWER}}:={\mathsf {F}}_{3}}$.
• العلاقات العامة:${\displaystyle f(n)}$هي دالة تكرارية بدائية . بعبارة أخرى،${\displaystyle {\mathsf {PR}}={\mathsf {DTIME}}(F_{1})\cup {\mathsf {DTIME}}(F_{2})\cup {\mathsf {DTIME}}(F_{3})\cup \cdots }$.
• إقرار:${\displaystyle f(n)=A(n,n)=F_{\omega }(n)}$، أين${\displaystyle A}$هي دالة أكرمان . بعبارة أخرى،${\displaystyle {\mathsf {ACK}}:={\mathsf {F}}_{\omega }}$

بحسب نظرية التسلسل الزمني ، فإنّ ELEMENTARY وPR لا تُمثّلان مسائل كاملة. بينما تُمثّل TOWER وACK مسائل كاملة.

برج - مسائل كاملة:

• تكافؤ التعبير الخالي من النجوم (SFEq) ^{[ 2 ]}
• إمكانية إرضاء منطق الرتبة الثانية الأحادي الضعيف للخلف الواحد (WS1S) ^{[ 2 ]}
• إمكانية إرضاء الجزء المخدد من منطق الرتبة الأولى لـ WVO Quine ^{[ 3 ]}
• قابلية التحويل β لمصطلحين مغلقين في حساب التفاضل والتكامل لامدا ذي النوع البسيط ^{[ 4 ] [ 5 ]}

ACK - حل المشكلات كاملة:

• إمكانية الوصول في أنظمة جمع المتجهات (VAS). ^{[ 6 ] [ 7 ]}
• إمكانية الوصول في نظام جمع المتجهات المصنف مع الحالات (VASS) ^{[ 8 ]}
• إمكانية الوصول في شبكات بتري . ^{[ 9 ] [ 7 ]}

مشاكل أخرى غير أولية ولكن قابلة للحل:

• مشكلة تكافؤ التعبيرات النمطية مع المكمل ^{[ 10 ]}
• النظرية الأحادية من الدرجة الثانية مع اثنين من الخلفاء ( انظر S2S ) ^{[ 11 ]}
• النظرية من الدرجة الأولى لأي جبر مصطلح في توقيع يحتوي على رمز دالة ثنائية واحد على الأقل ^{[ 12 ]}
• مشكلة الاحتواء المحدود (FCP): بالنظر إلى نظامين افتراضيين (VAS) مع مجموعات وصول محدودة${\displaystyle \operatorname {Reach} (V_{1}),\operatorname {Reach} (V_{2})}$قرر ما إذا${\displaystyle \operatorname {Reach} (V_{1})\subset \operatorname {Reach} (V_{2})}$مستوى تعقيدها الدقيق غير معروف. تجدر الإشارة إلى أن تحديد ما إذا كانت المجموعة التي يمكن الوصول إليها محدودة هو مسألة كاملة من فئة EXPSPACE. ^{[ 2 ]}
• من المعروف أن مشكلتي التغطية والإنهاء لبعض فئات أنظمة الانتقال جيدة التنظيم هما${\displaystyle {\mathsf {F}}_{\omega },{\mathsf {F}}_{\omega ^{\omega }},{\mathsf {F}}_{\omega ^{\omega ^{\omega }}},}$أو${\displaystyle {\mathsf {F}}_{\epsilon _{0}}}$-مكتمل. ^{[ 13 ]}

تم تجميع قائمة كبيرة في ^{[ 2 ]}