حول تعقيد PCSPs المتناظرة مقابل الوظيفية

تعقيد مشكلة تحقيق قيود الوعد (PCSP (A, B)) غير معروف إلى حد كبير، حتى بالنسبة لـ (A) و(B) المتناظرة، باستثناء الحالة عندما تكون (A) و(B) منطقيتين. أولاً، نثبت وجود انقسام لـ (PCSP (A, B)) حيث يكون (A, B) متناظرين، و(B) وظيفية (أي أن أي (r-1) عنصر من سُلسلة من الرتبة (r) يحدد بشكل فريد العنصر الأخير)، و( (A, B)) تلبي الشروط الفنية التي نقدمها والتي تُسمى الاعتماد والإضافة. تشير هذه النتيجة إلى وجود انقسام لـ (PCSP (A, B)) مع (A, B) متناظرين و(B) وظيفية إذا (i) كانت (A) منطقية، أو (ii) كانت (A) هي هيبرغراف بانتظام صغير، أو (iii) كانت (A) تحتوي على علاقة (R^A) بمرتبة لا تقل عن 3 بحيث يكون قطر الهيبرغراف لـ ( (A, R^A)) لا يزيد عن 1. ثانياً، نظهر أنه بالنسبة لـ (PCSP (A, B))، حيث تحتوي (A) و(B) على علاقة واحدة، و(A) تلبي شرطاً فنياً يُسمى التوازن، و(B) عشوائية، فإن الاسترخاء الأساسي لبرمجة الخطية المركبة ( (BLP)) والاسترخاء للبرمجة الصحيحة الموالية ( (AIP)) ليس أكثر قوة من استرخاء ( (AIP)) (عادةً أضعف بشكل صارم). تشمل (A) المتوازنة (A) المتناظرة أو، بشكل أكثر عمومية، (A) التي تحافظ عليها مجموعة تبديل متعاقبة.