التعقيد المُعَلم

FPT (قابلة للحل بمعامل ثابت) هي فئة من مسائل القرار التي يمكن حلها في وقت محدد${\displaystyle f(k)\cdot {|x|}^{O(1)}}$حيث f دالة قابلة للحساب . عادةً ما تُعتبر هذه الدالة دالة أسية أحادية، مثل${\displaystyle 2^{O(k)}}$لكن التعريف يسمح بدوال تنمو بوتيرة أسرع. وهذا أمرٌ جوهريٌّ لجزء كبير من التاريخ المبكر لهذه الفئة. ويتمثل الجزء الحاسم من التعريف في استبعاد الدوال من الشكل التالي:${\displaystyle f(n,k)}$، مثل${\displaystyle k^{n}}$.

تُعرف فئة FPL (الخطية ذات المعاملات الثابتة) بأنها فئة المسائل القابلة للحل في زمن${\displaystyle f(k)\cdot |x|}$بالنسبة لدالة قابلة للحساب f . ^{[ 2 ]} وبالتالي، فإن FPL هي فئة فرعية من FPT. ومن الأمثلة على ذلك مسألة إرضاء الصيغ المنطقية ، والتي تُحدد بعدد المتغيرات. يمكن التحقق من صحة صيغة معينة بحجم m تحتوي على k متغيرًا باستخدام البحث الشامل في زمن${\displaystyle O(2^{k}m)}$يمكن إيجاد غطاء رأس بحجم k في رسم بياني من الرتبة n في وقت${\displaystyle O(2^{k}n)}$لذا فإن مشكلة تغطية الرؤوس موجودة أيضًا في FPL.

من الأمثلة على المشكلات التي يُعتقد أنها لا تندرج ضمن وقت حل المشكلات الأمثل (FPT) تلوين الرسوم البيانية المُعامل بعدد الألوان. من المعروف أن التلوين بثلاثة ألوان هو مسألة صعبة الحل (NP-hard )، وخوارزمية لتلوين الرسوم البيانية بـ k لون في وقت حل المشكلات الأمثل (FPT) هي خوارزمية مُصممة لهذا الغرض.${\displaystyle f(k)n^{O(1)}}$ل${\displaystyle k=3}$سيستغرق تنفيذه وقتًا متعدد الحدود بالنسبة لحجم المدخلات. وبالتالي، إذا كان تلوين الرسم البياني المحدد بعدد الألوان يتم في وقت متعدد الحدود، فإن P  =  NP .

توجد عدة تعريفات بديلة لمصطلح FPT. على سبيل المثال، يمكن استبدال شرط وقت التشغيل بـ${\displaystyle f(k)+|x|^{O(1)}}$كذلك، تُصنّف المسألة المُعَلمة ضمن مسائل FPT إذا كانت تحتوي على ما يُسمى بالنواة. وتُعدّ عملية التَّعَلم تقنيةً مُسبقةً تُختزل المسألة الأصلية إلى "نواة صلبة"، وهي مسألة أصغر حجماً بكثير، تُكافئ المسألة الأصلية ولكن حجمها محدود بدالة في المُعامل.

