3-سات

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

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوقة. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (يناير 2016)
مسألة NP كاملة
زمرة كبرى
مسار هاملتونياني
عدل

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

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

  • الصيغة والمكونة فقط من متغير، يتم تحويلها إلى صيغة باستعمال ثلاث متغيرات في كل صيغة، فتصبح كما يلي .
  • الصيغة والمكونة من متغيرين، يتم تحويلها إلى صيغة باستعمال ثلاث متغيرات في كل صيغة، فتصبح كما يلي .
  • عند وجود صيغة بثلاث متغيرات لا يتم أي تغيير.
  • عند وجود أكثر من ثلاث متغيرات مثلا . هنا نضيف (k-3) متغير جديد يتم توزيعها كما يلي .

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

  • بوابة تقنية المعلومات
  • بوابة رياضيات
  • بوابة علم الحاسوب
  • بوابة منطق
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.