الاختزال (نظرية الحوسبة)

في نظرية الحوسبة ، تُدرس العديد من علاقات الاختزال (وتُسمى أيضًا الاختزالات ، وقابلية الاختزال ، ومفاهيم الاختزال ). وهي مدفوعة بالسؤال التالي: بالنظر إلى مجموعات معينة${\displaystyle A}$و${\displaystyle B}$هل من الممكن تحويل طريقة تحديد الانتماء إلى مجموعة الأعداد الطبيعية بشكل فعال ؟${\displaystyle B}$إلى طريقة لتحديد العضوية في${\displaystyle A}$إذا كانت الإجابة على هذا السؤال بنعم، فـ${\displaystyle A}$يقال إنه قابل للاختزال إلى${\displaystyle B}$.

إن دراسة مفاهيم الاختزال مدفوعة بدراسة مسائل القرار . بالنسبة للعديد من مفاهيم الاختزال، إذا كانت أي مجموعة غير قابلة للحساب قابلة للاختزال إلى مجموعة${\displaystyle A}$ثم${\displaystyle A}$يجب أن تكون غير قابلة للحساب أيضًا. وهذا يوفر أسلوبًا قويًا لإثبات أن العديد من المجموعات غير قابلة للحساب.

علاقة الاختزال هي علاقة ثنائية على مجموعات الأعداد الطبيعية التي

• خاصية الانعكاس : كل مجموعة قابلة للاختزال إلى نفسها.
• متعدٍ : إذا كانت المجموعة${\displaystyle A}$يمكن اختزالها إلى مجموعة${\displaystyle B}$و${\displaystyle B}$يمكن اختزالها إلى مجموعة${\displaystyle C}$ثم${\displaystyle A}$يمكن اختزاله إلى${\displaystyle C}$.

تشير هاتان الخاصيتان إلى أن قابلية الاختزال هي ترتيب جزئي على مجموعة قوى الأعداد الطبيعية. مع ذلك، لا تُدرس جميع الترتيبات الجزئية كمفاهيم للاختزال. تتميز المفاهيم التي تُدرس في نظرية الحوسبة بالخاصية غير الرسمية التالية:${\displaystyle A}$يمكن اختزاله إلى${\displaystyle B}$إذا وفقط إذا كان هناك أي إجراء لاتخاذ القرار (ربما غير فعال) لـ${\displaystyle B}$يمكن تحويلها بشكل فعال إلى إجراء اتخاذ قرار لـ${\displaystyle A}$تختلف علاقات الاختزال المختلفة في الطرق التي تسمح باستخدامها في عملية التحويل هذه.

إن المفهوم الأساسي للاختزال هو اختزال تورينج . مجموعة${\displaystyle A}$مجموعة الأعداد الطبيعية قابلة للاختزال بواسطة تورينج إلى مجموعة${\displaystyle B}$إذا وفقط إذا كانت هناك آلة تورينج أوراكل التي، عند تشغيلها مع${\displaystyle B}$باعتبارها مجموعة أوراكل الخاصة بها، ستقوم بحساب دالة المؤشر (الدالة المميزة) لـ${\displaystyle A}$أو بعبارة أخرى،${\displaystyle A}$هل يمكن اختزال تورينج إلى${\displaystyle B}$إذا وفقط إذا كانت هناك خوارزمية لحساب دالة المؤشر لـ${\displaystyle A}$بشرط أن يتم تزويد الخوارزمية بوسيلة للإجابة بشكل صحيح على أسئلة من النوع "هل${\displaystyle n}$في${\displaystyle B}$"."

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

تشمل قابلية الاختزال القوية

