3-سات

مسألة NP كاملة
قابلية الإرضاء 3سات NAE أو آي تي
تلوين مخطط تلوين مخطط بثلاثة ألوان تلوين مخطط مستو بثلاثة ألوان
زمرة كبرى
مسار هاملتونياني
عدل

3 سات اسم يطلق على نوع من المسائل الرياضياتية والمعلوماتية في ميدان المنطق. تسمى المسألة 3 سات 3 SAT اختصارا ل 3 satisfiability. و تبحث هذه المسألة في ما إذا كانت جملة منطقية من نوع Conjunctive normal form تتكون من 3 متغيرات قابلة لأن تكون صحيحة. مسألة 3SAT هي مسألة مشتقة من المسألة العامة SAT، حيث في كل قوس يوجد ثلاث متغيرات بالضبط. وهي أيضا من المسائل NP الكاملة.

الاختصار من SAT إلى 3SAT

يمكن هذا الاختصار من البرهنة على أن 3SAT هو أيضا مسألة NP كاملة، ويتم كما يلي:

• الصيغة $(x)$ والمكونة فقط من متغير، يتم تحويلها إلى صيغة باستعمال ثلاث متغيرات في كل صيغة، فتصبح كما يلي $(x\vee a_i\vee b_i)\wedge (x\vee \mathrm{\neg }{a}_i\vee b_i)\wedge (x\vee a_i\vee \mathrm{\neg }{b}_i)\wedge (x\vee \mathrm{\neg }{a}_i\vee \mathrm{\neg }{b}_i)$.
• الصيغة $(x\vee y)$ والمكونة من متغيرين، يتم تحويلها إلى صيغة باستعمال ثلاث متغيرات في كل صيغة، فتصبح كما يلي $(x\vee y\vee c_i)\wedge (x\vee y\vee \mathrm{\neg }{c}_i)$.
• عند وجود صيغة بثلاث متغيرات لا يتم أي تغيير.
• عند وجود أكثر من ثلاث متغيرات مثلا $(x_1\vee x_2\vee x_3\vee ...\vee x_k)$. هنا نضيف (k-3) متغير جديد يتم توزيعها كما يلي $(x_1\vee x_2\vee z_1)\wedge (x_3\vee \mathrm{\neg }{z}_1\vee z_2)\wedge ...\wedge (x_{k-2}\vee \mathrm{\neg }{z}_{k-4}\vee z_{k-3})\wedge (x_{k-1}\vee \mathrm{\neg }{z}_{k-3}\vee x_k)$.

و هذا الاختصار يتم في وقت حدودي، مع ملاحظة أن قيم المتغيرات في SAT هي نفسها قيم 3SAT. كما أن المتغيرات التي يتم اضافتها خاصة بكل عبارة clause.