تعقيد إرضاء القيود

يمكن تحقيق قابلية المعالجة بتقييد المجالات أو القيود الممكنة. وعلى وجه الخصوص، تم النظر في نوعين من القيود:

• تحدد القيود العلائقية المجال والقيم التي تفي بالقيود؛
• تحدد القيود الهيكلية طريقة توزيع القيود على المتغيرات.

بتعبير أدق، يُحدد القيد العلائقي لغة قيود ، وهي عبارة عن نطاق ومجموعة من العلاقات ضمن هذا النطاق. وتُحقق مسألة إرضاء القيود هذا القيد إذا كان نطاقها مطابقًا تمامًا لهذا النطاق، وكانت علاقة كل قيد ضمن مجموعة العلاقات المُعطاة. بعبارة أخرى، يُحدد القيد العلائقي النطاق ومجموعة القيم المُرضية لكل قيد، ولكنه لا يُحدد كيفية توزيع القيود على المتغيرات. ويتم ذلك من خلال القيود الهيكلية. ويمكن التحقق من القيد الهيكلي بالنظر فقط إلى نطاقات القيود (متغيراتها)، مع تجاهل علاقاتها (مجموعة القيم المُرضية).

تُعتبر لغة القيود قابلة للمعالجة إذا وُجدت خوارزمية متعددة الحدود لحل جميع المسائل القائمة على هذه اللغة، أي باستخدام المجال والعلاقات المحددة فيه. ومن أمثلة لغات القيود القابلة للمعالجة لغة المجالات الثنائية والقيود الثنائية. رسميًا، يُقابل هذا القيد السماح فقط بالمجالات ذات الحجم 2 والقيود التي تكون علاقتها ثنائية . في حين أن الحقيقة الثانية تُشير إلى أن نطاقات القيود ثنائية، إلا أن هذا ليس قيدًا بنيويًا لأنه لا يمنع وضع أي قيد على أي زوج من المتغيرات. وبالمناسبة، تُصبح المسألة NP-كاملة إذا رُفع أي من هذين القيدين: إذ يُمكن للقيود الثنائية والمجالات الثلاثية التعبير عن مسألة تلوين الرسم البياني بثلاثة ألوان ، بينما يُمكن للقيود الثلاثية والمجالات الثنائية التعبير عن مسألة 3-SAT ؛ وهاتان المسألتان NP-كاملتان.

من الأمثلة على فئة قابلة للمعالجة مُعرَّفة بتقييد هيكلي، مسائل الثنائية غير الدورية. عند وجود مسألة إرضاء قيود ثنائية فقط، يحتوي الرسم البياني المرتبط بها على رأس لكل متغير وحافة لكل قيد؛ ويتم ربط رأسين إذا كانا ضمن قيد. إذا كان الرسم البياني لمسألة ما غير دوري، تُسمى المسألة نفسها غير دورية. تُعتبر مسألة الإرضاء في فئة مسائل الثنائية غير الدورية قابلة للمعالجة. هذا تقييد هيكلي لأنه لا يفرض أي حد على المجال أو على القيم المحددة التي تُرضي القيود؛ بل يُقيّد طريقة وضع القيود على المتغيرات.

على الرغم من أن القيود العلائقية والبنيوية هي الأكثر استخدامًا لاستخلاص فئات قابلة للمعالجة من حلول القيود، إلا أن هناك بعض الفئات القابلة للمعالجة التي لا يمكن تعريفها بالقيود العلائقية وحدها أو بالقيود البنيوية وحدها. فالفئة القابلة للمعالجة المُعرَّفة بدلالة تحدب الصفوف لا يمكن تعريفها بدلالة العلاقات وحدها أو بدلالة البنية وحدها، لأن تحدب الصفوف يعتمد على كلٍّ من العلاقات وترتيب المتغيرات (وبالتالي لا يمكن التحقق منه بالنظر إلى كل قيد على حدة).

تُسمى الحالة الفرعية الناتجة عن تقييد اللغة بحدود قيود محدودة بالمسألة غير المنتظمة . وتُؤخذ هذه المسائل في الاعتبار غالبًا عند التعبير عن إرضاء القيود بدلالة مسألة التماثل، كما هو موضح أدناه. وقد عُرّفت المسائل المنتظمة أيضًا في سياق مسائل التماثل؛ إذ يُمكن تعريف المسألة المنتظمة بأنها اتحاد مجموعة (قد تكون لانهائية) من المسائل غير المنتظمة. وقد تكون المسألة المنتظمة المكونة من مجموعة لانهائية من المسائل غير المنتظمة غير قابلة للحل حتى لو كانت جميع هذه المسائل غير المنتظمة قابلة للحل.

