اختزال متعدد إلى واحد

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

تُعدّ اختزالات "الواحد المتعدد" حالة خاصة وشكلاً أقوى من اختزالات تورينج . ^{[ 1 ]} مع اختزالات "الواحد المتعدد"، يكون الحل (أي الحل الذي نقدمه لـ${\displaystyle L_{2}}$لا يمكن استدعاء ) إلا مرة واحدة في النهاية، ولا يمكن تعديل الإجابة. هذا يعني أنه إذا أردنا عرض تلك المشكلة${\displaystyle L_{1}}$يمكن اختزالها إلى مشكلة${\displaystyle L_{2}}$يمكننا استخدام حلنا لـ${\displaystyle L_{2}}$مرة واحدة فقط في حلنا لـ${\displaystyle L_{1}}$على عكس اختزالات تورينج، حيث يمكننا استخدام حلنا لـ${\displaystyle L_{2}}$بقدر ما يلزم لحل مشكلة العضوية للحالة المعطاة من${\displaystyle L_{1}}$.

استُخدمت اختزالات "الواحد المتعدد" لأول مرة من قبل إميل بوست في ورقة بحثية نُشرت عام 1944. ^{[ 2 ]} وفي وقت لاحق، استخدم نورمان شابيرو المفهوم نفسه في عام 1956 تحت اسم " الاختزال القوي" . ^{[ 3 ]}

العلاقة${\displaystyle \equiv _{m}}$في الواقع، تُعتبر هذه العلاقة تكافؤًا ، وتُسمى فئات التكافؤ الخاصة بها بالدرجات m، وتشكل مجموعة جزئية مرتبة.${\displaystyle {\mathcal {D}}_{m}}$مع النظام الناجم عن${\displaystyle \leq _{m}}$[ ^{4 ] ص 257}

بعض خصائص الدرجات m، والتي يختلف بعضها عن الخصائص المماثلة لدرجات تورينج : ^{[ 4 ] ص 555-581}

• يوجد عامل قفز محدد جيدًا على درجات m.
• الدرجة الوحيدة من الدرجة m مع قفزة 0 _m ′ هي 0 _m .
• هناك درجات m${\displaystyle \mathbf {a} >_{m}{\boldsymbol {0}}_{m}'}$حيث لا يوجد${\displaystyle \mathbf {b} }$أين${\displaystyle \mathbf {b} '=\mathbf {a} }$.
• كل ترتيب خطي قابل للعد ذو عنصر أصغر يُضمّن في${\displaystyle {\mathcal {D}}_{m}}$.
• نظرية الرتبة الأولى لـ${\displaystyle {\mathcal {D}}_{m}}$وهي متماثلة مع نظرية الحساب من الدرجة الثانية.

هناك توصيف لـ${\displaystyle {\mathcal {D}}_{m}}$باعتبارها المجموعة المرتبة جزئيًا الفريدة التي تُحقق العديد من الخصائص الصريحة لمُثُلها ، فقد استعصى وصفٌ مماثل على درجات تورينج. ^{[ 4 ] ص 574-575}

يمكن صياغة نظرية مايهيل للتشاكل على النحو التالي: "لكل مجموعة${\displaystyle A,B}$من الأعداد الطبيعية،${\displaystyle A\equiv B\iff A\equiv _{1}B}$"ونتيجة لذلك،${\displaystyle \equiv }$و${\displaystyle \equiv _{1}}$لها نفس فئات التكافؤ. ^{[ 4 ] ص 325} فئات التكافؤ لـ${\displaystyle \equiv _{1}}$تُسمى هذه الدرجات الأولى .

غالبًا ما تخضع عمليات الاختزال متعددة العناصر لقيود الموارد، على سبيل المثال أن دالة الاختزال قابلة للحساب في وقت متعدد الحدود، ومساحة لوغاريتمية، بواسطة${\displaystyle AC_{0}}$أو${\displaystyle NC_{0}}$الدوائر، أو الإسقاطات متعددة اللوغاريتمات حيث يكون كل مفهوم اختزال لاحق أضعف من المفهوم السابق؛ انظر الاختزال متعدد الحدود والاختزال في الفضاء اللوغاريتمي لمزيد من التفاصيل.

مشاكل اتخاذ القرار${\displaystyle A}$و${\displaystyle B}$وخوارزمية N التي تحل حالات من${\displaystyle B}$يمكننا استخدام اختزال متعدد إلى واحد من${\displaystyle A}$ل${\displaystyle B}$لحل حالات${\displaystyle A}$في:

• الوقت اللازم لـ N بالإضافة إلى الوقت اللازم للتخفيض
• الحد الأقصى للمساحة المطلوبة لـ N والمساحة المطلوبة للتخفيض

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

يمكن للمرء أيضًا أن يسأل عن الحالات المعممة للاختزال المتعدد-الواحد. أحد هذه الأمثلة هو الاختزال الإلكتروني ، حيث نعتبر${\displaystyle f:A\to B}$التي يمكن تعدادها بشكل متكرر بدلاً من الاقتصار على التعداد المتكرر${\displaystyle f}$يُشار إلى علاقة الاختزال الناتجة بـ${\displaystyle \leq _{e}}$وقد دُرست مجموعتها المرتبة جزئيًا بطريقة مشابهة لدراسة درجات تورينج. على سبيل المثال، هناك مجموعة قفز.${\displaystyle {\boldsymbol {0}}_{e}^{'}}$بالنسبة للدرجات e . تتميز الدرجات e ببعض الخصائص التي تختلف عن خصائص مجموعة درجات تورينج المرتبة جزئيًا، على سبيل المثال، تضمين الرسم البياني المعيني في الدرجات أدناه.${\displaystyle {\boldsymbol {'}}_{e}}$[ ^{5 ]​}

• إن علاقات الاختزال المتعدد-الواحد والاختزال-1 هي علاقات متعدية وانعكاسية ، وبالتالي تؤدي إلى ترتيب مسبق على مجموعة القوى للأعداد الطبيعية.
• ${\displaystyle A\leq _{\mathrm {m} }B}$إذا وفقط إذا${\displaystyle \mathbb {N} \setminus A\leq _{\mathrm {m} }\mathbb {N} \setminus B.}$
• تكون المجموعة قابلة للاختزال إلى مسألة التوقف إذا وفقط إذا كانت قابلة للتعداد التكراري . وهذا يعني أنه فيما يتعلق بقابلية الاختزال إلى مسألة التوقف، فإن مسألة التوقف هي الأكثر تعقيدًا بين جميع المسائل القابلة للتعداد التكراري. وبالتالي، فإن مسألة التوقف كاملة تكراريًا. تجدر الإشارة إلى أنها ليست المسألة الكاملة تكراريًا الوحيدة.
• تُعتبر مسألة التوقف المتخصصة لآلة تورينغ فردية T (أي مجموعة المدخلات التي تتوقف عندها T في النهاية) كاملة من نوع "متعدد-واحد" إذا وفقط إذا كانت T آلة تورينغ شاملة . وقد أثبت إميل بوست وجود مجموعات قابلة للتعداد بشكل متكرر ليست قابلة للتقرير ولا كاملة من نوع m، وبالتالي توجد آلات تورينغ غير شاملة تكون مسائل التوقف الفردية الخاصة بها غير قابلة للتقرير .

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