3-سات

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

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

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

• الصيغة و المكونة فقط من متغير، يتم تحويلها إلى صيغة باستعمال ثلاث متغيرات في كل صيغة، فتصبح كما يلي .

• الصيغة و المكونة من متغيرين، يتم تحويلها إلى صيغة باستعمال ثلاث متغيرات في كل صيغة، فتصبح كما يلي .

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

• عند وجود أكثر من ثلاث متغيرات مثلا . هنا نضيف (k-3) متغير جديد يتم توزيعها كما يلي .

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