تستند بعض القيود المدروسة إلى سهولة حل مشكلة إرضاء القيود، حيث تكون جميع القيود ثنائية وتشكل شجرة على المتغيرات. هذا قيد هيكلي، إذ يمكن التحقق منه بالنظر فقط إلى نطاقات القيود، متجاهلين المجالات والعلاقات.

يستند هذا القيد إلى الرسم البياني الأولي للمسألة، وهو رسم بياني تمثل رؤوسه متغيرات المسألة، بينما تمثل حوافه وجود قيد بين متغيرين. ومع ذلك، يمكن أيضًا تحقيق قابلية الحل بفرض شرط أن يكون الرسم البياني الأولي شجرةً على المسائل التي تُعدّ إعادة صياغة للرسم البياني الأصلي.

تم الربط بين إرضاء القيود ونظرية قواعد البيانات من خلال تطابق بين مشكلة إرضاء القيود ومشكلة التحقق من وجود تماثل بين بنيتين علائقيتين. البنية العلائقية هي تمثيل رياضي لقاعدة بيانات علائقية : وهي عبارة عن مجموعة من القيم ومجموعة من العلاقات التي تربط هذه القيم. رسميًا،${\displaystyle A=(V,R_{1}^{A},\ldots ,R_{n}^{A})}$حيث كل${\displaystyle R_{i}^{A}}$هي علاقة تتجاوز${\displaystyle V}$أي مجموعة من أزواج القيم${\displaystyle V}$.

يختلف الهيكل العلائقي عن مشكلة إرضاء القيود لأن القيد عبارة عن علاقة ومجموعة من المتغيرات. كما يختلفان في طريقة استخدامهما: ففي مشكلة إرضاء القيود، تكمن المشكلة الرئيسية في إيجاد تعيين مُرضٍ؛ أما في الهيكل العلائقي، فتتمثل المشكلة الرئيسية في إيجاد إجابة للاستعلام.

مع ذلك، ترتبط مشكلة إرضاء القيود بمشكلة إثبات وجود تماثل بين بنيتين علائقيتين. التماثل هو دالة من قيم العلاقة الأولى إلى قيم العلاقة الثانية، وعند تطبيقها على جميع قيم علاقة في البنية الأولى، فإنها تحولها إلى مجموعة جزئية من العلاقة المقابلة في البنية الثانية. رسميًا،${\displaystyle h}$هو تشاكل من${\displaystyle A=(V,R_{1}^{A},\ldots ,R_{n}^{A})}$ل${\displaystyle B=(D,R_{1}^{B},\ldots ,R_{n}^{B})}$إذا كانت دالة من${\displaystyle V}$ل${\displaystyle D}$بحيث إذا${\displaystyle (x_{1},\ldots ,x_{k})\in R_{i}^{A}}$ثم${\displaystyle (h(x_{1}),\ldots ,h(x_{k}))\in R_{i}^{B}}$.

يمكن إقامة تطابق مباشر بين مسألة إرضاء القيود ومسألة التماثل. بالنسبة لمسألة إرضاء قيود معينة، يمكن بناء زوج من البنى العلائقية، الأولى تُشفّر المتغيرات وتوقيعات القيود، والثانية تُشفّر نطاقات وعلاقات القيود. يتوافق إرضاء مسألة إرضاء القيود مع إيجاد قيمة لكل متغير بحيث يؤدي استبدال قيمة في توقيع إلى جعلها صفًا في علاقة القيد. يتحقق هذا تحديدًا إذا كان هذا التقييم تماثلًا بين البنيتين العلائقيتين.

العلاقة العكسية هي عكس العلاقة الأصلية: عند وجود بنيتين علائقيتين، تُشفّر إحداهما قيم الأولى في متغيرات مسألة إرضاء القيود، بينما تُشفّر الثانية قيمها في نطاق المسألة نفسها. لكل صف في كل علاقة من البنية الأولى، يوجد قيدٌ له قيمٌ في العلاقة المقابلة من البنية الثانية. وبهذه الطريقة، يُقابل التشاكل ربط كل نطاق لكل قيد (كل صف في كل علاقة من البنية الأولى) بصف في علاقة القيد (صف في العلاقة المقابلة من البنية الثانية).

