تخفيض من VC إلى {A، K |A هو 3DNF (شكل طبيعي محرم) وهناك مهمة مرضية بالضبط كلاؤات K في}

Question

لدي السؤال التالي:

\ ابدأ {align} L_2={A، K \ \ MID \ Text {A هو 3DNF (نموذج طبيعي محرز) و} \\ \ text {هناك مهمة مهمة $ Z $ يرضية بالضبط $ k $ c $ coures in} a \} \ End {محاذاة}

أعرف أن $ l_2 \ in $ NPC.

أظهر أن $ l_2 \ in $ np سهل نسبيا، سأتخطي هذا الجزء.

أحاول أن أظهر أن $ l_2 \ in $ NPC باستخدام تخفيض من VC $ \ Leq_P L_2 $ (VC هو Certex Cover الذي نعرفه في NPC)

حددت الوظيفة التالية $ f $ :

$$ f (g، k)= (a، k) $

فكرت في شيء من هذا القبيل لكل عقدة $ I $ في $ G $ ستحدد حرفية $ x_i $ ، وجعلها بتنسيق 3DNF، $ a=bigvee (x_i \ wedge x_i \ wedge x_i) $ حيث $ 1 \ leq i \ leq n $ حيث $ n $ هو عدد العقد في $ G $ . يمكننا تحديد ذلك التالية $ z $ مثل $ Z $ sheakies بالضبط $ K $ ، فقط أعط $ '1 دولار أمريكي حرفي $ x_i $ بحيث تكون العقدة $ I $ موجودة في VC، و $ '0' $ غير ذلك، لذلك هذه $ Z $ موجودة.

من السهل جدا أن نرى أن $ (g، k) \ in $ vc $ \ implies (a، k) \ في L_2 $ منذ أن أظهرنا صريحا مثل $ z $ التي تخدع بالضبط $ K $

