قابلية الاختزال ودرجات عدم القابلية للحل

تقارن قابلية الاختزال صعوبة المشكلات عن طريق تحويل إحداها إلى الأخرى، وينتج عن تجميع المشكلات ذات الصعوبة المتساوية درجات عدم القابلية للحل التي تشكل العالم خارج نطاق ما يمكن حسابه.

Definition

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

Scope

يغطي هذا الموضوع قابلية الاختزال من نوع واحد إلى متعدد (many-one) وقابلية اختزال تورينج (Turing reducibility)، واستخدام الاختزالات لإثبات عدم القابلية للتقرير (undecidability)، وعملية قفزة تورينج (Turing jump) التي تنتج مشكلات أكثر صعوبة بشكل صارم، والتسلسل الهرمي الحسابي (arithmetical hierarchy) الذي يصنف المشكلات حسب التعقيد المنطقي، والنتائج المركزية لنظرية الدرجات مثل وجود درجات وسيطة.

Core questions

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

Key theories

قابلية الاختزال وقفزة تورينج

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

وجود الدرجات الوسيطة

حل مبرهنة فريدبرغ-موشنيك مشكلة بوست عن طريق بناء مشكلات قابلة للعد حسابيًا غير قابلة للتقرير ولكنها أسهل بشكل صارم من مشكلة التوقف، باستخدام طريقة الأولوية، مما يدل على أن الدرجات لها بنية غنية.

Clinical relevance

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

History

قدم تورينج آلات الأوراكل (oracle machines) في عام 1939، وفي عام 1944، صاغ بوست دراسة درجات عدم القابلية للحل وطرح مشكلة ما إذا كانت هناك درجات وسيطة قابلة للعد حسابيًا (computably enumerable degrees). حلها فريدبرغ وموشنيك بشكل مستقل في 1956-1957 عن طريق ابتكار طريقة الأولوية (priority method)، والتي أصبحت تقنية مركزية في هذا المجال.

Key figures

• Emil Post
• Alan Turing
• Richard Friedberg
• Albert Muchnik

Seminal works

• soare2016
• rogers1987

Frequently asked questions

ما هو الاختزال، بشكل بديهي؟

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

هل توجد مشكلات أصعب من مشكلة التوقف؟

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