XOR-SAT

الموسوعة الحرة

في مجال التعقيد الحسابي ، تُعرف مسألة XOR-SAT (أو XORSAT ) بأنها فئة من مسائل الإرضاء المنطقي حيث يحتوي كل بند على عامل XOR (أي " أو الحصرية "، ويُكتب "⊕") بدلاً من عامل OR (العادي). [ أ ] تنتمي مسألة XOR-SAT إلى فئة P ، [ 1 ] حيث يمكن اعتبار صيغة XOR-SAT نظامًا من المعادلات الخطية بتردد 2، ويمكن حلها في زمن مكعب باستخدام طريقة الحذف الغاوسي . [ 2 ] تستند هذه الصياغة الجديدة إلى العلاقة بين الجبر البولياني والحلقات البوليانية ، وحقيقة أن العمليات الحسابية بتردد 2 تُشكل الحقل المنتهي GF(2) .

أمثلة

إليك مثال على XOR-SAT غير قابل للإرضاء لمتغيرين و3 بنود: [ b ]

( أ ⊕ ب ) ∧ ( أ ) ∧ ( ب )

إليك مثال قابل للإرضاء لـ XOR-SAT لمتغيرين وشرط واحد يقبل حلين:

( أ ⊕ ب )

وهنا مثال فريد لـ XOR-SAT، أي مثال قابل للإرضاء لـ XOR-SAT لمتغيرين وشرطين يقبل حلاً واحداً فقط:

( أ ⊕ ب ) ∧ ( أ )

مقارنة مع اختلافات اختبار SAT

قد تكون الصيغة المكونة من جزأين غير مستوفاة (أحمر)، أو مستوفاة من 3 (أخضر)، أو مستوفاة من 3 من نوع xor (أزرق)، أو/و مستوفاة من 1 من 3 (أصفر)، وذلك اعتمادًا على عدد القيم الحرفية TRUE في الجزء الأول (أفقي) والجزء الثاني (رأسي).

بما أن a ⊕ b ⊕ c تُقيّم إلى TRUE إذا وفقط إذا كان عنصر واحد أو ثلاثة عناصر من المجموعة { a , b , c } صحيحة، فإن كل حل لمسألة 1-in-3-SAT لصيغة CNF معينة هو أيضًا حل لمسألة XOR-3-SAT، وبالتالي فإن كل حل لمسألة XOR-3-SAT هو حل لمسألة 3-SAT ؛ انظر الشكل. ونتيجة لذلك، لكل صيغة CNF، من الممكن حل مسألة XOR-3-SAT المحددة بهذه الصيغة، وبناءً على النتيجة، يمكن استنتاج إما أن مسألة 3-SAT قابلة للحل أو أن مسألة 1-in-3-SAT غير قابلة للحل.

بشرط ألا تكون فئات التعقيد P و NP متساوية ، فإن قابلية الإرضاء 2، أو هورن، أو XOR ليست كاملة NP، على عكس SAT.

حل مثال XOR-SAT باستخدام طريقة الحذف الغاوسي

الصيغة المعطاة ( الفقرة الحمراء اختيارية):

( x 1 ⊕ ¬ x 2 ⊕ x 4 ) ∧ ( x 2 ⊕ x 4 ⊕ ¬ x 3 ) ∧ ( x 1 ⊕ x 2 ⊕ ¬ x 3 ) ∧ ( x 1 ⊕ x 2 ⊕ x 4 )

نظام المعادلات

"1" تعني صحيح، و"0" تعني خطأ. كل عبارة تؤدي إلى معادلة واحدة.

x 1⊕¬x 2⊕x 4= 1
x 2⊕x 4⊕¬3x​= 1
x 1⊕x 2⊕¬3x​= 1
x 1⊕x 2⊕x 4≃ 1

نظام المعادلات المعياري

باستخدام خصائص الحلقات المنطقية (¬ x =1⊕ x , x ⊕ x =0)

x 1⊕x 2⊕x 4= 0
x 2⊕x 4⊕3x​= 0
x 1⊕x 2⊕3x​= 0
x 1⊕x 2⊕x 4≃ 1

إذا وُجدت المعادلة الحمراء ، فإنها تتعارض مع المعادلة السوداء الأولى، وبالتالي يصبح النظام غير قابل للحل. لذلك، تُستخدم خوارزمية جاوس فقط للمعادلات السوداء.

مصفوفة المعاملات المرتبطة

x 1x 23x​x 4خط
 
11010أ
01110ب
11100ج

التحول إلى شكل متدرج

x 1x 23x​x 4عملية
 
11010أ
01110ب
00110D = C ⊕ A

التحويل إلى الشكل القطري

x 1x 23x​x 4عملية
 
10010F = A ⊕ B ⊕ D
01000E = B ⊕ D
00110د

تعيينات عشوائية متغيرة

بالنسبة لجميع المتغيرات الموجودة على يمين الشكل القطري (إن وجدت)، نقوم بتعيين أي قيمة عشوائية.

x 1x 23x​x 4 = صحيحنتيجة القيم المُخصصة
 
x 1حقيقيخطأ شنيعx 1 = صحيح
x 2خطأ شنيعx 2 = خطأ
3x​حقيقيخطأ شنيعx 3 = صحيح

حل

إذا وُجد الشرط الأحمر ، فإن الحالة غير قابلة للحل. وإلا:

  • x 1 = 1 = صحيح
  • x 2 = 0 = خطأ
  • x 3 = 1 = صحيح
  • x 4 = 1 = صحيح

ونتيجة لذلك، فإن R ( x 1 , ¬ x 2 , x 4 ) ∧ R ( x 2 , x 4 , ¬ x 3 ) ∧ R ( x 1 , x 2 , ¬ x 3 ) ∧ R (¬ x 1 , x 2 , x 4 ) ليست قابلة للإرضاء من النوع 1 في 3، بينما ( x 1 ∨ ¬ x 2 ∨ x 4 ) ∧ ( x 2 ∨ x 4 ∨ ¬ x 3 ) ∧ ( x 1 ∨ x 2 ∨ ¬ x 3 ) ∧ ( x 1 ∨ x 2 ∨ x 4 ) قابلة للإرضاء من النوع 3 مع x 1 = x 2 = x 3 = x 4 =TRUE.

ملحوظات

  1. ↑ رسميًا، تُستخدمالصيغ المنطقية العامة للاقتران مع دالة منطقية ثلاثية R ، والتي تكون صحيحة فقط إذا كان واحد أو ثلاثة من وسائطها صحيحًا. يمكن تحويل عبارة إدخال تحتوي على أكثر من 3 متغيرات حرفية إلى اقتران متساوي الإرضاء لعبارات تحتوي على 3 متغيرات حرفية، على غرار ما سبق ؛ أي يمكن اختزال XOR-SAT إلى XOR-3-SAT.
  2. ↑ يمكن إثبات جميع الأمثلة بواسطة جدول الحقيقة.

مراجع

  1. ↑ شيفر، توماس ج. (1978). "تعقيد مسائل الإرضاء". وقائع الندوة السنوية العاشرة لجمعية آلات الحوسبة حول نظرية الحوسبة - STOC '78 . الصفحات 216-226 . doi : 10.1145/800133.804350 . 
  2. ↑ مور، كريستوفر ؛ ميرتنز، ستيفان (2011)، طبيعة الحوسبة ، مطبعة جامعة أكسفورد، ص 366، ISBN  9780199233212.