تُعتبر مسألة FPT مغلقة في ظل مفهوم مُعَلم للاختزالات يُسمى اختزالات FPT . نقول إن مسألة واحدة مُعَلمة${\displaystyle L}$يُختزل fpt إلى${\displaystyle L'}$إذا وُجدت دالتان${\displaystyle (x,k)\mapsto x',k\mapsto k'}$بحيث

• ${\displaystyle (x,k)\in L}$إذا${\displaystyle (x',k')\in L'}$
• ${\displaystyle (x,k)\mapsto x'}$هو نفسه معلمة ثابتة قابلة للتحكم.
  • أي أن هناك ثابتًا${\displaystyle c}$ووظيفة${\displaystyle k\mapsto k''}$بحيث${\displaystyle (x,k)\mapsto x'}$يمكن حسابها في وقت${\displaystyle \leq k''|x|^{c}}$

من الواضح أن FPT تحتوي على جميع المسائل القابلة للحساب في زمن متعدد الحدود. علاوة على ذلك، فهي تحتوي على جميع مسائل التحسين في NP التي تسمح بوجود مخطط تقريبي فعال في زمن متعدد الحدود (EPTAS) .

XP هي فئة من المسائل ذات المعلمات التي يمكن حلها في وقت${\displaystyle n^{f(k)}}$بالنسبة لدالة قابلة للحساب f .

تُسمى هذه المسائل مسائل متعددة الحدود المقطعية ، بمعنى أن لكل "مقطع" من قيمة k ثابتة خوارزمية زمنية متعددة الحدود، وإن كان ذلك بمعامل أسي مختلف لكل قيمة k . قارن هذا بمسألة FPT، التي تسمح فقط بمعامل أسي ثابت مختلف لكل قيمة k.

يحتوي XP بشكل صارم على FPT عن طريق القطرنة.

تُعرف فئة para-NP بأنها فئة من مسائل القرار التي يمكن حلها في وقت غير حتمي${\displaystyle f(k)\cdot |x|^{O(1)}}$بالنسبة لدالة قابلة للحساب f .

${\displaystyle {\textsf {FPT}}={\textsf {para-NP}}}$إذا وفقط إذا${\displaystyle {\textsf {P}}={\textsf {NP}}}$[ ^{3 ]​}

تُعتبر المسألة شبه صعبة من نوع NP إذا كانت${\displaystyle {\textsf {NP}}}$-صعبة بالفعل لقيمة ثابتة للمعامل. أي أن هناك "شريحة" من قيمة k الثابتة التي${\displaystyle {\textsf {NP}}}$-صعبة. مسألة ذات معلمات${\displaystyle {\textsf {para-NP}}}$لا يمكن أن ينتمي -hard إلى الفئة${\displaystyle {\textsf {XP}}}$، إلا إذا${\displaystyle {\textsf {P}}={\textsf {NP}}}$مثال كلاسيكي على${\displaystyle {\textsf {para-NP}}}$تُعدّ مسألة تلوين الرسوم البيانية ، المُحددة بعدد الألوان k ، مسألة صعبة من حيث المعاملات، وهي بالفعل مسألة صعبة من حيث المعاملات.${\displaystyle {\textsf {NP}}}$-صعب من أجل${\displaystyle k=3}$(انظر تلوين الرسم البياني#التعقيد الحسابي ).

بشكل عام، توجد طريقتان لتعريف فئة التعقيد: نظرية الآلة والمنطق. في نظرية الآلة، تُعرَّف الفئة بأنها مجموعة مسائل القرار التي يمكن حلها بواسطة فئة من الآلات. أما في المنطق، فتُعرَّف الفئة بأنها مجموعة مسائل القرار التي يمكن تعريفها بواسطة فئة من الصيغ المنطقية.

من الناحية النظرية للآلة، فإن المسألة ذات المعلمات تنتمي إلى الفئة W[w][d] ، إذا كان هناك اختزال سريع للمسألة على النحو التالي:

• توجد أعداد صحيحة ثابتة${\displaystyle w,d}$بحيث
• في كل حالة${\displaystyle (x,k)}$يتم تحويلها في زمن fpt إلى دائرة منطقية ذات سماكة لا تتجاوز w ، وعمق لا يتجاوز d .
• ${\displaystyle (x,k)\in L}$إذا وفقط إذا كانت الدائرة تحتوي على تعيين مُرضٍ للوزن k .

نلاحظ هنا أن الحرف "W" يرمز إلى "الوزن". لاحظ أنه في التعريف أعلاه،${\displaystyle w,d}$مستقلة عن${\displaystyle (x,k)}$لكن الدائرة نفسها تعتمد على${\displaystyle (x,k)}$وقد يتغير ذلك إذا قام المرء بتغيير أي منهما${\displaystyle x}$أو${\displaystyle k}$.

ثم يتم تعريف الفئة W[w] على أنها اتحادهما:$${\displaystyle W[w][1]\subset W[w][2]\subset \dots \subset W[w]:=\bigcup _{d\geq 1}W[w][d]}$$بإيجاز أكثر، W[w] هي مجموعة المسائل القابلة للاختزال إلى عائلة من الدوائر المنطقية الخاصة بكل حالة مع weft${\displaystyle \leq w}$والعمق محدود بثابت معين خاص بالمشكلة.

الدائرة المعيارية ذات اللحمة w والعمق d هي دائرة، حيث يكون الأول${\displaystyle d-w}$لا تحتوي الطبقات إلا على بوابات صغيرة، والأخيرة${\displaystyle w}$تحتوي الطبقات على بوابات كبيرة متناوبة من نوعي AND و OR. يمكن تكرار قوانين التجميع وقوانين توزيع دي مورغان لتطبيع الدائرة في زمن fpt. لذلك، وبدون فقدان للعمومية، يمكننا الاقتصار على دراسة الدوائر المُطَبَّعة فقط. ^{[ 7 ]}

من الناحية النظرية النموذجية، تُعرَّف الفئة W[t] على أنها فئة المشكلات القابلة للاختزال fpt إلى${\displaystyle \operatorname {p-MC} (\Sigma _{t,1})}$.

بينما يُعدّ التسلسل الهرمي W تسلسلاً هرمياً مُضمّناً في NP، فإن التسلسل الهرمي A يُحاكي بشكلٍ أدق التسلسل الهرمي ذي الوقت متعدد الحدود من التعقيد الكلاسيكي. من الناحية النظرية للآلات، يُعرَّف التسلسل الهرمي A للمسائل بأنه مسائل قابلة للاختزال في وقت fpt إلى عمليات حسابية بواسطة أنواع مُحددة من آلات تورينغ المتناوبة . يشير الحرف "A" إلى "التناوب". ^{[ 6 ]}

من الناحية النظرية النموذجية، تُعرَّف الفئة A[t] على أنها فئة المشكلات القابلة للاختزال fpt إلى${\displaystyle \operatorname {p-MC} (\Sigma _{t})}$.

على سبيل المثال، يمكن تحديد مشكلة k -clique كمشكلة للتحقق من النموذج. تحتوي اللغة على علاقة ثنائية واحدة.${\displaystyle E}$، أين${\displaystyle E(x,y)}$وسائل "${\displaystyle x,y}$"يتشاركون في الحافة". ثم، نموذج محدود${\displaystyle A}$هو رسم بياني، وله مجموعة k إذا وفقط إذا${\displaystyle A\models \phi _{k}}$، أين$${\displaystyle \phi _{k}:=\exists x_{1:k},\bigwedge _{1\leq i<j\leq n}E(x_{i},x_{j})}$$هذا يدل على أن مشكلة k -clique تقع في${\displaystyle A[1]}$.

تكون المشكلة كاملة من النوع A[i] إذا كانت من النوع A[i] ، وأي مشكلة من النوع A[i] تختزل إليها من النوع fpt.

بحسب التعريف،$${\displaystyle W[0]\subset W[1]\subset \cdots ,\quad W[i]\subset A[i],\quad A[0]\subset A[1]\subset \cdots }$$${\displaystyle {\mathsf {FPT}}=W[0]=A[0]}$:

• ${\displaystyle W[0]=A[0]}$منذ${\displaystyle \Sigma _{0}}$لا يحتوي على أي أدوات تحديد كمية على الإطلاق، لذلك لا يوجد فرق بين${\displaystyle \Sigma _{0}}$و${\displaystyle \Sigma _{0,1}}$.
• ${\displaystyle {\mathsf {FPT}}\subset W[0]}$لأي مشكلة من مشاكل FPT${\displaystyle L}$يمكن اختزالها بسهولة باستخدام طريقة fpt كما يلي: حل المسألة${\displaystyle (x,k)\in L}$في زمن fpt، ثم قم بإخراج دائرة نعم/لا بسيطة لا تفعل شيئًا سوى إخراج القيمة المنطقية الصحيحة.
• ${\displaystyle {\mathsf {FPT}}\supset W[0]}$لأي مسألة W[0]${\displaystyle L}$وأي حالة مشكلة${\displaystyle c\in L}$الدوائر الكهربائية${\displaystyle c}$لا يحتوي على لحمة و${\displaystyle \leq d}$العمق، حيث${\displaystyle d}$ثابت. لذلك، يتم تحديد الناتج بما يصل إلى${\displaystyle 2^{d}}$المدخلات. جميع المدخلات الأخرى متاحة للاستخدام. لذلك، يمكن ببساطة حساب جميع المدخلات باستخدام طريقة القوة الغاشمة.${\displaystyle 2^{2^{d}}}$المدخلات الممكنة. إذا كان لمدخل معين وزن k' ويجعل خرج الدائرة صحيحًا، فتحقق مما إذا كانت هناك مدخلات كافية لملء الوزن:${\displaystyle \#({\text{inputs of }}c)-2^{d}\geq k-k'}$.

${\displaystyle W[1]=A[1]}$[ ^{6 ]​}

يمكن تفسير المسائل في فئة W[1] بشكل بديهي على النحو التالي: هل يوجد كائن بحجم k يتمتع بخاصية معينة قابلة للتحقق محليًا؟ رياضيًا، سيكون على النحو التالي:$${\displaystyle \bigvee _{u_{1},\dots ,u_{k}}({\text{object constructed according to }}u_{1},\dots ,u_{k}{\text{ has a certain local property}})}$$في الواقع، ينهار W[1] إلى W[1, 2] ، وهي فئة من المسائل القابلة للاختزال السريع إلى دوائر منطقية من الشكل${\displaystyle \bigwedge _{i}(x_{i,1}\lor x_{i,2})}$أي أن عملية AND كبيرة على العديد من عمليات OR ذات المدخلات 2. ^{[ 8 ]}

تتضمن أمثلة المسائل الكاملة من النوع W[1] ما يلي: ^{[ 8 ]}

• مجموعة مستقلة
  • المدخلات: رسم بياني G
  • المعامل: عدد صحيح k
  • الناتج: ما إذا كانت G تحتوي على مجموعة مستقلة بحجم k
• زمرة
  • المدخلات: رسم بياني G
  • المعامل: عدد صحيح k
  • الناتج: ما إذا كانت المجموعة G تحتوي على زمرة بحجم k
• غير مانع ثنائي الأجزاء
  • المدخلات: رسم بياني ثنائي الأجزاء${\displaystyle (V_{1},V_{2},E)}$
  • المعامل: عدد صحيح k
  • الناتج: ما إذا كانت هناك مجموعة جزئية${\displaystyle S\subset V_{1}}$بحجم k ، بحيث يكون أي${\displaystyle v\in V_{2}}$لديه جار${\displaystyle u\not \in S}$. بعبارة أخرى،${\displaystyle S}$لم يحجب${\displaystyle V_{2}}$.
• الوزن - k 2 - الرضا
  • المدخلات: صيغة اقتران عادية من الشكل${\displaystyle \bigwedge _{i}(p_{i,1}\lor p_{i,2})}$، حيث تتراوح i عبر البنود .
  • المعامل: عدد صحيح k
  • الناتج: ما إذا كان هناك وزن k يفي بالغرض المطلوب في الصيغة.
• مشكلة آلة تورينج القصيرة.
  • المدخلات: آلة تورينج غير حتمية M ، سلسلة x ، عدد صحيح k .
  • الناتج: ما إذا كان هناك مسار حسابي واحد، يقبل من خلاله M قيمة x في k خطوة على الأكثر.

لاحظ أن مشكلة عدم الحظر البسيطة هي مسألة FPT. ^{[ 9 ]}

ملاحظة حول آلة تورينج غير الحتمية. يمكن تحديد الآلة بأي من الصيغ القياسية. عادةً ما يُنظر إلى آلة تورينج ذات الشريط الواحد، لكن مسألة آلة تورينج القصيرة تظل W[1] حتى لو سمحنا باستخدام f ( k ) شريطًا، وحتى f ( k ) من الأشرطة ذات الأبعاد f ( k )، ولكن حتى مع هذا التوسع، فإن القيد على حجم أبجدية الشريط f ( k ) هو FPT. والأهم من ذلك، نظرًا لأن الآلة M نفسها جزء من مدخلات المسألة، فإن حجم المدخلات n أكبر من عدد حالات M. وبهذه الطريقة، يمكن لآلة تورينج أن تأخذ واحدة من${\displaystyle n}$مسارات الحساب الممكنة لكل خطوة، الوصول إلى${\displaystyle n^{O(k)}}$عدد الخطوات الإجمالي خلال الزمن k . وبالتالي نرى أن W[1] لا يقع ضمن FPT بشكل واضح .

يمكن ترميز مشكلة المجموعة المستقلة على النحو التالي. بالنظر إلى كل رسم بياني${\displaystyle (V,E)}$، يتم ترميز مشكلة المجموعة المستقلة الخاصة بها بواسطة دائرة منطقية من نوع weft-1 التالية:$${\displaystyle \Phi _{\text{IS}}(V,E):=\bigwedge _{\{u,v\}\in E}(\neg x_{u}\lor \neg x_{v})}$$أين${\displaystyle E}$هي مجموعة الحواف في الرسم البياني. يحتوي الرسم البياني على مجموعة مستقلة بحجم k إذا وفقط إذا كان هناك مدخل وزنه k لدائرة منطقية، بحيث يكون الناتج 1.

يمكن ترميز مشكلة الزمرة على النحو التالي:$${\displaystyle \Phi _{\text{clique}}(V,E):=\bigwedge _{\{u,v\}\subset V,u\neq v,\{u,v\}\not \in E}(\neg x_{u}\lor \neg x_{v})}$$يتحقق من أنه لا يمكن اختيار أي زوج من الرؤوس التي لا تشكل حافة، لذلك فإن أي مجموعة مختارة من الرؤوس تُجبر على أن تكون زمرة.

يمكن تحويل مسألة آلة تورينج القصيرة إلى صيغة منطقية باستخدام نفس فكرة البرهان المستخدمة في نظرية كوك-ليفين ، والتي تُثبت أن مسألة SAT هي مسألة NP-كاملة عن طريق ترميز آثار حسابات آلة تورينج كصيغ منطقية. البرهان التالي مأخوذ من ^{[ 8 ] و[ 10 ]} . وبالتحديد، نُعرّف المتغيرات الافتراضية التالية:

• ${\displaystyle s_{t,i,j,a,b}}$في الوقت t ، تكون آلة تورينج في الحالة i ، وتنتقل إلى الحالة j ، فتقرأ a وتكتب b .
• ${\displaystyle y_{t,p,a,b}}$: في الوقت t ، يكون موضع الشريط p هو الرمز a ، وفي الوقت (t+1) يكون الرمز b .

من بين المؤشرات، يتراوح الوقت t وموضع الشريط p على 1:k ، ويتم تحديد نطاقات المؤشرات لحالة آلة تورينج i، j ، والانتقال m ، والرموز a، b من خلال وصف الآلة M، ولكن كلاهما محدود ضمن 1:n .

ثم الصيغة${\displaystyle \Phi _{{\text{STM}},k}(M,x)}$هي عبارة عن مجموعة من الجمل التي تفرض القيود التالية:

• لا تمنع قاعدة الانتقال غير الحتمية جميع انتقالات حالة آلة تورينج. تبدو هذه الانتقالات كالتالي:${\displaystyle s_{t,i,j,a,b}\to \neg s_{t+1,i',j',a',b'}}$، بعبارة أخرى،${\displaystyle \neg s_{t,i,j,a,b}\lor \neg s_{t+1,i',j',a',b'}}$هناك${\displaystyle O(kn^{4})}$مثل هذه البنود.
• لا يمكن لآلة تورينج أن تكون في موضعين في وقت واحد، ولا يمكنها إجراء انتقالين في وقت واحد.
• لا يمنع قانون الانتقال غير الحتمي أي انتقال لحالة خلية الشريط.
• لا يمكن أن تحتوي كل حالة من حالات خلية الشريط على رمزين في وقت واحد.
• في الوقت 0، لا تكون آلة تورينج خارج حالتها وموضعها الأوليين، ولا يتم مسح x من الشريط.
• آلة تورينج ليست في حالة عدم قبول عند الزمن k .

ثم يتم تحديد مسار الحساب عبر آلة تورينج بشكل كامل عن طريق ضبط k متغيرات من${\displaystyle s_{t,i,j,a,b}}$إلى صحيح للإشارة إلى انتقالات حالة آلة تورينج في كل وقت، وتعيين${\displaystyle k^{2}}$متغيرات${\displaystyle y_{t,p,a,b}}$يُشير الرقم "صحيح" إلى انتقال حالة الشريط في كل لحظة. هذا يُختزل مشكلة آلة تورينج القصيرة إلى مشكلة إيجاد وزن.${\displaystyle (k+k^{2})}$تعيين مُرضٍ لدائرة منطقية مضادة للرتابة من نوع weft-1، وdepth-2.

تكون مسائل W[2] بشكل بديهي على النحو التالي: خمن كائنًا بحجم k ، وقم بإجراء بعض المعالجة المحلية على الكائن، ثم قم بإجراء معالجة عالمية واحدة.

تتضمن أمثلة المسائل الكاملة من النوع W [2] ما يلي:

• تحديد ما إذا كان الرسم البياني المعطى يحتوي على مجموعة مهيمنة بحجم k.
• تحديد ما إذا كانت آلة تورينغ متعددة الأشرطة غير حتمية معينة تقبل البيانات خلال k خطوة ("مسألة قبول آلة تورينغ متعددة الأشرطة القصيرة"). ومن الأهمية بمكان أن التفرع مسموح له بالاعتماد على n (كما في متغير W[1])، وكذلك عدد الأشرطة. يسمح نموذج W [2]-كامل بديل بآلات تورينغ أحادية الشريط فقط، ولكن قد يعتمد حجم الأبجدية على n .

مسألة المجموعة المهيمنة لها صيغة${\displaystyle \Psi _{\text{dom}}(V,E)=\bigwedge _{u\in V}\bigvee _{v\in \operatorname {Neighbor} [u]}x_{v}}$.

من المعروف أن بعض المسائل تُصنف ضمن فئة W[i] -complete، على الرغم من أنها تتخذ شكلاً حسابياً عاماً، وعادةً ما تُدرس ضمن نظرية التعقيد البارامتري نفسها. تجريبياً، اعتباراً من عام 2013، تبين أن جميع المسائل البارامترية التي دُرست بشكل طبيعي تقريباً تُصنف ضمن فئات W[0] -complete، أو W[1] -complete، أو W[2] -complete. ويُستخدم عادةً ما يلي: ^{[ 4 ]}

• قابلية الإرضاء الموزونة والمُعَيَّرة : ^{[ 7 ] [ 4 ] : ​​نظرية 23.2.1} بالنظر إلى صيغة منطقية، مكتوبة كـ AND لـ OR لـ AND لـ ... لمتغيرات قد تكون منفية، مع${\displaystyle i+1}$هل يمكن تحقيق ذلك من خلال تعيين k متغيرًا بالضبط إلى 1، وذلك باستخدام طبقات من عمليات AND أو OR المتناوبة؟
  • مخطط البرهان: يمكن تطبيع أي دائرة W[i] في وقت fpt عن طريق تكرار قانون الارتباط وقانون التوزيع دي مورغان، مما يدل على أن هذه المشكلة W[i] كاملة.
• إذا كان i>0 زوجيًا، فإن
  • ${\displaystyle {\text{monotone-}}W[i]=W[i]}$.
  • إن مسألة الرضا المعياري أحادي الوزن i هي مسألة كاملة من النوع W[i] .
  • الرضا المعياري الرتيب الموزون (i+1) موجود في W[i] .
• إذا كان i>0 فرديًا، فإن
  • ${\displaystyle {\text{antimonotone-}}W[i]=W[i]}$
  • إن مسألة الرضا المعياري الموزون المضاد للتوتر i هي مسألة كاملة من النوع W[i] .
  • لو${\displaystyle i\geq 3}$، ثم يكون الرضا المعياري الموزون المضاد للرتابة (i+1) في W[i] .

تُعتبر هذه المشكلات "مصطنعة" في جوهرها، إذ لا تُدرس إلا في سياق التعقيد المُعَلم. وتشير الأدبيات إلى قلة المشكلات الطبيعية التي تُصنف ضمن فئة W[i] الكاملة.${\displaystyle i\geq 3}$:

• إن اكتشاف تبعيات التضمين في قواعد البيانات العلائقية هو W[3] -كامل.
• بعض المشكلات في نماذج سلسلة التوريد هي من النوع W[3] -complete أو W[4] -complete. ^{[ 11 ]}

يشبه التسلسل الهرمي W * التسلسل الهرمي W ، ولكنه يُحدد العمق كمعامل بدلاً من تثبيته. تُعرَّف فئة W*[t] بأنها فئة المسائل القابلة للاختزال إلى هذه المسألة باستخدام fpt: ^{[ 5 ]}

• المدخلات: دائرة منطقية من اللحمة بحد أقصى t ، والعمق بحد أقصى k ،
• المعامل: k
• الناتج: ما إذا كانت الدائرة المنطقية تحتوي على وزن k مُرضٍ.

وهي مرتبطة بـ W من خلال: ^{[ 4 ]}$${\displaystyle W^{*}[1]=W[1],\;W^{*}[2]=W[2],\;W[t]\subset W^{*}[t]\subset W[t+2],\quad \forall t\geq 1}$$يتم الحصول على التسلسل الهرمي AW بإضافة التناوب إلى التسلسل الهرمي W. تُعرَّف فئة AW[t] بأنها فئة المسائل القابلة للاختزال fpt إلى هذه المسألة: ^{[ 5 ] [ 6 ]}

• المدخلات: دائرة منطقية من خيوط اللحمة على الأكثر t ، وتقسيم لمدخلاتها إلى${\displaystyle I_{1}\cup I_{2}\cup \cdots \cup I_{r}}$
• المعلمة:${\displaystyle (r,k_{1},\dots ,k_{r})}$
• الناتج: ما إذا كانت الدائرة المنطقية قابلة للإرضاء في ظل أوزان متناوبة-${\displaystyle (k_{1},\dots ,k_{r})}$شروط.

الوزن المتناوب-${\displaystyle (k_{1},\dots ,k_{r})}$يُعرَّف على النحو التالي:

• توجد مجموعة جزئية${\displaystyle J_{1}\subset I_{1}}$من الحجم${\displaystyle k_{1}}$بحيث إذا قمنا بتعيين تلك المدخلات تحديدًا إلى "صحيح" والباقي إلى "خطأ"، فإن
• لأي مجموعة فرعية${\displaystyle J_{2}\subset I_{2}}$من الحجم${\displaystyle k_{2}}$بحيث إذا قمنا بتعيين تلك المدخلات تحديدًا إلى "صحيح" والباقي إلى "خطأ"، فإن
• ...
• تُخرج الدائرة المنطقية القيمة "صحيح".

يمكن تفسير هذا على أنه لعبة ثنائية اللاعبين، حيث يحاول اللاعب الأول جعل خرج الدائرة صحيحًا، بينما يحاول اللاعب الثاني جعله خاطئًا. يقوم اللاعب الأول بتحريك الدائرة عن طريق ضبط القيمة بدقة.${\displaystyle k_{1}}$مدخلات${\displaystyle I_{1}}$إلى صحيح والآخرين إلى خطأ، ثم يقوم اللاعب الثاني بتحريك يده${\displaystyle I_{2}}$إلخ. الدائرة الكهربائية تحت تأثير أوزان متناوبة.${\displaystyle (k_{1},\dots ,k_{r})}$الشروط إذا كان لدى اللاعب 1 استراتيجية فائزة.

اتضح أن التسلسل الهرمي ينهار:${\displaystyle AW[1]=AW[2]=\cdots }$وهكذا، فإن الأدبيات لا تكتب سوى رمز مشترك لهم:${\displaystyle AW[\ast ]:=AW[1]=AW[2]=\cdots }$.

• داوني، رود ج .؛ فيلوز، مايكل ر. (1999). التعقيد المُعَلم . سبرينغر. doi : 10.1007/978-1-4612-0515-9 . ISBN 978-0-387-94883-6.
• نيدرماير، رولف (2006). دعوة إلى خوارزميات المعلمات الثابتة . مطبعة جامعة أكسفورد. رقم ISBN 978-0-19-856607-6.كتاب تمهيدي.
• فلوم، يورغ ؛ غروهي، مارتن (2006). نظرية التعقيد البارامتري . سبرينغر. doi : 10.1007/3-540-29953-X . ISBN 978-3-540-29952-3.مقدمة محدثة للكتاب المدرسي الصادر عام 1999.
• داوني، رودني ج.؛ فيلوز، مايكل ر. (2013). أساسيات التعقيد المُعَلم . نصوص في علوم الحاسوب. لندن: سبرينغر لندن. doi : 10.1007/978-1-4471-5559-1 . ISBN 978-1-4471-5558-4.كتاب مدرسي غير تمهيدي كُتب لوصف التطورات اللاحقة للكتاب المدرسي الصادر عام 1999.
• سيجان، ماريك؛ فومين، فيدور الخامس؛ كواليك، لوكاش. لوكشتانوف، دانيال؛ ماركس، دانيال؛ بيليبتشوك، مارسين؛ بيليبتشوك، ميشال؛ سوراب، ساكيت (2015). خوارزميات ذات معلمات . سبرينغر. رقم ISBN 978-3-319-21274-6.