مسألة إرضاء القيود غير المنتظمة هي قيدٌ تُثبَّت فيه البنية الثانية لمسألة التماثل. بعبارة أخرى، تُعرِّف كل بنية علائقية مسألةً غير منتظمة، وهي تحديد ما إذا كانت بنية علائقية أخرى متماثلة معها. يمكن وضع قيد مماثل على البنية الأولى؛ فبالنسبة لأي بنية أولى ثابتة، تكون مسألة التماثل قابلةً للحل، لأنه لا يوجد حينها سوى عدد كثير الحدود من الدوال من البنية الأولى إلى الثانية. أما مسألة إرضاء القيود المنتظمة فهي قيدٌ اختياري على مجموعات البنى للبنية الأولى والثانية لمسألة التماثل.

بما أن مشكلة التماثل تعادل تقييم الاستعلام الاقتراني واحتواء الاستعلام الاقتراني ، فإن هاتين المشكلتين تعادلان إرضاء القيود أيضًا.

يمكن اعتبار كل قيد بمثابة جدول في قاعدة بيانات ، حيث تُفسَّر المتغيرات على أنها أسماء سمات، والعلاقة هي مجموعة السجلات في الجدول. حلول مسألة إرضاء القيود هي نتيجة ربط داخلي للجداول التي تُمثِّل قيودها؛ لذا، يمكن إعادة صياغة مسألة وجود الحلول على أنها مسألة التحقق مما إذا كانت نتيجة الربط الداخلي لعدد من الجداول غير فارغة.

يرتبط شرط كافٍ لسهولة المعالجة بإمكانية التعبير في لغة Datalog . يُعطي استعلام Datalog المنطقي قيمة منطقية لمجموعة من القيم الحرفية على أبجدية معينة، حيث تكون كل قيمة حرفية تعبيرًا من الشكل التالي:${\displaystyle L(a_{1},\ldots ,a_{n})}$ونتيجة لذلك، فإن استعلام Datalog المنطقي يعبر عن مجموعة من مجموعات القيم الحرفية، حيث يمكن اعتباره مكافئًا دلاليًا لمجموعة جميع مجموعات القيم الحرفية التي يتم تقييمها على أنها صحيحة.

من ناحية أخرى، يمكن اعتبار المسألة غير المنتظمة طريقةً للتعبير عن مجموعة مماثلة. بالنسبة لمسألة غير منتظمة معينة، تكون مجموعة العلاقات التي يمكن استخدامها في القيود ثابتة؛ ونتيجةً لذلك، يمكن إعطاء أسماء فريدة.${\displaystyle R_{1},\ldots ,R_{n}}$لهم. ويمكن كتابة مثال على هذه المشكلة غير المنتظمة كمجموعة من القيم الحرفية على النحو التالي:${\displaystyle R_{i}(x_{1},\ldots ,x_{n})}$من بين هذه الحالات/مجموعات المتغيرات، بعضها قابل للتحقيق وبعضها الآخر غير قابل للتحقيق؛ ويعتمد تحديد قابلية تحقيق مجموعة من المتغيرات على العلاقات التي تحددها المسألة غير المنتظمة. وبالعكس، تحدد المسألة غير المنتظمة أي مجموعات المتغيرات تمثل حالات قابلة للتحقيق وأيها تمثل حالات غير قابلة للتحقيق. وبمجرد تسمية العلاقات، تعبر المسألة غير المنتظمة عن مجموعة من مجموعات المتغيرات: تلك المرتبطة بالحالات القابلة للتحقيق (أو غير القابلة للتحقيق).

يُعدّ شرطًا كافيًا لقابلية حلّ مشكلة غير منتظمة أن تكون قابلة للحلّ إذا أمكن التعبير عن مجموعة حالاتها غير القابلة للحل باستخدام استعلام منطقي في داتالوج. بعبارة أخرى، إذا كانت مجموعة مجموعات القيم الحرفية التي تُمثّل حالات غير قابلة للحل في المشكلة غير المنتظمة هي نفسها مجموعة مجموعات القيم الحرفية التي تُحقّق استعلامًا منطقيًا في داتالوج، فإنّ المشكلة غير المنتظمة تكون قابلة للحلّ.

