اختزال الوقت متعدد الحدود

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

في نظرية التعقيد الحسابي ، يُعدّ الاختزال متعدد الحدود طريقةً لحلّ مسألةٍ ما باستخدام مسألةٍ أخرى. ويُبيّن هذا الأسلوب أنه إذا وُجدت دالةٌ فرعيةٌ افتراضيةٌ لحلّ المسألة الثانية، فإنه يُمكن حلّ المسألة الأولى بتحويلها أو اختزالها إلى مُدخلاتٍ للمسألة الثانية، ثم استدعاء الدالة الفرعية مرةً واحدةً أو أكثر. وإذا كان كلٌّ من الوقت اللازم لتحويل المسألة الأولى إلى الثانية وعدد مرات استدعاء الدالة الفرعية متعدد الحدود ، فإن المسألة الأولى قابلةٌ للاختزال متعدد الحدود إلى المسألة الثانية. [ 1 ]

يُثبت اختزال الوقت متعدد الحدود أن المسألة الأولى ليست أصعب من الثانية، لأنه كلما وُجدت خوارزمية فعّالة للمسألة الثانية، وُجدت خوارزمية مماثلة للمسألة الأولى. وبالعكس ، إذا لم توجد خوارزمية فعّالة للمسألة الأولى، فلن توجد خوارزمية مماثلة للمسألة الثانية أيضًا. [ 1 ] تُستخدم اختزالات الوقت متعدد الحدود بكثرة في نظرية التعقيد لتحديد كلٍّ من فئات التعقيد والمسائل الكاملة لتلك الفئات.

أنواع التخفيضات

أكثر ثلاثة أنواع شيوعًا من الاختزال متعدد الحدود، مرتبة من الأكثر تقييدًا إلى الأقل، هي: اختزالات متعددة الحدود متعددة الحدود للوحدات المتعددة ، واختزالات جداول الحقيقة ، واختزالات تورينج . أكثرها استخدامًا هي اختزالات الوحدات المتعددة، وفي بعض الحالات قد يُستخدم مصطلح "اختزال متعدد الحدود" للدلالة على اختزال متعدد الحدود متعدد الحدود للوحدات المتعددة. [ 2 ] أكثر أنواع الاختزال عمومية هي اختزالات تورينج، وأكثرها تقييدًا هي اختزالات الوحدات المتعددة، بينما تحتل اختزالات جداول الحقيقة مكانة متوسطة بينهما. [ 3 ]

تخفيضات متعددة

الاختزال متعدد الحدود ذو القيمة الواحدة من مسألة A إلى مسألة B (والتي يُشترط عادةً أن تكون كلتاهما مسائل قرار ) هو خوارزمية متعددة الحدود لتحويل مدخلات المسألة A إلى مدخلات المسألة B ، بحيث يكون للمسألة المُحوَّلة نفس مخرجات المسألة الأصلية. يمكن حل حالة x من المسألة A بتطبيق هذا التحويل لإنتاج حالة y من المسألة B ، وإعطاء y كمدخل لخوارزمية حل المسألة B ، وإرجاع مخرجاتها. تُعرف عمليات الاختزال متعددة الحدود ذات القيمة الواحدة أيضًا باسم التحويلات متعددة الحدود أو اختزالات كارب ، نسبةً إلى ريتشارد كارب . يُرمز إلى هذا النوع من الاختزال بـأ≤مPب{\displaystyle A\leq _{m}^{P}B}أوأ≤صب{\displaystyle A\leq _{p}B}[ 4 ] [ 1 ]​

اختزالات جداول الحقيقة

يُعدّ اختزال جدول الحقيقة في زمن متعدد الحدود من المسألة A إلى المسألة B (وكلاهما مسائل قرار) خوارزميةً ذات زمن متعدد الحدود لتحويل مدخلات المسألة A إلى عدد ثابت من مدخلات المسألة B ، بحيث يمكن التعبير عن مخرجات المسألة الأصلية كدالة لمخرجات B. يجب أن تكون الدالة التي تربط مخرجات B بمخرجات A هي نفسها لجميع المدخلات، حتى يمكن التعبير عنها بجدول حقيقة . يمكن الإشارة إلى هذا النوع من الاختزال بالتعبير التالي:أ≤تتPب{\displaystyle A\leq _{tt}^{P}B}[ 5 ]​

