3-سات
من ويكيبيديا، الموسوعة الحرة
مسألة NP كاملة |
---|
زمرة كبرى |
مسار هاملتونياني |
عدل |
3 سات اسم يطلق على نوع من المسائل الرياضياتية و المعلوماتية في ميدان المنطق. تسمى المسألة 3 سات 3 SAT إختصارا ل 3 satisfiability .و تبحث هذه المسألة في ما إذا كانت جملة منطقية من نوع Conjunctive normal form تتكون من 3 متغيرات قابلة لأن تكون صحيحة. مسألة 3SAT هي مسألة مشتقة من المسألة العامة SAT، حيث في كل قوس يوجد ثلاث متغيرات بالضبط. و هي أيضا من المسائل NP الكاملة.
[تحرير] الاختصار من SAT إلى 3SAT
يمكن هذا الاختصار من البرهنة على أن 3SAT هو أيضا مسألة NP كاملة، و يتم كما يلي:
- الصيغة
و المكونة فقط من متغير، يتم تحويلها إلى صيغة باستعمال ثلاث متغيرات في كل صيغة، فتصبح كما يلي
.
- الصيغة
و المكونة من متغيرين، يتم تحويلها إلى صيغة باستعمال ثلاث متغيرات في كل صيغة، فتصبح كما يلي
.
- عند وجود صيغة بثلاث متغيرات لا يتم أي تغيير.
- عند وجود أكثر من ثلاث متغيرات مثلا
. هنا نضيف (k-3) متغير جديد يتم توزيعها كما يلي
.
و هذا الاختصار يتم في وقت حدودي، مع ملاحظة أن قيم المتغيرات في SAT هي نفسها قيم 3SAT. كما أن المتغيرات التي يتم اضافتها خاصة بكل عبارة clause.