يمكن أحيانًا إثبات قابلية الحل بفرض شكل من أشكال الاتساق المحلي ، ثم التحقق من وجود مجال فارغ أو علاقة قيد فارغة. هذه خوارزمية صحيحة عمومًا، ولكنها غير مكتملة، لعدم قابلية الحل: فقد تكون المسألة غير قابلة للحل حتى في حال عدم وجود مجال فارغ أو علاقة قيد فارغة. بالنسبة لبعض أشكال الاتساق المحلي، قد تتطلب هذه الخوارزمية وقتًا أُسّيًا. مع ذلك، بالنسبة لبعض المسائل وبعض أنواع الاتساق المحلي، تكون هذه الخوارزمية صحيحة وتعمل في وقت متعدد الحدود.

تستغل الشروط التالية الرسم البياني الأولي للمسألة، والذي يحتوي على رأس لكل متغير وحافة بين عقدتين إذا كانت المتغيرات المقابلة ضمن قيد. فيما يلي شروط على مسائل إرضاء القيود الثنائية حيث يكون فرض الاتساق المحلي قابلاً للتطبيق ويسمح بإثبات قابلية الإرضاء:

1. فرض اتساق القوس، إذا كان الرسم البياني الأولي غير دوري؛
2. فرض اتساق القوس الاتجاهي لترتيب المتغيرات الذي يجعل الرسم البياني المرتب للقيود له عرض 1 (يوجد مثل هذا الترتيب إذا وفقط إذا كان الرسم البياني الأولي شجرة، ولكن ليس كل ترتيبات الشجرة تولد عرضًا 1)؛
3. فرض اتساق قوي للمسار الاتجاهي لترتيب المتغيرات الذي يجعل الرسم البياني الأولي ذو عرض مستحث 2.

ينطبق شرطٌ يُوسّع الشرط الأخير على مسائل إرضاء القيود غير الثنائية. أي أنه بالنسبة لجميع المسائل التي يوجد لها ترتيب يجعل الرسم البياني الأولي ذو العرض المُستحث محدودًا بثابت i، فإن فرض الاتساق الاتجاهي القوي لـ i يكون قابلاً للمعالجة ويسمح بإثبات قابلية الإرضاء.

يمكن النظر إلى مسائل إرضاء القيود المكونة من قيود ثنائية فقط على أنها رسوم بيانية ، حيث تمثل الرؤوس المتغيرات، وتمثل الحواف وجود قيد بين متغيرين. يُطلق على هذا الرسم البياني اسم رسم غايفمان البياني أو الرسم البياني الأولي للقيود (أو ببساطة الرسم البياني الأولي) للمسألة.

إذا كان الرسم البياني الأولي لمسألة ما غير دوري، فإن إثبات قابلية المسألة للحل يصبح مسألة قابلة للمعالجة. هذا قيد هيكلي، إذ يمكن التحقق منه بالنظر فقط إلى نطاقات القيود، متجاهلين علاقاتها ومجالها. الرسم البياني غير الدوري هو غابة ، ولكن يُفترض عادةً وجود اتصال ؛ ونتيجة لذلك، فإن الشرط الذي يُؤخذ في الاعتبار عادةً هو أن الرسوم البيانية الأولية أشجار .

تستغل طرق التفكيك هذه الخاصية لمسائل إرضاء القيود الشجرية ، حيث تحول المسائل إلى مسائل مكافئة تحتوي فقط على قيود ثنائية مرتبة على شكل شجرة. تتوافق متغيرات هذه المسائل مع مجموعات متغيرات المسألة الأصلية؛ ويُحدد نطاق كل متغير من خلال النظر في بعض قيود المسألة الأصلية التي يندرج نطاقها ضمن مجموعة المتغيرات الأصلية المناظرة؛ وتمثل قيود هذه المسائل الجديدة تساوي المتغيرات الموجودة في مجموعتين.

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

يمكن "محاكاة" علاقة غير موجودة في لغة القيود باستخدام قيود تستخدم العلاقات الموجودة في تلك اللغة. على وجه الخصوص، يمكن إنشاء علاقة جديدة بوضع مجموعة من القيود واستخدام بعض متغيراتها فقط. إذا كانت جميع القيود الأخرى تستخدم هذه المتغيرات فقط، فإن هذه المجموعة من القيود تجبر هذه المتغيرات على أخذ قيم محددة فقط، مما يحاكي عمليًا علاقة جديدة.

تُعرّف كل مسألة إرضاء قيود، ومجموعة فرعية من متغيراتها، علاقةً تتألف من جميع أزواج قيم المتغيرات التي يمكن تعميمها على المتغيرات الأخرى لتكوين حل. ومن الناحية التقنية، تُستنتج هذه العلاقة بإسقاط العلاقة التي تمثل الحلول كصفوف على المتغيرات المدروسة.

