الاختزال (التعقيد)

في نظرية الحوسبة ونظرية التعقيد الحسابي ، يُعدّ الاختزال خوارزمية لتحويل مسألة إلى أخرى. ويمكن استخدام اختزال فعّال بدرجة كافية من مسألة إلى أخرى لإثبات أن المسألة الثانية لا تقل صعوبة عن المسألة الأولى.

بشكل بديهي، يمكن اختزال المسألة (أ) إلى المسألة (ب) إذا أمكن استخدام خوارزمية لحل المسألة (ب) بكفاءة (إن وُجدت) كإجراء فرعي لحل المسألة (أ) بكفاءة أيضًا. عندما يتحقق هذا، لا يمكن أن يكون حل المسألة (أ) أصعب من حل المسألة (ب) . يُقصد بـ"أصعب" تقديرًا أعلى للموارد الحسابية المطلوبة في سياق معين (مثل: تعقيد زمني أعلى ، متطلبات ذاكرة أكبر، الحاجة إلى نوى معالجة إضافية للحل المتوازي مقارنةً بالحل أحادي الخيوط، إلخ). يمكن كتابة وجود اختزال من ( أ) إلى (ب) بالاختصار (أ ≤ _م ب) ، وعادةً ما يُضاف رمز سفلي على (≤) للإشارة إلى نوع الاختزال المستخدم (م : اختزال متعدد الحدود ، ص : اختزال متعدد الحدود ).  

يشكل الهيكل الرياضي الناتج عن مجموعة من المشكلات من خلال عمليات الاختزال من نوع معين بشكل عام ترتيبًا مسبقًا ، ويمكن استخدام فئات التكافؤ الخاصة به لتحديد درجات عدم قابلية الحل وفئات التعقيد .

هناك حالتان رئيسيتان نحتاج فيهما إلى استخدام الاختزالات:

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

من الأمثلة البسيطة جدًا على التبسيط التحويل من الضرب إلى التربيع . لنفترض أن كل ما نعرفه هو الجمع والطرح والتربيع والقسمة على اثنين. يمكننا استخدام هذه المعرفة، بالإضافة إلى الصيغة التالية، للحصول على حاصل ضرب أي عددين:

${\displaystyle a\times b={\frac {\left(\left(a+b\right)^{2}-a^{2}-b^{2}\right)}{2}}}$

لدينا أيضًا اختزال في الاتجاه المعاكس؛ فمن الواضح أنه إذا استطعنا ضرب عددين، فبإمكاننا تربيع عدد. وهذا يعني ضمناً أن هاتين المسألتين متساويتان في الصعوبة. هذا النوع من الاختزال يُقابل اختزال تورينج .

لكن عملية الاختزال تصبح أكثر صعوبة إذا أضفنا قيدًا يقضي بأنه لا يمكننا استخدام دالة التربيع إلا مرة واحدة، وفي النهاية فقط. في هذه الحالة، حتى لو سُمح لنا باستخدام جميع العمليات الحسابية الأساسية، بما في ذلك الضرب، فلا يوجد اختزال بشكل عام، لأنه للحصول على النتيجة المطلوبة كمربع، علينا حساب جذرها التربيعي أولًا، وقد يكون هذا الجذر التربيعي عددًا غير نسبي مثل${\displaystyle {\sqrt {2}}}$لا يمكن إنشاء عدد باستخدام العمليات الحسابية على الأعداد النسبية. ولكن، بالاتجاه المعاكس، يمكننا بالتأكيد تربيع عدد ما بعملية ضرب واحدة فقط، في النهاية. باستخدام هذا الشكل المحدود من الاختزال، أظهرنا النتيجة المتوقعة بأن الضرب أصعب عمومًا من التربيع. وهذا يُقابل اختزالًا متعددًا لواحد .

الاختزالية هي ترتيب مسبق ، أي علاقة انعكاسية ومتعدية ، على P ( N ) × P ( N )، حيث P ( N ) هي مجموعة القوى للأعداد الطبيعية .

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

تُعتبر المسألة كاملةً بالنسبة لفئة تعقيد معينة إذا اختُزلت جميع المسائل في تلك الفئة إلى تلك المسألة، وكانت المسألة نفسها جزءًا من تلك الفئة. وبهذا المعنى، تُمثل المسألة الفئة، إذ يُمكن استخدام أي حل لها، بالاقتران مع الاختزالات، لحل جميع المسائل في تلك الفئة.

