APX

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

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

تعريف

تُسمى خوارزمية التقريب بـو(ن){\displaystyle f(n)}خوارزمية تقريبية لحجم المدخلاتن{\displaystyle n}إذا أمكن إثبات أن الحل الذي تجده الخوارزمية هو على الأكثر عامل ضربي لـو(ن){\displaystyle f(n)}أسوأ بكثير من الحل الأمثل. هنا،و(ن){\displaystyle f(n)}تُسمى هذه النسبة نسبة التقريب . وتُعرف مسائل APX بأنها تلك التي تحتوي خوارزمياتها على نسبة تقريبو(ن){\displaystyle f(n)}ثابتج{\displaystyle c}تُذكر نسبة التقريب عادةً بأنها أكبر من 1. في حالة مسائل التصغير،و(ن){\displaystyle f(n)}يتم حساب ذلك بقسمة درجة الحل المُكتشف على درجة الحل الأمثل، بينما في مسائل التعظيم يكون العكس صحيحًا. ففي مسائل التعظيم، حيث يكون للحل الأدنى درجة أقل،و(ن){\displaystyle f(n)}يُذكر أحيانًا أنه أقل من 1؛ في مثل هذه الحالات، يكون مقلوبو(ن){\displaystyle f(n)}هي نسبة درجة الحل الذي تم التوصل إليه إلى درجة الحل الأمثل.

يُقال إن للمسألة مخطط تقريب زمني متعدد الحدود ( PTAS ) إذا كان لكل عامل ضربي للحل الأمثل أسوأ من 1، توجد خوارزمية زمنية متعددة الحدود لحل المسألة ضمن هذا العامل. ما لم تكن P = NP، توجد مسائل تنتمي إلى APX ولكن بدون مخطط تقريب زمني متعدد الحدود، لذا فإن فئة المسائل التي تحتوي على مخطط تقريب زمني متعدد الحدود محصورة تمامًا في APX. ومن أمثلة المسائل التي تحتوي على مخطط تقريب زمني متعدد الحدود مسألة حقيبة الظهر .

صلابة APX واكتمال APX

يُقال إن المسألة صعبة من فئة APX إذا كان هناك اختزال باستخدام خوارزمية تقريبية متعددة الحدود (PTAS) من كل مسألة في APX إلى تلك المسألة، وتُعتبر كاملة من فئة APX إذا كانت المسألة صعبة من فئة APX وفي APX أيضًا. ونتيجةً لـ P ≠ NP ⇒ PTAS ≠ APX، إذا افترضنا أن P ≠ NP، فلن يكون لأي مسألة صعبة من فئة APX خوارزمية تقريبية متعددة الحدود. عمليًا، غالبًا ما يتم اختزال مسألة إلى أخرى لإثبات اكتمال APX باستخدام مخططات اختزال أخرى، مثل اختزالات L ، التي تتضمن اختزالات باستخدام خوارزمية تقريبية متعددة الحدود.

أمثلة

تُعدّ مسألة MAX-3SAT ، وهي صيغة من مسائل الإرضاء المنطقي ، من أبسط مسائل APX-complete . في هذه المسألة، لدينا صيغة منطقية في شكلها الطبيعي الاقتراني ، حيث يظهر كل متغير ثلاث مرات على الأكثر، ونريد معرفة الحد الأقصى لعدد البنود التي يمكن تحقيقها في آنٍ واحد بتعيين قيمة واحدة صحيحة/خاطئة للمتغيرات.

تشمل المشاكل الأخرى التي تتطلب إكمال اختبار APX ما يلي:

PTAS

تتألف خوارزمية تقريب الوقت متعدد الحدود (PTAS ) من مسائل يمكن تقريبها ضمن أي عامل ثابت غير 1 في وقت متعدد الحدود بالنسبة لحجم المدخلات، ولكن هذا الوقت يعتمد على هذا العامل. وتُعد هذه الفئة مجموعة فرعية من خوارزمية تقريب الوقت متعدد الحدود (APX).

APX-متوسط

ما لم تكن P = NP ، توجد مسائل في APX لا تنتمي إلى PTAS ولا إلى APX-كاملة. يمكن اعتبار هذه المسائل متوسطة الصعوبة بين مسائل PTAS ومسائل APX-كاملة، ويمكن تسميتها مسائل APX-متوسطة . تُعتبر مسألة تعبئة الصناديق مسألة APX-متوسطة. على الرغم من عدم وجود PTAS معروف لها، إلا أن مسألة تعبئة الصناديق لها العديد من خوارزميات "PTAS التقاربية"، التي تتصرف مثل PTAS عندما يكون الحل الأمثل كبيرًا، لذا قد يكون حلها أسهل من المسائل الصعبة في APX.

ومن الأمثلة الأخرى على المشاكل التي قد تكون متوسطة المستوى في APX هي تلوين الحواف الأدنى .

f(n)-APX

يمكن للمرء أيضًا تعريف مجموعة من فئات التعقيدو(ن){\displaystyle f(n)}-APX، حيثو(ن){\displaystyle f(n)}يحتوي برنامج APX على مسائل تتضمن خوارزمية تقريبية ذات زمن متعدد الحدود معيا(و(ن)){\displaystyle O(f(n))}نسبة التقريب. ويمكن تعريفها بشكل مماثل.و(ن){\displaystyle f(n)}فئات APX الكاملة؛ تحتوي بعض هذه الفئات على مسائل تحسين معروفة. يتم تعريف اكتمال Log-APX واكتمال poly-APX بدلالة اختزالات AP بدلاً من اختزالات PTAS؛ وذلك لأن اختزالات PTAS ليست قوية بما يكفي للحفاظ على الانتماء إلى Log-APX وPoly-APX، على الرغم من أنها كافية لـ APX.

تتضمن مجموعة Log-APX-complete، التي تتكون من أصعب المشكلات التي يمكن تقريبها بكفاءة ضمن عامل لوغاريتمي في حجم الإدخال، مجموعة الهيمنة الدنيا عندما تكون الدرجة غير محدودة.

تتضمن مسألة Poly-APX-complete، التي تتكون من أصعب المسائل التي يمكن تقريبها بكفاءة ضمن عامل متعدد الحدود في حجم الإدخال، مجموعة مستقلة قصوى في الحالة العامة.

توجد أيضًا مسائل كاملة من نوع exp-APX، حيث تكون نسبة التقريب أسية بالنسبة لحجم المدخلات. قد يحدث هذا عندما يعتمد التقريب على قيمة الأعداد داخل المسألة؛ ويمكن التعبير عن هذه الأعداد في الفضاء بشكل لوغاريتمي، ومن هنا يأتي العامل الأسي.

انظر أيضاً

مراجع