• قابلية الاختزال أحادي العنصر :${\displaystyle A}$قابل للاختزال أحاديًا إلى${\displaystyle B}$إذا كانت هناك دالة قابلة للحساب من نوع واحد إلى واحد${\displaystyle f}$مع${\displaystyle A(x)=B(f(x))}$للجميع${\displaystyle x}$.
• قابلية الاختزال المتعدد :${\displaystyle A}$هو متعدد-واحد قابل للاختزال إلى${\displaystyle B}$إذا كانت هناك دالة قابلة للحساب${\displaystyle f}$مع${\displaystyle A(x)=B(f(x))}$للجميع${\displaystyle x}$.
• قابل للاختزال باستخدام جدول الحقيقة :${\displaystyle A}$يمكن اختزال جدول الحقيقة إلى${\displaystyle B}$لو${\displaystyle A}$هل يمكن اختزال تورينج إلى${\displaystyle B}$عبر آلة تورينج واحدة (أوراكل) تنتج دالة كلية بالنسبة لكل أوراكل.
• قابل للاختزال باستخدام جدول الحقيقة الضعيف :${\displaystyle A}$هل يمكن اختزال جدول الحقيقة الضعيف إلى${\displaystyle B}$إذا كان هناك اختزال تورينج من${\displaystyle B}$ل${\displaystyle A}$ودالة قابلة للحساب${\displaystyle f}$هذا يحدد نطاق الاستخدام . كلما${\displaystyle A}$يمكن اختزال جدول الحقيقة إلى${\displaystyle B}$،${\displaystyle A}$كما يمكن اختزال جدول الحقيقة الضعيف إلى${\displaystyle B}$، حيث يمكن للمرء أن يبني حدًا قابلًا للحساب على الاستخدام من خلال النظر في الحد الأقصى للاستخدام على شجرة جميع الأوراكل، والذي سيكون موجودًا إذا كان الاختزال كليًا على جميع الأوراكل.
• قابل للاختزال الإيجابي:${\displaystyle A}$موجب قابل للاختزال إلى${\displaystyle B}$إذا وفقط إذا${\displaystyle A}$يمكن اختزال جدول الحقيقة إلى${\displaystyle B}$بطريقة يمكن للمرء أن يحسبها لكل${\displaystyle x}$صيغة تتكون من ذرات على شكل${\displaystyle B(0),B(1),...}$بحيث تتحد هذه الذرات بواسطة روابط "و" و"أو"، حيث يكون "و" من${\displaystyle a}$و${\displaystyle b}$يساوي 1 إذا${\displaystyle a=1}$و${\displaystyle b=1}$وهكذا دواليك.
• قابلية الاختزال في التعداد : على غرار قابلية الاختزال الموجبة، تتعلق بالإجراء الفعال لقابلية التعداد من${\displaystyle A}$ل${\displaystyle B}$.
• قابل للاختزال الانفصالي: يشبه قابل للاختزال الإيجابي مع القيد الإضافي الذي يسمح فقط بـ "أو".
• قابلية الاختزال الاقتراني: مشابهة لقابلية الاختزال الإيجابي مع القيد الإضافي الذي يسمح فقط بـ "و".
• الاختزال الخطي: يشبه الاختزال الموجب، ولكن مع قيد أن جميع الذرات من الشكل${\displaystyle B(n)}$يتم دمجها باستخدام " أو" الحصرية . بعبارة أخرى،${\displaystyle A}$يمكن اختزالها خطيًا إلى${\displaystyle B}$إذا وفقط إذا كانت دالة قابلة للحساب تحسب لكل${\displaystyle x}$مجموعة منتهية${\displaystyle F(x)}$معطاة كقائمة صريحة من الأرقام بحيث${\displaystyle x\in A}$إذا وفقط إذا${\displaystyle F(x)}$يحتوي على عدد فردي من عناصر${\displaystyle B}$.

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

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

• قابلية الاختزال الحسابي : مجموعة${\displaystyle A}$هو حسابي في مجموعة${\displaystyle B}$لو${\displaystyle A}$يمكن تعريفها على النموذج القياسي لحساب بيانو باستخدام مسند إضافي لـ${\displaystyle B}$وبصورة مكافئة، وفقًا لنظرية بوست ، فإن A عدد حسابي في${\displaystyle B}$إذا وفقط إذا${\displaystyle A}$هل يمكن اختزال تورينج إلى${\displaystyle B^{(n)}}$، ال${\displaystyle n}$قفزة تورينج رقم 1 من${\displaystyle B}$، لعدد طبيعي ما${\displaystyle n}$. يوفر التسلسل الهرمي الحسابي تصنيفًا أدق لقابلية الاختزال الحسابي.
• قابلية الاختزال الحسابي الفائق : مجموعة${\displaystyle A}$هو حسابي فائق في مجموعة${\displaystyle B}$لو${\displaystyle A}$يكون${\displaystyle \Delta _{1}^{1}}$قابلة للتعريف (انظر التسلسل الهرمي التحليلي ) على النموذج القياسي لحساب بيانو مع مسند لـ${\displaystyle B}$أو بعبارة أخرى،${\displaystyle A}$هو حسابي فائق في${\displaystyle B}$إذا وفقط إذا${\displaystyle A}$هل يمكن اختزال تورينج إلى${\displaystyle B^{(\alpha )}}$، ال${\displaystyle \alpha }$قفزة تورينج رقم 1 من${\displaystyle B}$بالنسبة للبعض${\displaystyle B}$- الترتيب التكراري${\displaystyle \alpha }$.
• قابلية الإنشاء النسبية : مجموعة${\displaystyle A}$يمكن بناؤها نسبياً من مجموعة${\displaystyle B}$لو${\displaystyle A}$هو في${\displaystyle L(B)}$، أصغر نموذج متعدٍ لنظرية مجموعة ZFC يحتوي على${\displaystyle B}$وجميع الأعداد الترتيبية .

• موسوعة ستانفورد للفلسفة: الدوال التكرارية