تعتمد الأداة العالمية على ملاحظة أن كل علاقة تحتوي على${\displaystyle k}$يمكن تعريف الصفوف من خلال إسقاط علاقة تحتوي على جميع الأعمدة الممكنة من${\displaystyle k}$عناصر من المجال. على سبيل المثال، توضح الجداول التالية مثل هذا الإسقاط:

abcdefghbd --------------- --- 1 1 1 1 0 0 0 0 -> 1 1 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 1 0 0 0

إذا كان الجدول الموجود على اليسار يمثل مجموعة حلول مسألة إرضاء القيود، فإن متغيراتها${\displaystyle b}$و${\displaystyle d}$تُقيّد القيم بقيم الجدول الموجود على اليمين. ونتيجةً لذلك، يمكن استخدام مسألة إرضاء القيود لوضع قيد تكون علاقته بالجدول الموجود على اليمين، وهو ما قد لا يكون موجودًا في لغة القيود.

نتيجةً لذلك، إذا كانت مسألة إرضاء القيود تحتوي على الجدول الموجود على اليسار كمجموعة حلول، فيمكن التعبير عن كل علاقة بإسقاطها على مجموعة مناسبة من المتغيرات. إحدى طرق محاولة الحصول على هذا الجدول كمجموعة حلول هي وضع كل قيد ممكن لا تنتهكه الحلول المطلوبة.

على سبيل المثال، إذا كانت اللغة تحتوي على العلاقة الثنائية التي تمثل الفصل المنطقي (علاقة تحتوي على جميع الصفوف المكونة من عنصرين والتي تحتوي على الأقل على 1)، فسيتم وضع هذه العلاقة كقيد على${\displaystyle a}$و${\displaystyle b}$لأن قيمها في الجدول أعلاه هي${\displaystyle (1,1)}$،${\displaystyle (1,1)}$مرة أخرى، و${\displaystyle (1,0)}$بما أن جميع هذه القيم تُحقق الشرط، يتم وضع الشرط. من ناحية أخرى، لا يتم وضع شرط بهذه العلاقة على${\displaystyle b}$و${\displaystyle d}$بما أن تقييد الجدول أعلاه بهذين المتغيرين يحتوي${\displaystyle (0,0)}$كصف ثالث، وهذا التقييم ينتهك هذا القيد.

أداة النظام العالمية${\displaystyle k}$هي مسألة إرضاء القيود التي تتضمن جميع القيود التي يمكن وضعها للحصول على الجدول أعلاه. تشمل حلول الأداة الشاملة صفوف هذا الجدول، ولكنها قد تحتوي على صفوف أخرى. إذا كانت الحلول هي صفوف الجدول تحديدًا، فيمكن التعبير عن كل علاقة بإسقاطها على مجموعة فرعية من المتغيرات. مع ذلك، حتى لو تضمنت الحلول صفوفًا أخرى، فإنه لا يزال من الممكن التعبير عن بعض العلاقات. من خصائص الأداة الشاملة أنها قادرة على التعبير، بالإسقاط، عن كل علاقة يمكن التعبير عنها بالإسقاط من مسألة إرضاء قيود عشوائية مبنية على نفس اللغة. بتعبير أدق، الأداة الشاملة من الرتبة${\displaystyle k}$يعبّر عن جميع علاقات${\displaystyle k}$صفوف يمكن التعبير عنها بلغة القيود.

بالنظر إلى علاقة محددة، يمكن التحقق من إمكانية التعبير عنها في اللغة من خلال النظر في قائمة عشوائية من المتغيرات التي تشكل أعمدتها في الجدول أعلاه (الحلول "المثالية" للأداة الشاملة) تلك العلاقة. يمكن التعبير عن العلاقة في اللغة إذا وفقط إذا تطابقت حلول الأداة الشاملة مع العلاقة عند إسقاطها على قائمة المتغيرات هذه. بعبارة أخرى، يمكن التحقق من إمكانية التعبير عن طريق اختيار متغيرات "كما لو" كانت حلول الأداة الشاملة كما في الجدول، ثم التحقق مما إذا كان تقييد الحلول "الحقيقية" هو نفسه تقييد العلاقة. في المثال أعلاه، يمكن التحقق من إمكانية التعبير عن العلاقة في الجدول على اليمين من خلال النظر فيما إذا كانت حلول الأداة الشاملة، عند تقييدها بالمتغيرات${\displaystyle b}$و${\displaystyle d}$، هي بالضبط صفوف هذا الجدول.

