التسلسل الهرمي متعدد الحدود

📅 آخر تحديث: ٣ أغسطس ٢٠٢٦
✍️ نُشر في: ٣ أغسطس ٢٠٢٦
📷 يحتوي على 65 صور
الموسوعة الحرة

في نظرية التعقيد الحسابي ، يُعرَّف التسلسل الهرمي متعدد الحدود (أو التسلسل الهرمي متعدد الحدود الزمني ) بأنه تسلسل هرمي لفئات التعقيد يُعمِّم الفئتين NP و co-NP . [ 1 ] تندرج كل فئة في هذا التسلسل ضمن فضاء PSPACE . ويمكن تعريف هذا التسلسل باستخدام آلات أوراكل أو آلات تورينج المتناوبة . وهو نظير محدود الموارد للتسلسل الهرمي الحسابي والتسلسل الهرمي التحليلي في المنطق الرياضي . ويُرمز إلى اتحاد الفئات في هذا التسلسل بالرمز PH .

تتضمن الفئات ضمن التسلسل الهرمي مسائل كاملة (فيما يتعلق بالاختزالات ذات الوقت متعدد الحدود ) تتساءل عما إذا كانت الصيغ المنطقية الكمية صحيحة، وذلك بالنسبة للصيغ التي تتضمن قيودًا على ترتيب المُكمِّم. ومن المعروف أن التساوي بين الفئات في نفس المستوى أو المستويات المتتالية في التسلسل الهرمي سيؤدي إلى "انهيار" التسلسل الهرمي إلى ذلك المستوى.

التعريفات

توجد تعريفات متكافئة متعددة لفئات التسلسل الهرمي متعدد الحدود.

تعريف أوراكل

بالنسبة لتعريف أوراكل للتسلسل الهرمي متعدد الحدود، حدد

Δ0P:=Σ0P:=Π0P:=P،{\displaystyle \Delta _{0}^{\mathrm {P} }:=\Sigma _{0}^{\mathrm {P} }:=\Pi _{0}^{\mathrm {P} }:=\mathrm {P} ,}

حيث P هي مجموعة مسائل القرار القابلة للحل في وقت متعدد الحدود . ثم، بالنسبة لـ i^n ≥ 0، نُعرّف

Δأنا+1P:=PΣأناP{\displaystyle \Delta _{i+1}^{\mathrm {P} }:=\mathrm {P} ^{\Sigma _{i}^{\mathrm {P} }}}
Σأنا+1P:=شمالPΣأناP{\displaystyle \Sigma _{i+1}^{\mathrm {P} }:=\mathrm {NP} ^{\Sigma _{i}^{\mathrm {P} }}}
Πأنا+1P:=جoشمالPΣأناP{\displaystyle \Pi _{i+1}^{\mathrm {P} }:=\mathrm {coNP} ^{\Sigma _{i}^{\mathrm {P} }}}

أينPأ{\displaystyle \mathrm {P} ^{\rm {A}}}هي مجموعة مسائل القرار التي يمكن حلها في وقت متعدد الحدود بواسطة آلة تورينج معززة بأداة أوراكل لمسألة كاملة في الفئة أ؛ الفئاتشمالPأ{\displaystyle \mathrm {NP} ^{\rm {A}}}وجoشمالPأ{\displaystyle \mathrm {coNP} ^{\rm {A}}}يتم تعريفها بشكل مماثل. على سبيل المثال،Σ1P=شمالP،Π1P=جoشمالP{\displaystyle \Sigma _{1}^{\mathrm {P} }=\mathrm {NP} ,\Pi _{1}^{\mathrm {P} }=\mathrm {coNP} }، وΔ2P=PشمالP{\displaystyle \Delta _{2}^{\mathrm {P} }=\mathrm {P^{NP}} }[ 2 ] هي فئة من المسائل التي يمكن حلها في وقت متعدد الحدود بواسطة آلة تورينج حتمية مزودة بأداة أوراكل لبعض المسائل الكاملة من فئة NP.

تعريف الصيغ المنطقية الكمية

بالنسبة للتعريف الوجودي/العالمي للتسلسل الهرمي متعدد الحدود، ليكن L لغة ( أي مسألة قرار ، مجموعة جزئية من {0,1} * )، وليكن p متعدد حدود ، ولنُعرّف

