3-سات

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

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

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

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

• الصيغة $(x\,)$ و المكونة فقط من متغير، يتم تحويلها إلى صيغة باستعمال ثلاث متغيرات في كل صيغة، فتصبح كما يلي خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\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)} .

• الصيغة خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x\lor y)} و المكونة من متغيرين، يتم تحويلها إلى صيغة باستعمال ثلاث متغيرات في كل صيغة، فتصبح كما يلي خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x\lor y\lor c_i)\wedge(x\lor y \lor \lnot c_i)} .

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

• عند وجود أكثر من ثلاث متغيرات مثلا خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x_1\lor x_2\lor x_3\lor ...\lor x_k )} . هنا نضيف (k-3) متغير جديد يتم توزيعها كما يلي خطأ رياضيات (اعرض بصيغة MathML إن أمكن (تحت التجريب): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\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.