الأدوات الجبرية العالمية للتلبية الضاغطة

الملخص: تتمثل مشكلة تلبية القيود (CSP) في هيكل علاقة محدودة B في اتخاذ قرار، بالنظر إلى مجموعة من القيود على المتغيرات حيث تأتي العلاقات من B، ما إذا كان هناك تخصيص للمتغيرات يلبي جميع القيود؛ CSP الضاغطة هي النسخة التي يتم فيها اتخاذ قرار بشأن وجود تخصيص ضاغط يلبي جميع العناصر في كون B. نقدم إطارًا جبريًا لإثبات نتائج الصعوبة المتعلقة بـ CSPs الضاغطة؛ في الأساس، يحسب هذا الإطار الأدوات العالمية التي تسمح بتقديم تقليص من CSP كلاسيكي إلى CSP ضاغط. نوضح كيفية اشتقاق عدد من نتائج الصعوبة لـ CSP الضاغطة في هذا الإطار، بما في ذلك صعوبة مشكلة القطع المنفصلة، ومشكلة التلوين الثلاثي بلا قوس قزح، وCSP الضاغطة على جميع الهياكل الثنائية العناصر المعروفة بأنها صعبة الحل (في هذا الإطار). وبالتالي، يسمح لنا إطارنا بتوحيد هذه النتائج الصعبة وكشف الهيكل المشترك بينها؛ نعتقد أن إثباتنا للصعوبة لمشكلة القطع المنفصلة أكثر اختصارًا من الأصلي. من وجهة نظرنا، يجعل الإطار أيضًا طريقة شفافة جدًا يمكن من خلالها تقليص CSPs الكلاسيكية إلى CSPs ضاغطة.