# 3-سات

### من ويكيبيديا، الموسوعة الحرة

مسألة NP كاملة

- قابلية الإرضاء
  - 3سات
  - NAE
  - OIT

- تلوين مخطط
  - تلوين مخطط بثلاثة ألوان
  - تلوين مخطط مستو بثلاثة ألوان

زمرة كبرى
مسار هاملتونياني
عدل

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

## [تحرير] الاختصار من SAT إلى 3SAT

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

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

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

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

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

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

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

تم الاسترجاع من "http://ar.wikipedia.org../../../3/-/%D8%B3/3-%D8%B3%D8%A7%D8%AA.html"

تصنيفات الصفحة: بذرة رياضيات | منطق رياضي | نظرية التعقيد | معلوماتية نظرية | مسائل NP كاملة

##### Views

- مقالة
- نقاش
- النسخة الحالية

##### الموسوعة

- الصفحة الرئيسية
- الأحداث الجارية
- أحدث التغييرات الأساسية

##### تصفح

- المواضيع
- أبجدي
- بوابات

##### المشاركة والمساعدة

- اتصل بنا
- بوابة المجتمع
- مساعدة
- الميدان
- التبرعات

##### ابحث

##### لغات أخرى

- Deutsch
- Français