تخمين الألعاب الفريدة: مشكلة مثيرة للجدل في تعقيد الحوسبة
2025-05-10
اقترح سوبهاش خوت في عام 2002، تخمين الألعاب الفريدة (UGC)، والذي ينص على أن تقريب قيمة نوع محدد من الألعاب، المعروف باسم اللعبة الفريدة، هو NP-صعب. لهذا التخمين آثار كبيرة على نظرية خوارزميات التقريب؛ إذا كان صحيحًا و P≠NP، فلن تسمح العديد من المشاكل المهمة بتقريبات جيدة في وقت متعدد الحدود، وليس فقط الحلول الدقيقة. المجتمع الأكاديمي منقسم حول صحة هذا التخمين، مع وجود صيغ مكافئة تشمل مشاكل تغطية العلامات و Max2Lin(k). على الرغم من دحض إصدارات أقوى، فقد حفز استكشاف UGC أبحاثًا رياضية كبيرة، وقد تم إحراز بعض التقدم نحو إثباته، بما في ذلك إثبات تخمين مرتبط، وهو تخمين ألعاب 2-2.