يمكن التعبير عن شرط ضروري لإمكانية المعالجة باستخدام أداة شاملة. ويمكن تلخيص حلول هذه الأداة في جدول كما يلي:

abcdefgh --------------- 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 0 (حلول موجودة بحكم التعريف) 1 0 1 0 1 0 1 0 --------------- .... 1 0 0 1 1 1 0 0 (حلول أخرى ممكنة) ....

يتكون هذا الجدول من جزأين. يحتوي الجزء الأول على الحلول الموجودة بحكم تعريف هذه المسألة؛ أما الجزء الثاني (الذي قد يكون فارغًا) فيحتوي على جميع الحلول الأخرى. وبما أن أعمدة الجدول مرتبطة بحكم تعريفها بالحلول الممكنة${\displaystyle k}$- مجموعات من قيم المجال، يمكن اعتبار كل حل دالة من${\displaystyle k}$- مجموعة من العناصر إلى عنصر واحد.

يمكن حساب الدالة الموافقة للحل من الجزء الأول من الجدول أعلاه والحل نفسه. على سبيل المثال، بالنسبة للحل الأخير المحدد في الجدول، يمكن تحديد هذه الدالة باستخدام عدد من الوسائط.${\displaystyle 1,0,1}$على النحو التالي: أولاً، هذه القيم الثلاث هي الجزء الأول من الصف "ج" في الجدول؛ قيمة الدالة هي قيمة الحل في نفس العمود، أي 0.

من الشروط الضرورية لإمكانية المعالجة وجود حل لأداة شاملة من رتبة معينة تنتمي إلى فئات معينة من الدوال. إلا أن هذه النتيجة لا تنطبق إلا على اللغات المختزلة، والتي سيتم تعريفها لاحقًا.

تُستخدم دوال الدمج لتقليل حجم نطاق لغات القيود. تُعرَّف دالة الدمج بتقسيم النطاق وعنصر تمثيلي لكل مجموعة في هذا التقسيم. تربط دالة الدمج جميع عناصر مجموعة في التقسيم بالعنصر التمثيلي لتلك المجموعة. ولكي تكون هذه الدالة دالة دمج، يجب أن يؤدي تطبيقها على جميع عناصر صف في علاقة ما في اللغة إلى إنتاج صف آخر في تلك العلاقة. يُفترض أن يحتوي التقسيم على مجموعة واحدة على الأقل بحجم أكبر من واحد.

بصورة رسمية، بالنظر إلى التقسيم${\displaystyle D_{1},\ldots ,D_{n}}$من المجال${\displaystyle D}$إذا احتوت دالة الضغط على مجموعة واحدة على الأقل بحجم أكبر من واحد، فهي دالة${\displaystyle s:D\rightarrow D}$بحيث${\displaystyle s(x)=s(y)}$لكل${\displaystyle x,y}$في نفس القسم، ولكل صف${\displaystyle \langle x_{1},\ldots ,x_{n}\rangle \in R}$، وهو يحمل${\displaystyle \langle s(x_{1}),\ldots ,s(x_{n})\rangle \in R}$.

في مسائل القيود التي تتضمن لغة قيود تحتوي على دالة ضغط، يمكن تقليص نطاق اللغة باستخدام هذه الدالة. في الواقع، يمكن استبدال كل عنصر في مجموعة ضمن التقسيم بنتيجة تطبيق دالة الضغط عليه، حيث تضمن هذه النتيجة استيفاء جميع القيود التي كان يستوفيها العنصر على الأقل. ونتيجة لذلك، يمكن حذف جميع العناصر غير التمثيلية من لغة القيود.

تُسمى لغات القيود التي لا توجد لها دالة ضغط باللغات المختزلة؛ وبشكل مكافئ، هذه هي اللغات التي تم تطبيق جميع عمليات الاختزال عليها عبر دوال الضغط.

ينطبق الشرط الضروري لقابلية المعالجة القائمة على الأداة الشاملة على اللغات المختزلة. وتكون هذه اللغة قابلة للمعالجة إذا كان للأداة الشاملة حل، عند النظر إليه كدالة بالطريقة المحددة أعلاه، يكون إما دالة ثابتة، أو دالة أغلبية، أو دالة ثنائية متطابقة، أو دالة خطية، أو إسقاطًا جزئيًا.