اختزالات تورينج

الاختزال التورينغي ذو الزمن متعدد الحدود من المسألة أ إلى المسألة ب هو خوارزمية تحل المسألة أ باستخدام عدد متعدد الحدود من استدعاءات روتين فرعي للمسألة ب ، وزمن متعدد الحدود خارج نطاق استدعاءات هذا الروتين الفرعي. تُعرف اختزالات تورينغ ذات الزمن متعدد الحدود أيضًا باسم اختزالات كوك ، نسبةً إلى ستيفن كوك . ويمكن الإشارة إلى هذا النوع من الاختزال بالتعبير التالي:أ≤تيPب{\displaystyle A\leq _{T}^{P}B}[ 4 ] يمكن اعتبار عمليات الاختزال المتعددة على أنها متغيرات مقيدة لعمليات اختزال تورينج حيث يكون عدد الاستدعاءات التي يتم إجراؤها للروتين الفرعي للمشكلة B هو واحد بالضبط والقيمة التي يتم إرجاعها بواسطة الاختزال هي نفس القيمة التي يتم إرجاعها بواسطة الروتين الفرعي.

اكتمال

المسألة الكاملة لفئة تعقيد معينة C واختزال ≤ هي مسألة P تنتمي إلى C ، بحيث يكون لكل مسألة A في C اختزال A ≤ P. على سبيل المثال، تُعتبر المسألة NP- كاملة إذا كانت تنتمي إلى NP وجميع المسائل في NP لها اختزالات متعددة الحدود ذات زمن متعدد الحدود. يمكن إثبات أن مسألة تنتمي إلى NP هي NP- كاملة من خلال إيجاد اختزال واحد متعدد الحدود ذي زمن متعدد الحدود لها من مسألة NP- كاملة معروفة. [ 6 ] استُخدمت الاختزالات متعددة الحدود ذات الزمن المتعدد لتعريف مسائل كاملة لفئات تعقيد أخرى، بما في ذلك لغات PSPACE- كاملة ولغات EXPTIME- كاملة . [ 7 ]

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

تحديد فئات التعقيد

لا تتضمن تعريفات فئات التعقيد NP و PSPACE و EXPTIME عمليات اختزال؛ إذ لا تدخل عمليات الاختزال في دراستها إلا عند تعريف اللغات الكاملة لهذه الفئات. مع ذلك، في بعض الحالات، يمكن تعريف فئة تعقيد باستخدام عمليات الاختزال. إذا كانت C أي مسألة قرار ، فيمكن تعريف فئة تعقيد C تتكون من اللغات A التيأ≤مPج{\displaystyle A\leq _{m}^{P}C}في هذه الحالة، ستكون C مكتملة تلقائيًا بالنسبة لـ C ، ولكن قد يكون لدى C مشاكل مكتملة أخرى أيضًا.

ومن الأمثلة على ذلك فئة التعقيد∃R{\displaystyle \exists \mathbb {R} }تم تعريفها من النظرية الوجودية للأعداد الحقيقية ، وهي مشكلة حسابية معروفة بأنها صعبة من نوع NP وفي PSPACE ، ولكن من غير المعروف أنها كاملة بالنسبة لـ NP أو PSPACE أو أي لغة في التسلسل الهرمي متعدد الحدود .∃R{\displaystyle \exists \mathbb {R} }هي مجموعة المسائل التي يمكن اختزالها إلى نظرية الوجود للأعداد الحقيقية في وقت متعدد الحدود؛ ولها عدة مسائل كاملة أخرى مثل تحديد عدد التقاطعات المستقيمة في رسم بياني غير موجه . كل مسألة في∃R{\displaystyle \exists \mathbb {R} }يرث خاصية الانتماء إلى PSPACE ، وكل∃R{\displaystyle \exists \mathbb {R} }المسألة الكاملة هي مسألة صعبة من نوع NP . [ 9 ]

