3-سات

من ويكيبيديا، الموسوعة الحرة

مسألة NP كاملة
زمرة كبرى
مسار هاملتونياني
عدل

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.


هذه بذرة مقالة عن الرياضيات تحتاج للنمو والتحسين؛ فساهم في إثرائها بالمشاركة في تحريرها.
لغات أخرى