نظرية شيفر الثنائية

في نظرية التعقيد الحسابي ، وهي فرع من علوم الحاسوب ، تنص نظرية شيفر الثنائية ، التي أثبتها توماس جيروم شيفر ، على الشروط اللازمة والكافية التي بموجبها تُنتج مجموعة منتهية S من العلاقات على المجال البولياني مسائل ذات زمن متعدد الحدود أو مسائل كاملة من فئة NP، وذلك عند استخدام علاقات S لتقييد بعض المتغيرات الافتراضية . ^{[ 1 ]} تُسمى هذه النظرية نظرية ثنائية لأن تعقيد المسألة المُعرَّفة بواسطة S إما أن يكون ضمن فئة P أو يكون كاملًا من فئة NP، على عكس إحدى فئات التعقيد المتوسط ​​المعروفة (بافتراض أن P ≠ NP ) وفقًا لنظرية لادنر .

تشمل الحالات الخاصة لنظرية شيفر الثنائية اكتمال NP لمسألة SAT ( مسألة الإرضاء البولياني ) ونوعيها الشائعين: 1-in-3 SAT و 3SAT غير المتساوية (يُشار إليها غالبًا بـ NAE-3SAT). في الواقع، بالنسبة لهذين النوعين من SAT، تُظهر نظرية شيفر الثنائية أن نسختيهما الرتيبتين (حيث لا يُسمح بنفي المتغيرات) هما أيضًا من مسائل NP-الكاملة.

يُعرّف شيفر مسألة قرار يُطلق عليها اسم مسألة الإرضاء المعممة لـ S (يرمز لها بـ SAT( S ))، حيث${\displaystyle S=\{R_{1},\ldots ,R_{m}\}}$هي مجموعة محدودة من العلاقات على المجال الثنائي${\displaystyle \{0,1\}}$أحد أمثلة هذه المشكلة هو صيغة S ، أي اقتران القيود بالشكل التالي :${\displaystyle R_{j}(x_{i_{1}},\dots ,x_{i_{n}})}$أين${\displaystyle R_{j}\in S}$و${\displaystyle x_{i_{j}}}$هي متغيرات افتراضية. تكمن المشكلة في تحديد ما إذا كانت الصيغة المعطاة قابلة للتحقيق، بمعنى آخر، ما إذا كان من الممكن إسناد قيم للمتغيرات بحيث تحقق جميع القيود كما هو موضح في العلاقات من S.

يُحدد شيفر ست فئات من مجموعات العلاقات المنطقية التي يكون فيها SAT( S ) ضمن P، ويُثبت أن جميع مجموعات العلاقات الأخرى تُولّد مسألة NP-كاملة. تُعرّف مجموعة العلاقات S المنتهية على المجال المنطقي مسألة إرضاء قابلة للحساب في زمن متعدد الحدود إذا تحقق أي من الشروط التالية:

1. جميع العلاقات التي لا تكون خاطئة باستمرار تكون صحيحة عندما تكون جميع حججها صحيحة؛
2. جميع العلاقات التي لا تكون خاطئة باستمرار تكون صحيحة عندما تكون جميع حججها خاطئة؛
3. جميع العلاقات تعادل ربط جمل ثنائية ؛
4. جميع العلاقات تعادل ربط عبارات هورن ؛
5. جميع العلاقات تعادل اقتران جمل هورن المزدوجة؛
6. جميع العلاقات تعادل اقتران الصيغ الأفينية. ^{[ 2 ]}

وإلا فإن المشكلة SAT( S ) هي NP-كاملة.

يُقدّم هوبي تشين عرضًا حديثًا ومبسطًا لنظرية شيفر في ورقة بحثية توضيحية. ^{[ 3 ] [ 4 ]} وبعبارة حديثة، تُعتبر مسألة SAT( S ) مسألة إرضاء قيود على المجال البولياني . في هذا المجال، من الشائع الإشارة إلى مجموعة العلاقات بالرمز Γ، وإلى مسألة القرار المُعرّفة بواسطة Γ بالرمز CSP(Γ).

