التسلسل الهرمي الأسي

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

فئة التعقيد EH هي اتحاد الفئات${\displaystyle \Sigma _{k}^{\mathsf {E}}}$لكل k ، حيث${\displaystyle \Sigma _{0}^{\mathsf {E}}={\mathsf {E}}}$و${\displaystyle \Sigma _{k}^{\mathsf {E}}={\mathsf {NE}}^{\Sigma _{k-1}^{\mathsf {P}}}}$(أي اللغات القابلة للحساب في وقت غير حتمي )${\displaystyle 2^{cn}}$لبعض الثوابت c مع a${\displaystyle \Sigma _{k-1}^{\mathsf {P}}}$(أوراكل ). كما يُعرّف المرء أيضًا

${\displaystyle \Pi _{k}^{\mathsf {E}}={\mathsf {coNE}}^{\Sigma _{k-1}^{\mathsf {P}}}}$و${\displaystyle \Delta _{k}^{\mathsf {E}}={\mathsf {E}}^{\Sigma _{k-1}^{\mathsf {P}}}.}$

التعريف المكافئ هو أن اللغة L في${\displaystyle \Sigma _{k}^{\mathsf {E}}}$إذا وفقط إذا كان من الممكن كتابتها بالشكل

${\displaystyle x\in L\iff \exists y_{1}\forall y_{2}\dots Qy_{k}R(x,y_{1},\ldots ,y_{k}),}$

أين${\displaystyle R(x,y_{1},\ldots ,y_{n})}$هو مسند قابل للحساب في الوقت${\displaystyle 2^{c|x|}}$(مما يحد ضمنيًا من طول y _i ). وبالمثل، فإن EH هي فئة اللغات القابلة للحساب على آلة تورينج المتناوبة في زمن${\displaystyle 2^{cn}}$لبعض القيم c التي تتضمن العديد من التناوبات باستمرار.

EXPH هو اتحاد الطبقات${\displaystyle \Sigma _{k}^{\mathsf {EXP}}}$، أين${\displaystyle \Sigma _{k}^{\mathsf {EXP}}={\mathsf {NEXP}}^{\Sigma _{k-1}^{\mathsf {P}}}}$(لغات قابلة للحساب في وقت غير حتمي)${\displaystyle 2^{n^{c}}}$لبعض الثوابت c مع a${\displaystyle \Sigma _{k-1}^{\mathsf {P}}}$(أوراكل)${\displaystyle \Sigma _{0}^{\mathsf {EXP}}={\mathsf {EXP}}}$ومرة أخرى:

${\displaystyle \Pi _{k}^{\mathsf {EXP}}={\mathsf {coNEXP}}^{\Sigma _{k-1}^{\mathsf {P}}},\Delta _{k}^{\mathsf {EXP}}={\mathsf {EXP}}^{\Sigma _{k-1}^{\mathsf {P}}}.}$

اللغة L​${\displaystyle \Sigma _{k}^{\mathsf {EXP}}}$إذا وفقط إذا كان من الممكن كتابتها على النحو التالي

${\displaystyle x\in L\iff \exists y_{1}\forall y_{2}\dots Qy_{k}R(x,y_{1},\ldots ,y_{k}),}$

أين${\displaystyle R(x,y_{1},\ldots ,y_{k})}$يمكن حسابها في وقت${\displaystyle 2^{|x|^{c}}}$بالنسبة لبعض قيم c ، والتي تحدد ضمنيًا طول yᵢ _. وبالمثل، فإن EXPH هي فئة اللغات القابلة للحساب في زمن${\displaystyle 2^{n^{c}}}$على آلة تورينج متناوبة ذات عدد كبير من التناوبات باستمرار.

التسلسل الهرمي الأسي القوي، والذي يُرمز إليه بـ SEH، هو اتحاد NE و NP ^NE و NP ^{NP NE} ، وهكذا. ^{[ 4 ]}

نحصل على نفس الفئة إذا استبدلنا NE بـ NEXP. ^{[ 4 ]}

E ⊆ NE ⊆ EH⊆ ESPACE ,

EXP ⊆ NEXP ⊆ EXPH⊆ EXPSPACE ,

EH ⊆ EXPH.

حديقة حيوانات التعقيد : الفئة EH