3-سات

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

• الصيغة ${\displaystyle (x\,)}$ والمكونة فقط من متغير، يتم تحويلها إلى صيغة باستعمال ثلاث متغيرات في كل صيغة، فتصبح كما يلي ${\displaystyle (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})}$.
• الصيغة ${\displaystyle (x\lor y)}$ والمكونة من متغيرين، يتم تحويلها إلى صيغة باستعمال ثلاث متغيرات في كل صيغة، فتصبح كما يلي ${\displaystyle (x\lor y\lor c_{i})\wedge (x\lor y\lor \lnot c_{i})}$.
• عند وجود صيغة بثلاث متغيرات لا يتم أي تغيير.
• عند وجود أكثر من ثلاث متغيرات مثلا ${\displaystyle (x_{1}\lor x_{2}\lor x_{3}\lor ...\lor x_{k})}$. هنا نضيف (k-3) متغير جديد يتم توزيعها كما يلي ${\displaystyle (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.

• بوابة تقانة المعلومات
• بوابة رياضيات
• بوابة علم الحاسوب
• بوابة منطق