التسلسل الهرمي المنطقي

التسلسل الهرمي البولياني هو تسلسل هرمي للتراكيب البوليانية ( التقاطع ، والاتحاد ، والمتممة ) لمجموعات NP . وبصورة مكافئة، يمكن وصف التسلسل الهرمي البولياني بأنه فئة الدوائر البوليانية على مسندات NP . ويؤدي انهيار التسلسل الهرمي البولياني إلى انهيار التسلسل الهرمي متعدد الحدود . ^{[ 1 ]}

يُعرَّف BH على النحو التالي: ^{[ 2 ]}

• BH ₁ هو NP .
• BH _{2 k} هي فئة اللغات التي تمثل تقاطع لغة في BH _{2 k -1} ولغة في coNP .
• BH _{2 k +1} هي فئة اللغات التي تمثل اتحاد لغة في BH _{2 k} ولغة في NP .
• BH هو اتحاد جميع فئات BH _i .

• DP (زمن متعدد الحدود التفاضلي) هو BH ₂ . ^{[ 3 ]}

يُتيح تعريف الاقتران والفصل بين الأصناف على النحو التالي تعريفات أكثر إيجازًا. يتضمن اقتران صنفين اللغات التي تمثل تقاطع لغة من الصنف الأول ولغة من الصنف الثاني. ويُعرَّف الفصل بطريقة مماثلة، مع استبدال التقاطع بالاتحاد.

• C ∧ D = { A ∩ B | A ∈ C  B ∈ D }
• C ∨ D = { A ∪ B | A ∈ C  B ∈ D }

وفقًا لهذا التعريف، فإن DP = NP ∧ coNP. ويمكن تعريف الفئات الأخرى للتسلسل الهرمي المنطقي على النحو التالي.

${\displaystyle {\mathsf {BH}}_{2k}={\mathsf {coNP}}\wedge {\mathsf {BH}}_{2k-1}}$

${\displaystyle {\mathsf {BH}}_{2k+1}={\mathsf {NP}}\vee {\mathsf {BH}}_{2k}}$

يمكن استخدام المعادلات التالية كتعريفات بديلة لفئات التسلسل الهرمي المنطقي: ^{[ 4 ]}

${\displaystyle {\mathsf {BH}}_{2k}=\bigvee _{i=1}^{k}{\mathsf {DP}}}$

${\displaystyle {\mathsf {BH}}_{2k+1}={\mathsf {NP}}\vee \bigvee _{i=1}^{k}{\mathsf {DP}}}$

أو بدلاً من ذلك، ^{[ 5 ]} لكل k ≥ 3:

${\displaystyle {\mathsf {BH}}_{k}={\mathsf {DP}}\vee {\mathsf {BH}}_{k-2}}$

يمكن إثبات صعوبة فئات التسلسل الهرمي البولياني من خلال إظهار اختزال من عدد من حالات مسألة NP-كاملة عشوائية A. على وجه الخصوص، بالنظر إلى سلسلة { x ₁ , ... x _m } من حالات A بحيث يكون x _i ∈ A يستلزم x _{i -1} ∈ A، يلزم اختزال ينتج حالة y بحيث يكون y ∈ B إذا وفقط إذا كان عدد x _i ∈ A فرديًا أو زوجيًا: ^{[ 4 ]}

• يتم إثبات صلابة BH _{2 k} إذا${\displaystyle m=2k}$وعدد xᵢ _∈ A فردي​
• يتم إثبات صلابة BH _{2 k +1} إذا${\displaystyle m=2k+1}$وعدد xᵢ _∈ A زوجي​

تنجح هذه الاختزالات مع كل قيمة ثابتة لـ k . إذا وُجدت هذه الاختزالات لأي قيمة لـ k ، فإن المشكلة تصبح صعبة بالنسبة لـ P ^{NP[ O (log n )]} .