∃صل:={x∈{0،1}* | (∃w∈{0،1}≤ص(|x|))⟨x،w⟩∈ل}،{\displaystyle \exists ^{p}L:=\left\{x\in \{0,1\}^{*}\ \left|\ \left(\exists w\in \{0,1\}^{\leq p(|x|)}\right)\langle x,w\rangle \in L\right.\right\},}

أين⟨x،w⟩∈{0،1}*{\displaystyle \langle x,w\rangle \{0,1\}^{*}}هي ترميز قياسي لزوج السلاسل الثنائية x و w كسلسلة ثنائية واحدة. تمثل اللغة L مجموعة من الأزواج المرتبة من السلاسل، حيث تكون السلسلة الأولى x عنصرًا من∃صل{\displaystyle \exists ^{p}L}والسلسلة الثانية w هي سلسلة "قصيرة" (|w|≤ص(|x|){\displaystyle |w|\leq p(|x|)}شاهد يشهد بأن س عضو في∃صل{\displaystyle \exists ^{p}L}. بعبارة أخرى،x∈∃صل{\displaystyle x\in \exists ^{p}L}إذا وفقط إذا وُجد شاهد قصير w بحيث⟨x،w⟩∈ل{\displaystyle \langle x,w\rangle \in L}وبالمثل، حدد

∀صل:={x∈{0،1}* | (∀w∈{0،1}≤ص(|x|))⟨x،w⟩∈ل}{\displaystyle \forall ^{p}L:=\left\{x\in \{0,1\}^{*}\ \left|\ \left(\forall w\in \{0,1\}^{\leq p(|x|)}\right)\langle x,w\rangle \in L\right.\right\}}

لاحظ أن قوانين دي مورغان لا تزال سارية:(∃صل)ج=∀صلج{\displaystyle \left(\exists ^{p}L\right)^{\rm {c}}=\forall ^{p}L^{\rm {c}}}و(∀صل)ج=∃صلج{\displaystyle \left(\forall ^{p}L\right)^{\rm {c}}=\exists ^{p}L^{\rm {c}}}، حيث L c هو مكمل L.

ليكن C فئة من اللغات. قم بتوسيع هذه المعاملات لتعمل على فئات كاملة من اللغات وفقًا للتعريف.

∃Pج:={∃صل | ص هي متعددة الحدود و ل∈ج}{\displaystyle \exists ^{\mathrm {P} }{\mathcal {C}}:=\left\{\exists ^{p}L\ |\ p{\text{ is a polynomial and }}L\in {\mathcal {C}}\right\}}
∀Pج:={∀صل | ص هي متعددة الحدود و ل∈ج}{\displaystyle \forall ^{\mathrm {P} }{\mathcal {C}}:=\left\{\forall ^{p}L\ |\ p{\text{ is a polynomial and }}L\in {\mathcal {C}}\right\}}

ومرة أخرى، تبقى قوانين دي مورغان سارية:جo∃Pج=∀Pجoج{\displaystyle \mathrm {co} \exists ^{\mathrm {P} }{\mathcal {C}}=\forall ^{\mathrm {P} }\mathrm {co} {\mathcal {C}}}وجo∀Pج=∃Pجoج{\displaystyle \mathrm {co} \forall ^{\mathrm {P} }{\mathcal {C}}=\exists ^{\mathrm {P} }\mathrm {co} {\mathcal {C}}}، أينجoج={لج|ل∈ج}{\displaystyle \mathrm {co} {\mathcal {C}}=\left\{L^{c}|L\in {\mathcal {C}}\right\}}.

يمكن تعريف الفئتين NP و co-NP على النحو التالي:شمالP=∃PP{\displaystyle \mathrm {NP} =\exists ^{\mathrm {P} }\mathrm {P} }، وجoشمالP=∀PP{\displaystyle \mathrm {coNP} =\forall ^{\mathrm {P} }\mathrm {P} }حيث P هي فئة جميع اللغات القابلة للتقرير بشكل ممكن (في زمن متعدد الحدود). ويمكن تعريف التسلسل الهرمي متعدد الحدود بشكل تكراري على النحو التالي:

Σ0P:=Π0P:=P{\displaystyle \Sigma _{0}^{\mathrm {P} }:=\Pi _{0}^{\mathrm {P} }:=\mathrm {P} }
Σك+1P:=∃PΠكP{\displaystyle \Sigma _{k+1}^{\mathrm {P} }:=\exists ^{\mathrm {P} }\Pi _{k}^{\mathrm {P} }}
Πك+1P:=∀PΣكP{\displaystyle \Pi _{k+1}^{\mathrm {P} }:=\forall ^{\mathrm {P} }\Sigma _{k}^{\mathrm {P} }}

لاحظ أنشمالP=Σ1P{\displaystyle \mathrm {NP} =\Sigma _{1}^{\mathrm {P} }}، وجoشمالP=Π1P{\displaystyle \mathrm {coNP} =\Pi _{1}^{\mathrm {P} }}.

يعكس هذا التعريف الصلة الوثيقة بين التسلسل الهرمي متعدد الحدود والتسلسل الهرمي الحسابي ، حيث يؤدي كل من R و RE أدوارًا مماثلة لـ P و NP على التوالي. كما يُعرَّف التسلسل الهرمي التحليلي بطريقة مماثلة لإعطاء تسلسل هرمي لمجموعات جزئية من الأعداد الحقيقية .

تعريف آلات تورينج المتناوبة

آلة تورينغ المتناوبة هي آلة تورينغ غير حتمية ذات حالات غير نهائية مقسمة إلى حالات وجودية وحالات شاملة. وتكون في حالة قبول نهائية من تكوينها الحالي إذا: كانت في حالة وجودية ويمكنها الانتقال إلى تكوين قابل للقبول في النهاية؛ أو كانت في حالة شاملة وكل انتقال يؤدي إلى تكوين قابل للقبول في النهاية؛ أو كانت في حالة قبول. [ 3 ]

نحن نحددΣكP{\displaystyle \Sigma _{k}^{\mathrm {P} }}أن تكون فئة اللغات التي تقبلها آلة تورينج المتناوبة في وقت متعدد الحدود بحيث تكون الحالة الأولية حالة وجودية، وكل مسار يمكن أن تسلكه الآلة يبدل على الأكثر k – 1 مرة بين الحالات الوجودية والشاملة. نُعرّفΠكP{\displaystyle \Pi _{k}^{\mathrm {P} }}وبالمثل، باستثناء أن الحالة الأولية هي حالة شاملة. [ 4 ]

إذا حذفنا شرط إجراء k – 1 تبديلات على الأكثر بين الحالات الوجودية والشاملة، بحيث نكتفي فقط باشتراط أن تعمل آلة تورينج المتناوبة لدينا في وقت متعدد الحدود، فسنحصل على تعريف الفئة AP ، وهو ما يساوي PSPACE . [ 5 ]

العلاقات بين الفئات في التسلسل الهرمي متعدد الحدود

مخطط تبادلي مكافئ للتسلسل الهرمي ذي الوقت متعدد الحدود. تشير الأسهم إلى الاحتواء.

إن اتحاد جميع الفئات في التسلسل الهرمي متعدد الحدود هو فئة التعقيد PH .

تتضمن التعريفات العلاقات التالية:

ΣأناP⊆Δأنا+1P⊆Σأنا+1P{\displaystyle \Sigma _{i}^{\mathrm {P} }\subseteq \Delta _{i+1}^{\mathrm {P} }\subseteq \Sigma _{i+1}^{\mathrm {P} }}
ΠأناP⊆Δأنا+1P⊆Πأنا+1P{\displaystyle \Pi _{i}^{\mathrm {P} }\subseteq \Delta _{i+1}^{\mathrm {P} }\subseteq \Pi _{i+1}^{\mathrm {P} }}
ΣأناP=جoΠأناP{\displaystyle \Sigma _{i}^{\mathrm {P} }=\mathrm {co} \Pi _{i}^{\mathrm {P} }}

بخلاف التسلسلات الهرمية الحسابية والتحليلية، التي من المعروف أن عناصرها صحيحة، يبقى السؤال مفتوحًا حول ما إذا كان أي من هذه العناصر صحيحًا، على الرغم من الاعتقاد السائد بأنها جميعًا صحيحة.ΣكP=Σك+1P{\displaystyle \Sigma _{k}^{\mathrm {P} }=\Sigma _{k+1}^{\mathrm {P} }}أو إن وجدΣكP=ΠكP{\displaystyle \Sigma _{k}^{\mathrm {P} }=\Pi _{k}^{\mathrm {P} }}ثم ينهار التسلسل الهرمي إلى المستوى k : لكلأنا>ك{\displaystyle i>k}،ΣأناP=ΣكP{\displaystyle \Sigma _{i}^{\mathrm {P} }=\Sigma _{k}^{\mathrm {P} }}[ 6 ] وعلى وجه الخصوص ، لدينا الآثار المترتبة التالية التي تنطوي على مشاكل لم يتم حلها:

  • P = NP إذا وفقط إذا كان P = PH . [ 7 ]
  • إذا كان NP = co-NP فإن NP = PH . ( co-NP هوΠ1P{\displaystyle \Pi _{1}^{\mathrm {P} }}.)

تُسمى الحالة التي يكون فيها NP = PH أيضًا بانهيار PH إلى المستوى الثاني . أما الحالة P = NP فتُقابلها انهيار PH إلى P.

مشكلة لم تُحل في علوم الحاسوب
⁠P=؟شمالP{\displaystyle \mathrm {P} {\overset {?}{=}}\mathrm {NP} }⁠
المزيد من المشاكل التي لم يتم حلها في علوم الحاسوب

يُعتبر احتمال الانهيار إلى المستوى الأول مسألة بالغة الصعوبة. ولا يؤمن معظم الباحثين بحدوث الانهيار، حتى إلى المستوى الثاني.

العلاقات مع الصفوف الأخرى

مشكلة لم تُحل في علوم الحاسوب
⁠Pح=؟PSPأجهـ{\displaystyle \mathrm {PH} {\overset {?}{=}}\mathrm {PSPACE} }⁠
المزيد من المشاكل التي لم يتم حلها في علوم الحاسوب
مخطط هاس لفئات التعقيد بما في ذلك P و NP و co-NP و BPP و P/poly و PH و PSPACE

التسلسل الهرمي متعدد الحدود هو نظير (بتعقيد أقل بكثير) للتسلسل الهرمي الأسي والتسلسل الهرمي الحسابي .

من المعروف أن PH مُضمنة ضمن PSPACE ، ولكن ليس من المعروف ما إذا كانت الفئتان متساويتين. إحدى الصياغات المفيدة لهذه المشكلة هي أن PH = PSPACE إذا وفقط إذا لم يكتسب منطق الرتبة الثانية على البنى المحدودة أي قوة إضافية من إضافة عامل إغلاق متعدٍ على علاقات العلاقات (أي على متغيرات الرتبة الثانية). [ 8 ]

إذا احتوى التسلسل الهرمي متعدد الحدود على أي مسائل كاملة ، فإنه سيحتوي على عدد محدود فقط من المستويات المتميزة. وبما أن هناك مسائل كاملة في فضاء PSPACE ، فإننا نعلم أنه إذا كان PSPACE = PH، فإن التسلسل الهرمي متعدد الحدود سينهار، لأن المسألة الكاملة في فضاء PSPACE ستكونΣكP{\displaystyle \Sigma _{k}^{\mathrm {P} }}مسألة كاملة لبعض قيم k . [ 9 ]

تحتوي كل فئة في التسلسل الهرمي متعدد الحدود على≤مP{\displaystyle \leq _{\rm {m}}^{\mathrm {P} }}المسائل الكاملة (المسائل الكاملة في ظل اختزالات متعددة الحدود ذات وقت متعدد الحدود). علاوة على ذلك، فإن كل فئة في التسلسل الهرمي متعدد الحدود مغلقة تحت≤مP{\displaystyle \leq _{\rm {m}}^{\mathrm {P} }}الاختزالات : بمعنى أنه بالنسبة للفئة C في التسلسل الهرمي ولغةل∈ج{\displaystyle L\in {\mathcal {C}}}، لوأ≤مPل{\displaystyle A\leq _{\rm {m}}^{\mathrm {P} }L}، ثمأ∈ج{\displaystyle A\in {\mathcal {C}}}كذلك. تشير هاتان الحقيقتان معًا إلى أنه إذاكأنا{\displaystyle K_{i}}يمثل مشكلة كاملة لـΣأناP{\displaystyle \Sigma _{i}^{\mathrm {P} }}، ثمΣأنا+1P=شمالPكأنا{\displaystyle \Sigma _{i+1}^{\mathrm {P} }=\mathrm {NP} ^{K_{i}}}، وΠأنا+1P=جoشمالPكأنا{\displaystyle \Pi _{i+1}^{\mathrm {P} }=\mathrm {coNP} ^{K_{i}}}. على سبيل المثال،Σ2P=شمالPSأتي{\displaystyle \Sigma _{2}^{\mathrm {P} }=\mathrm {NP} ^{\mathrm {SAT} }}بمعنى آخر، إذا تم تعريف لغة ما بناءً على مرجع ما في C ، فيمكننا أن نفترض أنها مُعرَّفة بناءً على مسألة كاملة لـ C. وبالتالي، تعمل المسائل الكاملة كـ "ممثلات" للفئة التي تكون كاملة بالنسبة لها.

  • نظرية سيبسر-لاوتمان :بPP⊂Σ2P∩Π2P{\displaystyle \mathrm {BPP} \subset \Sigma _{2}^{\mathrm {P} }\cap \Pi _{2}^{\mathrm {P} }}.
  • نظرية كانان :∀ك،Σ2⊄SأناZهـ(نك){\displaystyle \forall k,\Sigma _{2}\not \subset \mathrm {SIZE} (n^{k})}يبقى السؤال مفتوحاً حول ما إذا كانΣ2⊄⋃كSأناZهـ(نك)=P/صoلy{\displaystyle \Sigma _{2}\not \subset \bigcup _{k}\mathrm {SIZE} (n^{k})=\mathrm {P/poly} }.
  • نظرية تودا :Pح⊂P8P{\displaystyle \mathrm {PH} \subset \mathrm {P} ^{\mathrm {\#P} }}.

هناك بعض الأدلة على أن فئة مسائل BQP ، التي يمكن حلها في وقت متعدد الحدود بواسطة حاسوب كمومي ، غير مضمنة في PH؛ ومع ذلك، يُعتقد أيضًا أن PH غير مضمنة في BQP. [ 10 ] [ 11 ]

مشاكل

  • مثال على مشكلة طبيعية فيΣ2P{\displaystyle \Sigma _{2}^{\mathrm {P} }}تبسيط الدوائر : بالنظر إلى عدد k ودائرة A لحساب دالة منطقية f ، حدد ما إذا كانت هناك دائرة تحتوي على k بوابة على الأكثر تحسب نفس الدالة f . ليكن C مجموعة جميع الدوائر المنطقية.
    ل={⟨أ،ك،ب،x⟩∈ج×شمال×ج×{0،1}*|ب لديه على الأكثر ك البوابات، و أ(x)=ب(x)}{\displaystyle L=\left\{\langle A,k,B,x\rangle \in {\mathcal {C}}\times \mathbb {N} \times {\mathcal {C}}\times \{0,1\}^{*}\left|B{\text{ has at most }}k{\text{ gates, and }}A(x)=B(x)\right.\right\}}

    يمكن حسمها في وقت متعدد الحدود. اللغة

    جم={⟨أ،ك⟩∈ج×شمال|توجد دائرة كهربائية ب مع أقصى حد ك البوابات  بحيث أ و ب حساب نفس الدالة}{\displaystyle {\mathit {CM}}=\left\{\langle A,k\rangle \in {\mathcal {C}}\times \mathbb {N} \left|{\begin{matrix}{\text{there exists a circuit }}B{\text{ with at most }}k{\text{ gates }}\\{\text{ such that }}A{\text{ and }}B{\text{ compute the same function}}\end{matrix}}\right.\right\}}
    هي لغة تصغير الدوائر.جم∈Σ2P(=∃P∀PP){\displaystyle {\mathit {CM}}\in \Sigma _{2}^{\mathrm {P} }(=\exists ^{\mathrm {P} }\forall ^{\mathrm {P} }\mathrm {P} )}لأن L قابلة للتقرير في وقت متعدد الحدود ولأنه، معطى⟨أ،ك⟩{\displaystyle \langle A,k\rangle }،⟨أ،ك⟩∈جم{\displaystyle \langle A,k\rangle \in {\mathit {CM}}}إذا وفقط إذا وُجدت دائرة B بحيث يكون لجميع المدخلات x ،⟨أ،ك،ب،x⟩∈ل{\displaystyle \langle A,k,B,x\rangle \in L}.
  • مشكلة كاملة لـΣكP{\displaystyle \Sigma _{k}^{\mathrm {P} }}تُعرف هذه المسألة بمسألة قابلية الإرضاء للصيغ المنطقية الكمية ذات k – 1 تبديلات للمُكمِّمات (يُشار إليها اختصارًا بـ QBF k أو QSAT k ). هذه هي صيغة مسألة قابلية الإرضاء المنطقية لـΣكP{\displaystyle \Sigma _{k}^{\mathrm {P} }}في هذه المسألة، لدينا صيغة منطقية f بمتغيرات مقسمة إلى k مجموعة X1 ، ...، Xk . علينا تحديد ما إذا كان صحيحًا أن
    ∃X1∀X2∃X3...و{\displaystyle \exists X_{1}\forall X_{2}\exists X_{3}\ldots f}

    أي، هل يوجد تعيين للقيم للمتغيرات في X 1 بحيث، لكل تعيينات القيم في X 2 ، يوجد تعيين للقيم للمتغيرات في X 3 ، ... إذا كان f صحيحًا؟

    النسخة المذكورة أعلاه كاملة لـΣكP{\displaystyle \Sigma _{k}^{\mathrm {P} }}الصيغة التي يكون فيها المُكمِّم الأول "للكل"، والثاني "يوجد"، وما إلى ذلك، كاملة لـΠكP{\displaystyle \Pi _{k}^{\mathrm {P} }}كل لغة هي مجموعة فرعية من المشكلة التي تم الحصول عليها عن طريق إزالة قيد k – 1 من التناوبات، وهي مشكلة PSPACE الكاملة TQBF .
  • يمكن العثور في هذا الملخص على قائمة على غرار غاري/جونسون للمسائل المعروفة بأنها كاملة للمستويات الثانية والأعلى من التسلسل الهرمي متعدد الحدود .

انظر أيضاً

مراجع

مراجع عامة

  1. أرورا، سانجيف؛ باراك، بواز (2009). نظرية التعقيد: منهج حديث . مطبعة جامعة كامبريدج. ISBN 978-0-521-42426-4القسم 1.4، "الآلات كأوتار وآلة تورينج العالمية" و1.7، "إثبات النظرية 1.9"
  2. أ. ر. ماير ول . ج. ستوكمير . مسألة التكافؤ للتعبيرات النمطية مع التربيع تتطلب مساحة أسية. في وقائع الندوة الثالثة عشرة لمعهد مهندسي الكهرباء والإلكترونيات حول نظرية التبديل والأتمتة ، الصفحات  125-129 ، 1972. الورقة البحثية التي قدمت التسلسل الهرمي متعدد الحدود.
  3. إل جيه ستوكمير . التسلسل الهرمي متعدد الحدود . علوم الحاسوب النظرية ، المجلد 3 ، الصفحات  1-22 ، 1976.
  4. سي. باباديميتريو . التعقيد الحسابي. أديسون-ويسلي، 1994. الفصل 17. التسلسل الهرمي متعدد الحدود ، الصفحات  409-438 .
  5. مايكل ر. غاري وديفيد س. جونسون (1979). الحواسيب والاستعصاء: دليل لنظرية اكتمال NP . دبليو إتش فريمان. ISBN 0-7167-1045-5.القسم 7.2: التسلسل الهرمي متعدد الحدود، الصفحات  161-167.

الاقتباسات

  1. ↑ أرورا وباراك، 2009، ص 97
  2. ↑ الاكتمال في التسلسل الهرمي متعدد الحدود: خلاصة، إم. شيفر، سي. أومانس
  3. ^ أرورا وباراك، ص 99 – 100
  4. ↑ أرورا وباراك، ص 100
  5. ↑ أرورا وباراك، ص 100
  6. ↑ أرورا وباراك، 2009، النظرية 5.4
  7. ↑ هيماسباندرا، لين (2018). "17.5 فئات التعقيد". في روزن، كينيث هـ. (محرر). دليل الرياضيات المتقطعة والتوافقية . الرياضيات المتقطعة وتطبيقاتها ( الطبعة الثانية). مطبعة سي آر سي. الصفحات 1308-1314 . ISBN   9781351644051.
  8. ^ فيراروتي، فلافيو. فان دن بوش، يناير؛ فيرتيما ، جوني (2018). "التعبير ضمن منطق الإغلاق المتعدي من الدرجة الثانية" . DROPS-IDN/V2/Document/10.4230/LIPIcs.CSL.2018.22 . شلوس-داجستول - Leibniz Zentrum für Informatik. دوى : 10.4230/LIPIcs.CSL.2018.22 . S2CID 4903744 . 
  9. ↑ أرورا وباراك، 2009، الادعاء 5.5
  10. ↑ آرونسون، سكوت (2009). "BQP والتسلسل الهرمي متعدد الحدود". وقائع الندوة الثانية والأربعين حول نظرية الحوسبة (STOC 2009) . رابطة آلات الحوسبة . الصفحات 141-150 . arXiv : 0910.4698 . doi : 10.1145/1806689.1806711 . ECCC TR09-104 .  
  11. ↑ هارتنيت، كيفن (21 يونيو 2018). "أخيرًا، مشكلة لن تتمكن من حلها إلا الحواسيب الكمومية" . مجلة كوانتا .