لكنني لست متأكدا من الجانب الآخر يحمل $ (g، k) \ not \ в $ vc $ \ يعني (A، K) \ Not \ in L_2 $ لقد أعطينا رسم بياني لا يحتوي على VC بحجم $ K $ ولكن أعتقد أنه بسبب إلى المبنى الخاص بي ( $ a=bigvee (x_i \ wedge x_i \ wedge x_i) $ ) يمكننا أن نجد $ Z $ الصخور بالضبط $ K $ claus (في الواقع يمكننا العثور على $ z $ $ x $ chaus حيث $ 1 \ leq x \ leq n $ حيث $ N $ هو عدد العقد في $ G $ .

لذلك تخفيض بلدي لا يحمل؟

Answer 1

سبب لماذا تواجه مشاكل لأن الحل الخاص بك لا يعمل. على وجه الخصوص، المشكلة هي أن الصيغة الخاصة بك لا تلتقط بيان مشكلة VC. على وجه التحديد، فإن الصيغة التي تبنيها دائما لها مهام تلبية $ K $ فقط إعداد $ K $ المتغيرات إلى True والباقي كاذب.

لذلك دع $ g= (v، e) $ يكون الرسم البياني و $ x \ subseteq v $ كن VC في $ G $ . ثم لأي حافة $ vw \ in e $ يجب أن يكون لدينا $ v \ في x $ أو $ w \ в x $ ، مما يمنحنا 3 إمكانيات حصرية متبادلة (من خلال إعادة كتابة $ v \ vee w $ in DNF):

• $ v \ in x $ ولكن $ w \ notin x $ ،
• $ v \ notin x $ ولكن $ w \ in x $
• $ v \ in x $ و $ w \ in x $

وبالتالي الحافة $ vw $ مغطاة $ x $ إذا وفقط إذا كانت الصيغة < span class="حاوية الرياضيات"> $ \ psi (vw)= (v \ wedge w) \ vee (\ neg v \ wedge w) \ vee (v \ wedge \ neg w) $ لديه بالضبط واحد بند راض (بموجب المهمة المقابلة $ x $ ).

بناء هذه الصيغة لكل حافة وأخذها انتقارفا، نحصل على صيغة DNF $$ \ psi ^ \ text {vc} (g)=bigvee_ {e \ in e} \ psi (e)=bigvee_ {vw \ in e} (v \ wedge W) \ Vee (\ Neg v \ Wedge W) \ Vee (v \ Wedge \ Neg W) $$ وأي مهمة مرضية بالضبط $ | $ | $ يجب أن تكون البنات VC من $ G $ . الآن نحتاج إلى طريقة لترميز حجم VC في كل شيء، والتي يمكننا إعادة استخدام فكرتك. حدد $$ \ PSI (g)=psi ^ \ text {vc} (g) \ vee \ bigvee_ {v \ in v} v $$ ولاحظ أن عدد البنود الراضية في الجزء الثاني يعطى فقط من خلال حجم مجموعة القمم التي نقوم بتحديدها، لذلك العدد الإجمالي للبنات الراضية الموجودة تحت المهمة المقابلة لبعض VC $ x $ in $ g $ هو $ | E | + | X | $ .

هناك مشكلة واحدة فقط تبقى هنا. يمكننا الحصول على مهمة لا تتوافق مع VC ولكن بما في ذلك المزيد من القمم لتلبية نفس العدد من الجمل بأن VC المرغوب فيه. كعلاج، يمكننا تكرار الصيغة الأولى بعض $ | + 1 $ مرات بحيث لا يهم عدد القمم التي اخترتها، فإن العدد الإجمالي للبنود الراضية سيكون دائما منخفضا جدا.

وبالتالي نحصل على الصيغة النهائية $$ \ psi ^ \ ast (g)=bigvee_ {i= 1} ^ {| V | + 1} \ PSI ^ \ Text {vc} (g) \ vee \ bigvee_ {v \ in v} v $$ ولاحظ أنه في حالة $ g $ لديه vc $ x $ ثم سوف ترضي المهمة المقابلة بالضبط $ (| v | + 1) \ cdot | ه | + | X | $ بنود $ \ psi ^ \ ast (g) $ . للاتجاه العكسي، دع $ \ ألفا $ يكون بعض المهام $ (| v | + 1) \ cdot | ه | + K $ بنود $ \ psi ^ \ ast (g) $ . ثم يجب أن تمثل $ \ ألفا $ vc في g كما خلاف ذلك، وعدد البنود الراضية في الجزء الأول من $ \ PSI ^ \ AST (G) $ هو على الأكثر $ (| v | + 1) \ cdot (| e | - 1)= | V | \ CDOT | ه | + | ه | - | الخامس | - 1 دولار وكما $ \ ألفا $ يمكن أن ترضي على الأكثر $ | v | $ البنود في الجزء الثاني، فإن العدد الإجمالي للبنود الراضية سيكون على الأكثر $$ (| الخامس | + 1) \ CDOT (| E | - 1) + | V |= | الخامس | \ CDOT | ه | + | ه | - 1 <(| V | + 1) \ CDOT | ه | $$ ومع ذلك، هذا يعني أن العدد الإجمالي للبنود الراضية في الجزء الأول يجب أن يكون بالضبط $ (| v | + 1) \ cdot | E | $ ، وبالتالي < Span Class="حاوية الرياضيات"> $ K $ quuses من الجزء الثاني راض عن $ \ ألفا $ ، لذلك $ \ ألفا $ يتوافق مع VC $ x_ \ ألفا $ الحجم $ k $ في $ g $ .

لاحظ أنه من أجل الوضوح لم أحدد $ 3 $ صيغة -DNF. ومع ذلك، نظرا لأن جميع البنود في $ \ psi ^ \ ast (g) $ هي من الحجم على الأكثر $ 2 $ يمكنك jus

أضف حرفيات زائدة عن الحاجة إلى البنود لتفجيرها إلى الحجم $ 3 $ إذا لزم الأمر.

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