يستخدم هذا الفهم الحديث الجبر ، وبالتحديد الجبر الشامل . بالنسبة لنظرية شيفر الثنائية، فإن أهم مفهوم في الجبر الشامل هو مفهوم تعدد الأشكال. وهي عملية${\displaystyle f:D^{m}\to D}$هو تعدد أشكال العلاقة${\displaystyle R\subseteq D^{k}}$إذا، لأي اختيار من m صفوف${\displaystyle (t_{11},\dotsc ,t_{1k}),\dotsc ,(t_{m1},\dotsc ,t_{mk})}$من R ، يتضح أن المجموعة المرتبة التي تم الحصول عليها من هذه المجموعات المرتبة m بتطبيق f على مستوى الإحداثيات، أي${\displaystyle (f(t_{11},\dotsc ,t_{m1}),\dotsc ,f(t_{1k},\dotsc ,t_{mk}))}$، تنتمي إلى R. أي أن العملية f هي تعدد أشكال في R إذا كانت R مغلقة تحت f : تطبيق f على أي صفين في R ينتج صفًا آخر داخل R. يقال إن مجموعة العلاقات Γ تحتوي على تعدد أشكال f إذا كانت كل علاقة في Γ تحتوي على f كتعدد أشكال. يسمح هذا التعريف بالصياغة الجبرية لنظرية شيفر الثنائية.

لتكن Γ لغة قيود محدودة على المجال البولياني. تكون المسألة CSP(Γ) قابلة للحل في وقت متعدد الحدود إذا كانت Γ تحتوي على إحدى العمليات الست التالية كتعدد أشكال:

1. العملية الأحادية الثابتة 1؛
2. العملية الأحادية الثابتة 0؛
3. عملية AND الثنائية ∧؛
4. عملية OR الثنائية ∨؛
5. عملية الأغلبية الثلاثية${\displaystyle \operatorname {Majority} (x,y,z)=(x\wedge y)\vee (x\wedge z)\vee (y\wedge z);}$
6. عملية الأقلية الثلاثية${\displaystyle \operatorname {Minority} (x,y,z)=x\oplus y\oplus z.}$

وإلا فإن مشكلة CSP(Γ) هي NP-كاملة.

في هذه الصيغة، من السهل التحقق مما إذا كانت أي من شروط قابلية المعالجة صحيحة.

بالنظر إلى مجموعة Γ من العلاقات، هناك علاقة وثيقة بشكل مدهش بين تعدد أشكالها والتعقيد الحسابي لـ CSP(Γ).

