فريدة من نوعها 3SAT إلى فريدة من نوعها 1 في 3SAT

Question

لنفترض أن لدي صيغة CNF مع بنود الحجم 2 و 3. لديها مهمة مرضية فريدة من نوعها.

تم تصنيعها من دائرة الضرب الثنائية حيث تضاعل أرقام اثنين من الأعداد الأولية A و B بحيث يكون A * B= S E هو رقم Semiprime. أضفت الظروف التي!= 1، b!= 1 و <= b، ثم أضفت قيمة S إلى الصيغة تأكد من أن المهمة فريدة من نوعها. الطريقة الوحيدة لإرضاء الصيغة هي وضع قيم الأعداد الأولية A و B بالترتيب الصحيح في أجزاء الإدخال.

في 1 في 3SAT، نحن نفرض ذلك بالضبط 1 الحرفي يجب أن يكون صحيحا في كل ثلاث سنوات واثنين آخرين خطأ. إذا كان الأمر حرفيا بالضبط 2 صحيح، فيمكننا أن نقفل جميع المفاتيحين في البند للحصول على بند ما يعادل 1 في 3SAT (بمعنى آخر 2-in-3sat هو نفس المشكلة).

الملاحظة الأساسية: في حين أن المنتظم أو البند يلغي 1 إمكانية من 8، فإن جملة 1 في 3 تزيل 5 إمكانيات من 8.

3sat يمكن تخفيضها إلى 1 في 3 جلست، بحيث إذا كانت صيغة 3SAT راضية ثم هي الصيغة المخفضة.

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

يمكن تخفيض 3SAT فريدة من نوعها إلى 1 في 3SAT ...

1. دون معرفة المهمة الصحيحة؟
2. إذا لم يكن الأمر كذلك، في حين معرفة المهمة الصحيحة؟

Answer 1

نعم، يمكن تحويل الصيغة 3-Sat $ \ Phi $ في صيغة SAT 1 في 3 $ \ Phi '$ مع الحفاظ على عدد المهام المرضية. لتجنب تناول الغموض وسأستعبه " $ \ VEE $ " بين الحرفيين من جملة 3 جاتين، وفواصل بين الحرفيين من بند جلاس 1 في 3. < / ص>

---

اسمحوا لي أن أظهر لي بشكل مسبق، منح حرفين $ $ و $ B $ ، يمكننا محاكاة نوع جديد من البند $ (x= a \ wedge b) $ الذي يفرض قيمة متغير جديد $ x $ ليكون $ a \ wedge b $ باستخدام قيود السبت 1 في 3 فقط، دون تقديم أي حل جديد.

النظر في الأمعاء: $$ (\ overline {b}، c، x) \ wedge (أ، ج، د) \ إسفين (\ overline {a}، e، x) \ wedge (ب، ه، و)

إذا كان $ a=top $ ، و $ b=top $ ، ثم 2nd والجلوس الرابعة تضمن أن $ c= d= d= f=bot $ . ثم تضمن البنود الأولى والثالثة بعد ذلك $ x=top $ .

إذا $ a=top $ ، و $ b=bot $ ، ثم 2nd يضمن جملة أن $ c= d=bot $ . ثم يضمن البند الأول أن $ x=bot $ . يضمن البند الثالث أن $ e=Top $ ، والفقلة الرابعة يعني $ f=bot $ .

الحالة $ a=bot $ ، و $ B=TOP $ متماثل.

إذا $ a=bot $ و $ b=bot $ ، ثم 1st و تعني البنود الثالثة $ c= e= x=bot $ . تضمن البنود الثانية والرابع $ d= f=top $ .

---

أنا الآن جاهز لتحويل صيغة $ \ Phi $ من 3SAT إلى صيغة $ \ phi '$ < / تمتد> من 1 في 3 جلست. فكر الآن بند $ (a \ vee b \ vee c) $ من $ \ Phi $ . يمكن تحويل هذا إلى كل من بنود السبت المكافئة التالية:

• أضف متغيرا جديدا $ x $ صحيح IFF $ A $ هو خطأ و $ B $ صحيح. يتم ترميز هذا عن طريق البند $ (x=overline {a} \ wedge b) $ .

• أضف متغيرا جديدا $ y $ صحيح IFF $ $ $ هو خطأ ، $ B $ هو FALSE، و $ C $ صحيح. سنحتاج إلى متغير إضافي $ Z $ . البند $ (z=overline {a} \ Wedge \ overline {b}) $ يضمن أن $ z $ < / span> صحيح إذا وفقط إذا كانت $ $ false و $ B $ هي false. بعد ذلك، يمكن تطبيق قيمة $ y $ بواسطة البند $ (y= z \ edge c) $ .

• إذا كان $ (a \ vee b \ vee c) $ صحيح ثم واحد من $ $ ، $ B $ ، أو $ C $ $ $ ، $ x $ ، و $ y $ صحيح. على التحدث، إذا $ (a \ vee b \ vee c) $ هو false، ثم في كل من $ $ ، $ x $ ، و $ y $ هي خطأ. هذا يدل على أن $ (a \ vee b \ vee c) $ راضي إذا وفقط إذا كان $ (a، x، Y $ ) راضي.

لقد شيدنا بعد ذلك ما يعادلها 1 -3 في 3 جلسة الصيغة $ \ Phi '$ يستخدم مجموعة من متغيرات الصيغة 3 الساتانية الأصلية $ \ Phi $ . مهمة الحقيقة بمتغيرات $ \ Phi '$ يرضي $ \ phi' $ إذا وفقط إذا المهمة مقيدة بمتغيرات $ \ Phi $ يرضي $ \ phi $ . لذلك، إذا تم تقديم أي حل جديد إلى $ \ Phi '$ ، يجب أن يكون بسبب المتغيرات المضافة حديثا $ x $

n>، $ y $ ، و $ z $ (مجموعة واحدة لكل جملة).ومع ذلك، يتم تحديد قيم هذه المتغيرات بالكامل من خلال قيم المتغيرات من $ \ Phi $ .

Answer 2

تم وصف هذا التخفيض في الملحق ب من Régis Barbanchon، على الرسم البياني الفريد 3-قابلية القابلية للتلوين والتخفيضات البارزين في الطائرة .يعزه Barbanchon إلى العمل السابق ([9] في المراجع).في أي مكان آخر، رأيت إسناادا للورق الشهير الذي يحتفل به حيث يثبت نظريته الشهيرة لثلاثي، من بين آخر تخفيض من 3SAT إلى 1 في 3SAT، وهو ما يفترض البابلية (لم أكن راجع).