وبالمثل، تتألف فئة التعقيد GI من المسائل التي يمكن اختزالها إلى مسألة تماثل الرسوم البيانية . ولأن تماثل الرسوم البيانية معروف بانتمائه إلى كل من NP و co- AM ، فإن الأمر نفسه ينطبق على كل مسألة في هذه الفئة. تُعتبر المسألة كاملةً في GI إذا كانت كاملةً لهذه الفئة؛ ومسألة تماثل الرسوم البيانية نفسها كاملة في GI ، وكذلك العديد من المسائل الأخرى ذات الصلة. [ 10 ]

انظر أيضاً

مراجع

  1. 1 2 3 كلينبيرج, جون ; تاردوس، إيفا (2006). تصميم الخوارزمية . تعليم بيرسون. ص 452 – 453. ISBN  978-0-321-37291-8.
  2. ↑ فيجنر، إنجو (2005)، نظرية التعقيد: استكشاف حدود الخوارزميات الفعالة ، سبرينغر، ص 60، ISBN  9783540274773.
  3. ↑ ماندال، ديباسيس؛ بافان، أ.؛ فينوجوبالان، راجيسواري (2014). فصل اكتمال كوك عن اكتمال كارب-ليفين في ظل فرضية صعوبة أسوأ الحالات . المؤتمر الدولي الرابع والثلاثون حول أسس تكنولوجيا البرمجيات وعلوم الحاسوب النظرية. ISBN 978-3-939897-77-4.
  4. 1 2 غولدريتش، أوديد (2008)، التعقيد الحسابي: منظور مفاهيمي ، مطبعة جامعة كامبريدج، ص 59-60 ، ISBN  9781139472746
  5. ↑ بوس، إس آر ؛ هاي، إل. (1988)، "حول قابلية اختزال جدول الحقيقة إلى SAT والتسلسل الهرمي للاختلاف على NP"، وقائع المؤتمر السنوي الثالث لبنية نظرية التعقيد ، ص 224-233 ، CiteSeerX 10.1.1.5.2387 ، doi : 10.1109/SCT.1988.5282 ، ISBN   978-0-8186-0866-7.
  6. ↑ غاري، مايكل ر.؛ جونسون ، د. س. (1979)، الحواسيب والاستعصاء: دليل لنظرية اكتمال NP ، دبليو إتش فريمان.
  7. ↑ أهو، أ. ف. (2011)، "نظرية التعقيد"، في بلوم، إ. ك.؛ أهو، أ. ف. (محرران)، علوم الحاسوب: الأجهزة والبرمجيات وجوهرها ، ص 241-267 ، doi : 10.1007/978-1-4614-1168-0_12 ، ISBN  978-1-4614-1167-3انظر على وجه الخصوص الصفحة  255.
  8. ↑ غرينلو، ريموند؛ هوفر، جيمس؛ روزو، والتر (1995)، حدود الحوسبة المتوازية؛ نظرية الاكتمال-P ، ISBN 978-0-19-508591-4. على وجه الخصوص، بالنسبة للحجة القائلة بأن كل مشكلة غير تافهة في P لها اختزال متعدد الحدود إلى كل مشكلة غير تافهة أخرى، انظر الصفحة  48.
  9. ↑ شيفر، ماركوس (2010)، "تعقيد بعض المسائل الهندسية والطوبولوجية" (ملف PDF) ، رسم المخططات، الندوة الدولية السابعة عشرة، GS 2009، شيكاغو، إلينوي، الولايات المتحدة الأمريكية، سبتمبر 2009، أوراق منقحة ، سلسلة محاضرات في علوم الحاسوب، المجلد 5849، سبرينغر-فيرلاغ، الصفحات 334-344 ، doi : 10.1007/978-3-642-11805-0_32 ، ISBN   978-3-642-11804-3.
  10. ^ كوبلر، يوهانس. الأماكن القريبة : توران ، جاكوبو (1993)، مشكلة تماثل الرسم البياني: تعقيدها الهيكلي ، بيركهاوزر، ISBN 978-0-8176-3680-7، OCLC 246882287 .