3سات

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

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

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

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

الصيغة $(x)$ و المكونة فقط من متغير، يتم تحويلها إلى صيغة باستعمال ثلاث متغيرات في كل صيغة، فتصبح كما يلي $(x \lor a_{i} \lor b_{i}) \land (x \lor \neg a_{i} \lor b_{i}) \land (x \lor a_{i} \lor \neg b_{i}) \land (x \lor \neg a_{i} \lor \neg b_{i})$ .
الصيغة $(x \lor y)$ و المكونة من متغيرين، يتم تحويلها إلى صيغة باستعمال ثلاث متغيرات في كل صيغة، فتصبح كما يلي $(x \lor y \lor c_{i}) \land (x \lor y \lor \neg c_{i})$ .
عند وجود صيغة بثلاث متغيرات لا يتم أي تغيير.
عند وجود أكثر من ثلاث متغيرات مثلا $(x_{1} \lor x_{2} \lor x_{3} \lor . . . \lor x_{k})$ . هنا نضيف (k-3) متغير جديد يتم توزيعها كما يلي $(x_{1} \lor x_{2} \lor z_{1}) \land (x_{3} \lor \neg z_{1} \lor z_{2}) \land . . . \land (x_{k - 2} \lor \neg z_{k - 4} \lor z_{k - 3}) \land (x_{k - 1} \lor \neg z_{k - 3} \lor x_{k})$ .

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

هذه بذرة مقالة عن الرياضيات تحتاج للنمو والتحسين، ساهم في إثرائها بالمشاركة في تحريرها.