مع ذلك، لكي تكون عمليات الاختزال مفيدة، يجب أن تكون سهلة . على سبيل المثال، من الممكن اختزال مسألة معقدة من فئة NP-complete، مثل مسألة إرضاء العبارات المنطقية ، إلى مسألة بسيطة، مثل تحديد ما إذا كان عدد ما يساوي صفرًا، وذلك بجعل آلة الاختزال تحل المسألة في وقت أُسّي وتُخرج صفرًا فقط في حال وجود حل. لكن هذا لا يُحقق الكثير، لأنه حتى لو استطعنا حل المسألة الجديدة، فإن إجراء الاختزال لا يقل صعوبة عن حل المسألة القديمة. وبالمثل، يمكن لعملية اختزال تحسب دالة غير قابلة للحساب أن تُختزل مسألة غير قابلة للتقرير إلى مسألة قابلة للتقرير. وكما يُشير مايكل سيبسر في كتابه "مقدمة في نظرية الحوسبة" : "يجب أن يكون الاختزال سهلًا، نسبةً إلى تعقيد المسائل النموذجية في هذه الفئة [...] إذا كان الاختزال نفسه صعب الحساب، فإن الحل السهل للمسألة الكاملة لن يُؤدي بالضرورة إلى حل سهل للمسائل التي تُختزل إليه."

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

في مسائل التحسين (التعظيم أو التصغير)، غالبًا ما نفكر من منظور الاختزالات التي تحافظ على التقريب . لنفترض أن لدينا مسألتين في التحسين بحيث يمكن ربط حالات إحداهما بحالات الأخرى، بحيث يمكن تحويل الحلول شبه المثلى لحالات المسألة الثانية إلى حلول شبه مثلى للأولى. بهذه الطريقة، إذا كان لدينا خوارزمية تحسين (أو خوارزمية تقريب ) تجد حلولًا شبه مثلى (أو مثلى) لحالات المسألة B ، واختزال فعال يحافظ على التقريب من المسألة A إلى المسألة B ، فبتركيبها نحصل على خوارزمية تحسين تُنتج حلولًا شبه مثلى لحالات المسألة A. تُستخدم الاختزالات التي تحافظ على التقريب غالبًا لإثبات صعوبة نتائج التقريب: إذا كانت مشكلة التحسين A صعبة التقريب (في ظل افتراض تعقيد معين) ضمن عامل أفضل من α لبعض α ، وكان هناك اختزال يحافظ على التقريب β من المشكلة A إلى المشكلة B ، فيمكننا أن نستنتج أن المشكلة B يصعب تقريبها ضمن العامل α / β .

• لإثبات أن مسألة القرار A غير قابلة للحل، يجب إيجاد اختزال من مسألة قرار معروفة مسبقًا بأنها غير قابلة للحل إلى A. يجب أن تكون دالة الاختزال هذه دالة قابلة للحساب . على وجه الخصوص، غالبًا ما نثبت أن المسألة A غير قابلة للحل بإثبات أن مسألة التوقف تختزل إلى A.
• تُعتبر فئات التعقيد P و NP و PSPACE مغلقة تحت عمليات الاختزال متعددة الحدود (الواحد المتعدد، "كارب") .
• تُعتبر فئات التعقيد L و NL و P و NP و PSPACE مغلقة تحت اختزال المساحة اللوغاريتمية .

• الاختزال الدقيق
• أداة (علوم الحاسوب)
• اختزال متعدد إلى واحد
• الاختزال المقتصد
• الاختزال (نظرية الاستدعاء الذاتي)
• اختزال جدول الحقيقة
• اختزال تورينج

• توماس هـ. كورمين ، تشارلز إي. ليسرسون ، رونالد ل. ريفست وكليفورد ستاين ، مقدمة في الخوارزميات، مطبعة معهد ماساتشوستس للتكنولوجيا، 2001، ISBN 978-0-262-03293-3
• هارتلي روجرز الابن : نظرية الدوال التكرارية والحوسبة الفعالة، ماكجرو هيل، 1967، رقم ISBN 978-0-262-68052-3.
• بيتر بورغيسر : الاكتمال والاختزال في نظرية التعقيد الجبري، سبرينغر، 2000، رقم ISBN 978-3-540-66752-0.
• إي آر غريفور: دليل نظرية الحوسبة، نورث هولاند، 1999، رقم ISBN 978-0-444-89882-1.