3-سات

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

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

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

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

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

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

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