معادلة كروم الصيغ لين العريكة?

Question

نفترض أن لدي اثنين كروم الصيغ $\psi_1, \psi_2$.كروم الصيغ اقتراحي الصيغ في CNF أن يكون 2 حرفية في كل بند.كل الحرفي يمكن أن يبطل أو unnegated.وبعبارة أخرى ، $\psi_1,\psi_2$ 2-CNF الصيغ.على سبيل المثال:

$(x_1 \مخروطى eg x_2) \الأرض ( eg x_2 \مخروطى x_3 ) \الأرض (x_3 \مخروطى x_4)$

أريد أن تقرر ما إذا كان $\psi_1,\psi_2$ منطقيا ما يعادلها ، أي ، $\psi_1 \leftrightarrow \psi_2$.مكافئ ، أريد أن اختبار ما إذا كان $F=(\psi_1 \مخروطى \سالب\psi_2)\إسفين (\سالب \psi_1 \مخروطى \psi_2)$ صحيح بالنسبة لجميع المهام $x_1,\النقاط ، x_n$.

هل هذه المشكلة لين العريكة?

Answer 1

نعم، يمكن التحقق من التكافؤ في وقت متعدد الحدود (في الواقع، في الوقت الربع الثالث).

سأصف كيفية اختبار ما إذا كان $ \ psi_1 \ lor \ neg \ psi_2 $ صحيح بالنسبة لجميع المهام. يمكنك أن تفعل الشيء نفسه بالنسبة ل $ \ neg \ psi_1 \ lor \ psi_2 $ ، واستخدم هذا لاختبار ما إذا كان $ f $ هو أمراضا سعيدة، أي ما إذا كان $ \ psi_1، \ psi_2 $ معادل منطقيا.

سأفعل ذلك عن طريق التحقق من ذلك سواء $ \ psi_1 \ lor \ neg \ psi_2 $ هو false for أي مهمة، أو بمعنى آخر، سواء $ \ neg (\ psi_1 \ lor \ neg \ psi_2) $ راضي. لاحظ أن

$$ \ neg (\ psi_1 \ lor \ neg \ psi_2)= neg \ psi_1 \ land \ psi_2، $

لذلك يكفي لاختبار الرضا عن $ \ neg \ psi_1 \ land \ psi_2 $ حيث $ \ psi_1، \ PSI_2 $ هي صيغ KROM (2-CNF).

افترض أن $ \ psi_1= c_1 \ land \ cdots \ land c_k $ حيث $ c_i $ هو $ I $ جملة th in $ \ psi_1 $ . ثم

$$ \ neg \ psi_1= (\ neg c_1) \ lor \ cdots \ lor (\ neg c_k). $

لذلك

$ \ ادبت {align *} \ neg \ psi_1 \ land \ psi_2 &= ((neg c_1) \ lor \ cdots \ lor (\ neg c_k)) \ land \ psi_2 \\ &= (\ neg c_1 \ land \ psi_2) \ lor \ cdots \ lor (\ neg c_k \ land \ psi_2). \ END {محاذاة *} $

الآن، $ \ neg \ psi_1 \ land \ psi_2 $ راضي IFF $ \ neg c_i \ land \ psi_2 $ هو راضي عن بعض $ i $ $ . لذلك، يمكننا تكرار أكثر من $ I $ وراض الاختبار من كل $ \ neg c_i \ land \ psi_2 $ ؛ إذا كان أي منهم راضيه، ثم $ \ neg \ psi_1 \ lor \ psi_2 $ راضي و $ f $ ليس علميا و $ \ psi_1، \ psi_2 $ لا يعادلها منطقيا.

كيفية اختبار الرضا عن $ \ neg c_i \ land \ psi_2 $ ؟ حسنا، $ c_i $ لديه النموذج $ (\ ell_1 \ lor \ ell_2) $ أين $ \ ell_1، \ ell_2 $ هي حرفين، لذلك $ \ neg c_i \ land \ psi_2 $ لديه النموذج < Span Class="حاوية الرياضيات"> $ \ neg \ ell_1 \ land \ neg \ ell_2 \ land \ psi_2 $ . هذا هو أيضا صيغة KROM (2-CNF)، حتى تتمكن من اختبار تلبيةها باستخدام خوارزمية وقت متعدد الحدود القياسية. يمكنك القيام بعدد خطي من هذه الاختبارات، وبالتالي فإن وقت التشغيل الإجمالي هو متعدد الحدود. في الواقع، من الدرجة الثانية، حيث يمكن إجراء إرضاء الاختبار في الوقت الخطي.

Answer 2

