صعوبة التقريب

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

تُكمّل صعوبة التقريب دراسة خوارزميات التقريب من خلال إثبات، بالنسبة لبعض المسائل، حدًا للعوامل التي يمكن من خلالها تقريب حلها بكفاءة. عادةً ما تُظهر هذه الحدود عامل تقريب يتجاوزه حل المسألة ليصبح من فئة NP-hard ، مما يعني استحالة إيجاد تقريب زمني متعدد الحدود للمسألة إلا إذا كان NP=P . مع ذلك، تستند بعض نتائج صعوبة التقريب إلى فرضيات أخرى، من أبرزها فرضية الألعاب الفريدة .

منذ أوائل سبعينيات القرن الماضي، كان معروفًا أن العديد من مسائل التحسين لا يمكن حلها في زمن متعدد الحدود إلا إذا كانت P = NP ، ولكن في كثير من هذه المسائل، يمكن تقريب الحل الأمثل بكفاءة إلى حد معين. في سبعينيات القرن الماضي، بدأ تيوفيلو ف. غونزاليس وسارتاج ساهني دراسة صعوبة التقريب، من خلال إظهار أن بعض مسائل التحسين كانت صعبة الحل من فئة NP حتى عند تقريبها ضمن نسبة تقريب معينة . أي أنه بالنسبة لهذه المسائل، توجد عتبة بحيث يمكن استخدام أي تقريب متعدد الحدود بنسبة تقريب تتجاوز هذه العتبة لحل مسائل NP-كاملة في زمن متعدد الحدود. ^{[ 1 ]} في أوائل تسعينيات القرن الماضي، مع تطور نظرية PCP ، أصبح من الواضح أن العديد من مسائل التقريب الأخرى يصعب تقريبها، وأن العديد من خوارزميات التقريب المعروفة (إلا إذا كانت P = NP) تحقق أفضل نسبة تقريب ممكنة.

تتناول نظرية صعوبة التقريب دراسة عتبة التقريب لمثل هذه المشكلات.

للحصول على مثال لمشكلة تحسين صعبة من نوع NP والتي يصعب تقريبها، انظر إلى تغطية المجموعة وتغطية الرأس .

• نظرية PCP

• Trevisan, Luca (July 27, 2004), Inapproximability of Combinatorial Optimization Problems(PDF), arXiv:cs/0409043, Bibcode:2004cs........9043T

• CSE 533: The PCP Theorem and Hardness of Approximation, Autumn 2005, syllabus from the University of Washington, Venkatesan Guruswami and Ryan O'Donnell