هو إيجاد حل نظام من 2SAT المعادلات مفصولة أو (DNF شكل) في NP

Question

أريد أن أعرف إذا كان إيجاد حل عدد محدد من 2SAT المعادلات sepearted أو بوابة (DNF الشكل أدناه) في ف أو NP.

المعادلة مجموع n من المتغيرات و كل شرط هو 2SAT المعادلة نفسها في مجموعة من المتغيرات من 1 إلى n.على سبيل المثال:

F = [(x1 || x2 ) && ( !x2 || x3) && (x3 || x4)] || [(x2 || x5) && (x3 || x6) && (!x4 || !x6)] || ....

المعادلة F هو DNF من 2SAT المعادلات التي تقول م بنود.هو إيجاد حل لهذه في NP?إذا كان الجواب نعم كيف ؟

أيضا ، على وجه التحديد أنا أيضا أريد أن أعرف إذا كان إيجاد كاذبة الحالات من المعادلة و هو في الصفحة أو NP كذلك.

Answer 1

• الأول, اسمحوا لي أن أشير إلى أن مسألة العنوان هو قليلا مضللة ، لأن $P$ هو مجموعة فرعية من $NP$.انظر أيضا يوفال السينمائي للبيعus تعليق.أفترض ما كنت المقصود أن نسأل ما إذا كان في $P$ أو في $NP \setminus P$.
• أيضا اسم "DNF" يشير تحديدا إلى انفصال من الابتدائية العطف لا انفصال التعسفي من الوظائف.ما كنت تصف ليست DNF, ولكن انفصال من CNFs.

مع أن الخروج من الطريق ، وهنا جوابي.

---

1. لتلبية انفصال 2-CNFs ، كل ما عليك هو إرضاء واحد منهم.لذا إذا قمت بتطبيق 2-جلس الخوارزمية الأولى من CNFs و الحصول على "نعم" ، ثم الإجابة على المشكلة كلها هي "نعم".وإلا يمكنك فقط الانتقال إلى الثاني وهكذا.لا ينبغي أن تستغرق وقتا طويلا ، حيث لديك فقط م منهم.إذا كان أي منهم يمكن أن يكون راضيا بشكل فردي ، أيهم كل المستمر أصفار ، ثم من الواضح أن الأمر برمته هو ثابت الصفر.

   وبالتالي فإن الإجابة على الجزء الأول هو:المشكلة هي في الصفحة التالية القرار الخوارزمية:

   كل 2-CNF ، تطبيق "طبيعية" 2-جلس خوارزمية (القرار القاعدة) لتحديد ما إذا كان قابل للإرضاء عربية أم لا.إذا كان "نعم" فقط العودة "نعم".إذا ذهبت من خلال كل منهم دون العثور على "نعم" ، ثم العودة "لا".

---

2. الآن العثور على "False" حالات من أن صيغة (المعروف أيضا باسم مشكلة حشوا) هو مسألة أخرى تماما.لشيء واحد ، حشوا الإماهة الفموية من يستخدم المعامل من أملاح الإماهة الفموية يعادل satisfiability على يدي من أملاح الإماهة الفموية من إضافات, دي مورغان القاعدة.ولكن هذا هو أكثر من مجرد حالة العامة بالفعل العامة جلس مشكلة, أليس كذلك ؟

   النظر في ما يحدث عند تقييد مجموعة من الصيغ الممكنة لتلك التي كل اثنين من عناصر التباين هو في الحقيقة مجرد عنصر واحد المتكررة.لذلك هو صيغة مثل $$ F = [(x_1 \مخروطى x_1 ) \& ( eg x_2 \مخروطى eg x_2) \& (x_3 \مخروطى x_3)] \مخروطى [(x_2 \مخروطى x_2) \& (x_4 \مخروطى x_4) \& (x_5 \مخروطى x_5)] \مخروطي ...$$ وهو ما يعادل $$ F = [x_1 \& eg x_2 \& x_3] \مخروطى [x_2 \& x_4 \& x_5] \مخروطي ...$$ الذي هو مجرد الطبيعي DNF.بعد مورغان دي التحول ، ستحصل على CNF التي satisfiability من المعروف أن NP-hard.ولذلك ، فإن أي مشكلة في أن يشمل هذا واحد كمجموعة فرعية كما سيتم على الأقل NP-hard.

   ومن الواضح أن المشكلة في السؤال لن يكون خارج NP, لأنه لا يزال polynomially يمكن التحقق منها.وبالتالي فإن الجواب على السؤال الثاني هو "في NP ، ولكن ليس في الصفحة".