أذكر 2-جلس الحل الذي يستخدم مكونات مرتبطة بقوة:ونحن بناء على الرسم البياني مع القمم $x_1,\ldots,x_n, \lnot x_1, \ldots, \lnot x_n$, و نستبدل كل بند $x_i \لور x_j$ مع حواف $\lnot x_i \إلى x_j$ و $\lnot x_j \إلى x_i$.مثال من هنا:

لتلبية الصيغة, من الضروري و الكافي لتعيين القمم بحيث لا توجد تناقضات في الرسم البياني (لا حافة $true \false$).يمكننا استخدام هذه الرسوم البيانية من أجل التحقق من التكافؤ.

1. نحن نبني هذه الرسوم البيانية $G_1$ و $G_2$ لكل الصيغ $F_1$ و $F_2$.
2. إذا كان هناك دورة $x_i \leadsto \lnot x_i \leadsto x_i$ في الرسم البياني ، ثم تركيبته لا يوجد لديه حلول.علينا التحقق من أن كلا من الصيغ قابلة للحل/غير قابلة للحل.
3. إذا كان هناك مسار شكل $x_i \leadsto \lnot x_i$ (وبالمثل حالة $\lnot x_i \leadsto x_i$) ، ونحن نعلم أن لإرضاء الصيغة يجب أن نختار $x_i$ أن تكون كاذبة (وإلا لدينا تناقض).علينا أن نتذكر هذا الاختيار.باستخدام الرسم البياني يمكننا تعيين قيم على كل القمم يمكن الوصول إليها من $\lnot x_i$ (يجب أن يكون صحيحا).مرة أخرى, تحقق من أن كل الصيغ بالضبط نفس القرارات في نهاية المطاف.
4. إزالة جميع الحواف/من المعروف القمم من الرسوم البيانية.
5. الآن ، $F_1$ و $F_2$ تعادل $\المنتدى$ تبقى الرسوم البيانية تعادل في المعنى:أي $v_1 ، v_2$ المسار $v_1 \leadsto v_2$ موجود في $G_1$ المنتدى كان موجودا في $G_2$.يمكن التحقق من ذلك في معظم $O(|V|\cdot|ه|)$ الوقت (فقط تشغيل DFS من كل قمة والتحقق من أنه قد زار نفس القمم لكل الرسوم البيانية).ربما يمكن القيام به بشكل أسرع.

دليل:

$\Leftarrow$:واضح لأن بعد متعدية إغلاق الرسوم البيانية سوف يكون لها نفس الآثار في كل من الصيغ.

$ ightarrow$:من خلال التناقض.Wlog افترضنا أن هناك مسار $v_1 \leadsto v_2$ في $G_1$ التي لا وجود لها في $G_2$.فهذا يعني أن مهمة $v_1 := true$, $v_2 := false$ هو ممكن في $F_2$ (حيث لا يوجد مسار $v_1 \leadsto v_2$) ولكن هو قابل للتطبيق في $F_1$.

وهي المهمة التالية يرضي $F_2$:

• $true$ كل القمم التي يسهل الوصول إليها من $v_1$.
• $false$ من كل القمم التي يمكن أن تصل إلى $v_2$.
• إزالة كل معروف القمم (المذكورة أعلاه ويكمل بهم) من الرسم البياني.كل ما تبقى القمم إنشاء اتصال المكونات.ونحن اللون توصيل المكونات في $true$, و توصيل مكونات الموافق يكمل في $false$ (انظر الملاحظة أدناه).

هذه المهمة قد لا تناقض ، حيث يمكن أن يكون هناك أي حافة $u \إلى الخامس$ من شكل $true \false$:

• إذا $u$ ينتمي إلى المكون الذي كان كامل الملونة $true$, ثم هذه $v$ يجب أن يكون صحيحا أيضا.
• وإلا فإن ذلك يعني أن $u$ يمكن الوصول من $v_1$, وبالتالي $v$ هو أيضا يمكن الوصول إليها من $v_1$ و يجب أن يكون صحيحا. $\blacksquare$

ملاحظة تقنية:لكل متغير $x_i$ هناك اثنين من القمم: $v_i$ و $\lnot v_i$ و قد يتساءل المرء ما إذا كان ذلك سوف يؤدي إلى بعض المشاكل مع المهام.الجواب هو أنه بعد الخطوة 4) ، $v_i$ و $\lnot v_i$ سوف تقع في اثنين من مختلف مكونات (وعلاوة على ذلك ، فهي متماثل: $u \إلى الخامس$ في عنصر واحد يعني $\lnot u \إلى \lnot v$ في واحد آخر).ولذلك مهما كان قرار نتخذه على $u$ في عنصر واحد ، ونحن يمكن أن تجعل الآخر قرار $\lnot u$ في واحد آخر.