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