تُسمى العلاقة R _علاقةً أوليةً قابلةً للتعريف الإيجابي ، أو باختصار قابلةً للتعريف الإيجابي ، من مجموعة العلاقات Γ إذا كان _{R(v1, ..., vk) ⇔ ∃x1, ..., xm.C} محققًا لبعض اقترانات _C من القيود من Γ _{والمعادلات} على المتغيرات { v1 , ... , _vk , x1 _, ... , xm } . على سبيل المثال، إذا كانت Γ تتكون من العلاقة الثلاثية _nae ( x , y , z ₎ التي تتحقق إذا لم تكن x و y و z متساوية ، وكانت R ( x , y , z ) هي x ∨ y ∨ z ، فيمكن تعريف R إيجابيًا من خلال R ( x , y , z ) ⇔ ∃a.nae ( 0, x , a ) ∧ nae ( y , z , ¬a ) . استُخدم هذا الاختزال لإثبات أن مسألة NAE-3SAT هي مسألة NP-كاملة. يُرمز إلى مجموعة جميع العلاقات القابلة للتعريف pp من Γ بالرمز ≪Γ≫. إذا كانت Γ' ⊆ ≪Γ≫ لبعض مجموعات القيود المحدودة Γ و Γ'، فإن CSP(Γ') تختزل إلى CSP(Γ). ^{[ 5 ]}

بالنظر إلى مجموعة علاقات Γ، يُرمز إلى مجموعة تعدد الأشكال في Γ بـ Pol (Γ). وعلى العكس، إذا كانت O مجموعة عمليات، فإن Inv ( O ) يُرمز إلى مجموعة العلاقات التي تُمثل جميع عمليات O تعدد أشكال فيها. تُشكل Pol و Inv معًا اتصال غالوا مضادًا . لأي مجموعة علاقات منتهية Γ على مجال منتهٍ، يتحقق الشرط ≪Γ≫ = Inv ( Pol (Γ))، أي أن مجموعة العلاقات القابلة للتعريف pp من Γ يُمكن اشتقاقها من تعدد أشكال Γ. ^{[ 6 ]} علاوة على ذلك، إذا كان Pol (Γ) ⊆ Pol (Γ') لمجموعتي علاقات منتهيتين Γ وΓ'، فإن Γ' ⊆ ≪Γ≫، ويُختزل CSP(Γ') إلى CSP(Γ). ونتيجة لذلك، تؤدي مجموعتا علاقات لهما نفس تعدد الأشكال إلى نفس التعقيد الحسابي. ^{[ 7 ]}

تم تحسين التحليل لاحقًا: يمكن حل CSP(Γ) إما في co-NLOGTIME، أو L-complete ، أو NL-complete ، أو ⊕L-complete، أو P-complete ، أو NP-complete، وبمعرفة Γ، يمكن تحديد أي من هذه الحالات صحيح في وقت متعدد الحدود. ^{[ 8 ]}

كما تم تعميم نظرية شيفر الثنائية لاستخدام منطق القضايا للرسوم البيانية بدلاً من المنطق البولياني. ^{[ 9 ]}

إذا كانت المشكلة هي حساب عدد الحلول، والذي يُرمز إليه بـ #CSP(Γ)، فهناك نتيجة مماثلة للمجال الثنائي من قِبل كريجنو وهيرمان. ^{[ 10 ]} تحديدًا، تُعرّف مجموعة منتهية من العلاقات S على المجال البولياني مسألة إرضاء قابلة للحساب في زمن متعدد الحدود إذا كانت كل علاقة في S مكافئة لربط صيغ خطية. ^{[ 2 ]}

بالنسبة للمجالات الأكبر، قدم بولاتوف ودالماو شرطًا ضروريًا لتحقيق إمكانية الإرضاء في زمن متعدد الحدود. ^{[ 11 ]} ليكن Γ لغة قيود محدودة على المجال البولياني. إذا كانت المسألة #CSP(Γ) قابلة للحساب في زمن متعدد الحدود، فإن Γ تحتوي على عملية مالتسيف كتعدد أشكال. وإلا، فإن المسألة #CSP(Γ) تكون كاملة من النوع #P . عملية مالتسيف m هي عملية ثلاثية تحقق الشرط التالي:${\displaystyle m(x,y,y)=m(y,y,x)=x.}$من أمثلة عمليات مالتسيف عملية الأقلية الواردة في الصيغة الجبرية الحديثة لنظرية شيفر الثنائية المذكورة أعلاه. بالتالي، عندما تكون عملية الأقلية متعددة الأشكال لـ Γ، فإنه لا يمكن فقط تحديد CSP(Γ) في وقت متعدد الحدود، بل يمكن أيضًا حساب #CSP(Γ) في وقت متعدد الحدود. يوجد إجمالاً 4 عمليات مالتسيف على المتغيرات المنطقية، والتي تُحدد بقيم${\displaystyle m(T,F,T)}$و${\displaystyle m(F,T,F)}$. مثال على نموذج أقل تناظرًا هو ما يلي${\displaystyle m(x,y,z)=(x\wedge z)\vee (\neg y\wedge (x\vee z))}$أما في مجالات أخرى، مثل المجموعات ، فتشمل أمثلة عمليات مالتسيف ما يلي:${\displaystyle x-y+z}$و${\displaystyle xy^{-1}z.}$ بالنسبة للمجالات الأكبر، حتى بالنسبة لمجال بحجم ثلاثة، فإن وجود تعدد أشكال مالتسيف لـ Γ ليس شرطًا كافيًا لإمكانية حل #CSP(Γ). ومع ذلك، فإن غياب تعدد أشكال مالتسيف لـ Γ يستلزم صعوبة #P لـ #CSP(Γ).

• نظريات تصنيف الحد الأقصى/الأدنى لمسألة إرضاء القيود/الواحدات ، وهي مجموعة مماثلة من القيود لمسائل التحسين.