المكمل (التعقيد)

الموسوعة الحرة

في نظرية التعقيد الحسابي ، تُعرف متممة مسألة القرار بأنها مسألة القرار الناتجة عن عكس إجابتي "نعم" و " لا" . [ 1 ] وبالمثل، إذا عرّفنا مسائل القرار على أنها مجموعات من السلاسل المحدودة ، فإن متممة هذه المجموعة على نطاق ثابت ما هي مسألة متممتها. [ 2 ]

على سبيل المثال، تتمثل إحدى المشكلات المهمة في تحديد ما إذا كان العدد عددًا أوليًا . أما مكملتها فهي تحديد ما إذا كان العدد عددًا مركبًا (عددًا غير أولي). وهنا، فإن مجال كل من المشكلة الأصلية ومكملتها هو مجموعة جميع الأعداد الطبيعية . [ 3 ]

يوجد اختزال تورينج من كل مسألة إلى مسألتها المكملة. [ 4 ] عملية المكمل هي عملية عكسية ، أي أنها "تعكس نفسها"، أو أن مكمل المكمل هو المسألة الأصلية.

يمكن تعميم ذلك على مكمل فئة التعقيد ، والذي يُسمى فئة المكمل ، وهي مجموعة مكملات كل مسألة في تلك الفئة. [ 5 ] إذا سُميت فئة ما C ، فإن مكملها يُسمى عادةً co-C . لاحظ أن هذا ليس مكمل فئة التعقيد نفسها كمجموعة من المسائل، والتي عادةً ما تحتوي على عدد أكبر بكثير من المسائل.

يُقال إن فئة ما مغلقة تحت المكمل إذا كان مكمل أي مسألة في تلك الفئة لا يزال ضمنها. [ 6 ] ولأن هناك اختزالات تورينج من كل مسألة إلى مكملها، فإن أي فئة مغلقة تحت اختزالات تورينج تكون مغلقة تحت المكمل. أي فئة مغلقة تحت المكمل تساوي فئة مكملها. مع ذلك، في ظل اختزالات "متعدد-واحد" ، يُعتقد أن العديد من الفئات المهمة، وخاصة NP ، متميزة عن فئات مكملها (على الرغم من أن هذا لم يُثبت). [ 7 ]

إن إغلاق أي فئة تعقيد تحت اختزالات تورينج هو مجموعة شاملة لتلك الفئة مغلقة تحت المكمل. والإغلاق تحت المكمل هو أصغر فئة من هذا النوع. إذا تقاطعت فئة مع مكملها، نحصل على مجموعة جزئية (قد تكون فارغة) مغلقة تحت المكمل.

كل فئة تعقيد حتمية ( DTIME ( f ( n ))، DSPACE ( f ( n ))، لأي f ( n )) مغلقة تحت المكمل، [ 8 ] لأنه يمكن ببساطة إضافة خطوة أخيرة إلى الخوارزمية لعكس الإجابة. لا ينطبق هذا على فئات التعقيد غير الحتمية، لأنه إذا وُجدت مسارات حسابية تقبل وأخرى ترفض حالة معينة، وقامت جميع المسارات بعكس إجابتها، فستظل هناك مسارات تقبل وأخرى ترفض – وبالتالي، فإن كلًا من الآلة الأصلية والآلة المعدلة تقبل الحالة.

وبالمثل، فإن الفئات الاحتمالية مثل BPP و ZPP و BQP أو PP التي يتم تعريفها بشكل متناظر فيما يتعلق بحالات نعم ولا تكون مغلقة تحت المكمل، في حين أن الفئات مثل RP و co-RP التي تحدد احتمالاتها بخطأ من جانب واحد ليست (من المعروف حاليًا أنها) مغلقة تحت المكمل.

أظهرت بعض نتائج التعقيد الأكثر إثارة للدهشة التي عُرضت حتى الآن أن فئتي التعقيد NL و SL مغلقتان في الواقع تحت المكمل (انظر نظرية إيمرمان-سيليبسيني )، بينما كان يُعتقد سابقًا على نطاق واسع أنهما ليستا كذلك. وقد أصبح هذا الأخير أقل إثارة للدهشة الآن بعد أن عرفنا أن SL تساوي L ، وهي فئة حتمية.

كل فئة منخفضة بالنسبة لنفسها تكون مغلقة تحت المكمل.

مراجع

  1. ^ إيتو، كيوسي (1993)، القاموس الموسوعي للرياضيات، المجلد الأول ، مطبعة معهد ماساتشوستس للتكنولوجيا، ص.  269، ردمك 9780262590204.
  2. ↑ شريجفر، ألكسندر (1998)، نظرية البرمجة الخطية والبرمجة العددية ، سلسلة وايلي في الرياضيات المتقطعة والتحسين، جون وايلي وأولاده، ص 19، ISBN  9780471982326.
  3. ↑ هومر، ستيفن؛ سيلمان، آلان ل. (2011)، الحوسبة ونظرية التعقيد ، نصوص في علوم الحاسوب، سبرينغر، ISBN 9781461406815.
  4. ↑ سينغ، أرينداما (2009)، عناصر نظرية الحوسبة ، نصوص في علوم الحاسوب، سبرينغر، التمرين 9.10، ص 287، ISBN  9781848824973.
  5. ↑ بوفيه، دانييلي؛ كريشينزي، بييرلويجي (1994)، مقدمة في نظرية التعقيد ، سلسلة برنتيس هول الدولية في علوم الحاسوب، برنتيس هول، الصفحات 133-134 ، ISBN  9780139153808.
  6. ↑ فولمر، هيريبيرت (1999)، مقدمة في تعقيد الدوائر: منهج موحد ، نصوص في علوم الحاسوب النظرية. سلسلة EATCS، سبرينغر، ص 113، ISBN  9783540643104.
  7. ↑ برويم، ر.؛ فيجنر، إنجو (2005)، نظرية التعقيد: استكشاف حدود الخوارزميات الفعالة ، سبرينغر، ص 66، ISBN  9783540274773.
  8. ↑ أوسييلو، جورجيو (1999)، التعقيد والتقريب: مسائل التحسين التوافقي وخصائص قابليتها للتقريب ، سبرينغر، ص 189، ISBN  9783540654315.