3-سات

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

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

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

• الصيغة $(x\,)$ و المكونة فقط من متغير، يتم تحويلها إلى صيغة باستعمال ثلاث متغيرات في كل صيغة، فتصبح كما يلي $(x\lor a_{i}\lor b_{i})\wedge (x\lor \lnot a_{i}\lor b_{i})\wedge (x\lor a_{i}\lor \lnot b_{i})\wedge (x\lor \lnot a_{i}\lor \lnot b_{i})$.

• الصيغة $(x\lor y)$ و المكونة من متغيرين، يتم تحويلها إلى صيغة باستعمال ثلاث متغيرات في كل صيغة، فتصبح كما يلي $(x\lor y\lor c_{i})\wedge (x\lor y\lor \lnot c_{i})$.

• عند وجود صيغة بثلاث متغيرات لا يتم أي تغيير.

• عند وجود أكثر من ثلاث متغيرات مثلا $(x_{1}\lor x_{2}\lor x_{3}\lor ...\lor x_{k})$. هنا نضيف (k-3) متغير جديد يتم توزيعها كما يلي $(x_{1}\lor x_{2}\lor z_{1})\wedge (x_{3}\lor \lnot z_{1}\lor z_{2})\wedge ...\wedge (x_{k-2}\lor \lnot z_{k-4}\lor z_{k-3})\wedge (x_{k-1}\lor \lnot z_{k-3}\lor x_{k})$.

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