كم عدد البنود المطلوبة ل SAT ليكون NP-Hard في صيغ CNF؟

Question

ليس من الصعب أن نرى أن جلس صيغة CNF مع $ N $ المتغيرات وعدد ثابت من البنود يمكن حلها في وقت متعدد الحدود. من ناحية أخرى، ليس من الصعب رؤية أن صيغة CNF مع $ n $ المتغيرات و $ O (n) $ الجمل كافية لصون NP (مراقبة على سبيل المثال مثيلات SAT المرتبطة الصيغة الطبيعية لقابلية التلوين الثلاثة، المطبقة على الرسوم البيانية المستوية).

يمكننا تحديد هذا رسميا ك $ \ text {cnfsat} -f- \ text {clauses} $ ، عائلة من المشاكل المعلمة بواسطة وظيفة $ f $ ، حيث توجد حالات صيغ في CNF بحيث يكون لديك $ N $ المتغيرات، ثم لديهم في معظم $ f (n) $ clauses. بناء على ذلك، ما أود أن أعرفه هو ما هو أصغر وظيفة $ g $ بحيث نعلم أن هناك موجودة $ f \ in o (g) $ مثل هذا $ \ text {cnfsat}-text {claus} $ هو بالفعل NP-Hard. نحن نعرف أن g= 1 (ثابت # من البنات) لا يعمل، و $ g= n $ (عدد الخطوط الخطية).

ماذا عن $ g=log n $ ؟ هل هناك خوارزمية بسيطة ل CNFSAT على الصيغ التي تحتوي على $ O (\ lg \ lg n) $ clauses؟

Answer 1

الحد الأدنى. ل $ g \ le c \ cdot \ sqrt {\ log n} $ يوجد خوارزمية زمنية متعددة الحدود وبعد الفكرة هي ما يلي: إذا كان لدى بعض البنود العديد من المتغيرات، فيجب أن تكون تافهة لتحديد بعض المتغيرات لإرضاء هذه الفقرة، دون إيذاء البنود ذات القليل من المتغيرات. نكرر ما يلي:

ابحث عن البند مع أصغر عدد من المتغيرات. دع $ x_1، \ Ldots، x_k $ تكون المتغيرات المشاركة في هذا البند.

• إذا $ k> g $ ، ثم الصيغة بأكملها راضية (نقوم بمعالجة البنود واحدا تلو الآخر وحدد متغير لم نقم بتحديدها من قبل).
• خلاف ذلك، نقوم بإزالة البند. ونحن أيضا إزالة $ x_1، \ Ldots، x_k $ من جميع البنود الأخرى.

الآن، علينا أن نفي البنود التي تمت إزالتها. نظرا لأن هناك على الأكثر $ G $ ، تقدم كل واحد منهم في معظم $ g $ متغيرات جديدة، وهذا يعني أن هناك على الأكثر $ g ^ 2= c ^ 2 \ cdot \ log n $ المتغيرات بشكل عام. لذلك، هناك في معظم $ n ^ {c ^ 2} $ مجموعات متغيرة، ويمكننا فقط استخدام القوة الغاشمة.

العلوي الشرطي العلوي. ضيق تقريبا بالمعنى التالي. افترض أن السفلى ملزمة على السبت مع $ n $ المتغيرات و $ \ ge c \ CDOT N $ clauses (لبعض $ c $ ، على سبيل المثال، القادمة من $ 3 $ -Coloring ) هو $ \ alpha ^ n $ ( $ \ alpha \ in (1، 2] $ ). لاحظ أن نفس الحد الأدنى السفلي يحمل بعد التحول (نظرا لأنه يمكننا فقط تطبيقه قبل أي خوارزمية). لذلك، إذا كان هناك ما لا يقل عن $ \ log ^ {1+ \ epsilon} n $ claus، يمكن أن يكون لديهم $ \ frac {\ log {{1+ \ epsilon} n} c $ المتغيرات والأقلية المنخفضة لوقت التشغيل مشكلتنا هي

$$ \ alpha ^ {\ frac {\ log ^ {1+ \ epsilon} n} c}= n ^ {\ frac {\ log ^ \ epsilon n \ cdot \ Log \ Alpha} {c}}، $

وهو متعدد متعدد الحدود.