تماكل بيانين

معطيات : بيانين و المطلوب : البيانين و هل هما متشابهان ؟ أو بمعنى آخر, هل توجد دالة عكسية بحيث

هذا وتعتبر مسألة تصنيف مسألة التماكل الخاصة بالبيانات من المسائل غير المحلولة في الوقت الراهن، فالمسألة من صنف NP، لكن هل هي P أو NP_complet؟.

مثال

عدل

البيانان أدناه متشاكلان، رغم الاختلاف الكبير في طريقة رسمهما، والسبب هو وجود العلاقة الموضحة على الجانب الأيسر.

بيان G بيان H تشاكل
بين G و H

تمديد المسألة

عدل

معطيات : بيانين   و  المطلوب : البيان   هل هو ضمن البيان   ؟ أي بالمعنى الرياضي:

  •  
  •  

و تعتبر المسألة أصعب بكثير من المسألة الأولى وهي تصنف ضمن NP_complet.


المراجع

عدل