حول تكافؤ عدم الاقتراب المعاير لمشكلة الكا-ميديان، الكا-ماكس-كوفيراج، و2-CSP

فرضية عدم الاقتراب المعاير (PIH) هي سؤال مركزي في مجال التعقيد المعاير. تؤكد PIH أنه عند إعطاء 2-CSP على k متغيرات وحجم أبجدية n، فإنه يصعب تمييز ما إذا كانت المدخلات قابلة للإرضاء تمامًا أو إذا كانت كل تعيينات المدخلات تنتهك 1% من القيود. إحدى النتائج المهمة لـ PIH هي أنها تؤدي إلى عدم الاقتراب المعاير الضيق لمشكلة الكا-maxcoverage. في مشكلة الكا-maxcoverage، يتم إعطاء نظام مجموعة كمدخل، وحد >0، ومعامل k والهدف هو تحديد ما إذا كانت هناك k مجموعات في المدخلات التي يكون اتحادها على الأقل جزء من الكون الكامل. من المعروف أن PIH تشير إلى أنه يصعب تمييز ما إذا كانت هناك k مجموعات مدخلات اتحادها على الأقل جزء من الكون أو إذا لم يكن اتحاد كل k مجموعة مدخلات أكبر بكثير من (1-1e) جزء من الكون. في هذا العمل نقدم تقليص FPT يحافظ على الفجوة (في الاتجاه المعاكس) من مشكلة الكا-maxcoverage إلى مشكلة 2-CSP المذكورة، مما يظهر أن التأكيد على أن تقريب مشكلة الكا-maxcoverage إلى بعض العوامل الثابتة هو صعب من النوع W1 يعني PIH. بالإضافة إلى ذلك، نقدم تقليص FPT يحافظ على الفجوة من مشكلة الكا-median (في مقاييس عامة) إلى مشكلة الكا-maxcoverage، مما يبرز أكثر قوة تقليصات FPT التي تحافظ على الفجوة مقارنة بالتقليصات الكلاسيكية التي تحافظ على الفجوة في الوقت المتعدد الحدود.