3سات

مسألة NP كاملة
	قابلية الإرضاء 3SAT; NAE; OIT; ;
	تلوين مخطط تلوين مخطط بثلاثة ألوان; تلوين مخطط مستوبثلاثة ألوان; ;
	زمرة كبرى
	مسار هاملتونياني
	عدل

مسألة 3SAT هي مسألة مشتقة من المسألة العامة SAT، حيث في جميع قوس يوجد ثلاث متغيرات بالضبط. وهي أيضا من المسائل NP الكاملة.

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

يمكن هذا الاختصار من البرهنة على حتى 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 )$ .