مشكلة إرضاء القيود

📅 آخر تحديث: ٢٦ يوليو ٢٠٢٦
✍️ نُشر في: ٢٦ يوليو ٢٠٢٦
📷 يحتوي على 15 صور
الموسوعة الحرة

تُعرَّف مسائل إرضاء القيود ( CSPs ) بأنها مسائل رياضية تُحدد كمجموعة من الكائنات التي يجب أن تُحقق حالتها عددًا من القيود أو المحددات . تُمثل مسائل إرضاء القيود الكيانات في المسألة كمجموعة متجانسة من القيود المحدودة على المتغيرات ، ويتم حلها باستخدام طرق إرضاء القيود . تُعد مسائل إرضاء القيود موضوعًا للبحث في كلٍ من الذكاء الاصطناعي وبحوث العمليات ، نظرًا لأن انتظام صياغتها يوفر أساسًا مشتركًا لتحليل وحل مسائل من عائلات عديدة تبدو غير مترابطة. غالبًا ما تُظهر مسائل إرضاء القيود تعقيدًا عاليًا ، مما يتطلب مزيجًا من الطرق الاستدلالية وطرق البحث التوافقي لحلها في وقت معقول. يُعد برمجة القيود (CP) مجالًا بحثيًا يُركز تحديدًا على معالجة هذا النوع من المسائل. [ 1 ] [ 2 ] بالإضافة إلى ذلك، تُعد مسألة الإرضاء المنطقي (SAT)، والإرضاء المعياري للنظريات (SMT)، والبرمجة الخطية المختلطة (MIP)، وبرمجة مجموعة الإجابات (ASP) جميعها مجالات بحثية تُركز على حل أشكال معينة من مسألة إرضاء القيود.

تتضمن أمثلة المشكلات التي يمكن نمذجتها كمشكلة إرضاء القيود ما يلي:

غالبًا ما تُرفق هذه البرامج بدروس تعليمية حول خوارزميات حل مسائل القيود (CP) ، وASP، وBoolean SAT، وSMT. في الحالة العامة، قد تكون مسائل القيود أكثر تعقيدًا، وقد لا يُمكن التعبير عنها في بعض هذه الأنظمة الأبسط. تشمل الأمثلة العملية التخطيط الآلي [ 6 ] [ 7 ] ، وإزالة الغموض المعجمي [ 8 ] [ 9 ] ، وعلم الموسيقى [ 10 ] ، وتكوين المنتجات [ 11 ] ، وتخصيص الموارد [ 12 ] .

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

التعريف الرسمي

بشكل رسمي، تُعرَّف مشكلة إرضاء القيود على أنها ثلاثية⟨X،د،ج⟩{\displaystyle \langle X,D,C\rangle }، حيث [ 13 ]

  • X={X1،...،Xن}{\displaystyle X=\{X_{1},\ldots ,X_{n}\}}هي مجموعة من المتغيرات،
  • د={د1،...،دن}{\displaystyle D=\{D_{1},\ldots ,D_{n}\}}هي مجموعة من نطاقات القيم الخاصة بكل منها، و
  • ج={ج1،...،جم}{\displaystyle C=\{C_{1},\ldots ,C_{m}\}}هي مجموعة من القيود.

كل متغيرXأنا{\displaystyle X_{i}}يمكن أن تأخذ القيم في المجال غير الفارغدأنا{\displaystyle D_{i}}كل قيدجج∈ج{\displaystyle C_{j}\in C}وهو بدوره زوج⟨تج،Rج⟩{\displaystyle \langle t_{j},R_{j}\rangle }، أينتج⊆{1،2،...،ن}{\displaystyle t_{j}\subseteq \{1,2,\ldots ,n\}}هي مجموعة منك{\displaystyle k}المؤشرات وRج{\displaystyle R_{j}}هوك{\displaystyle k}العلاقة -ary على حاصل الضرب المقابل للمجالات×أنا∈تجدأنا{\displaystyle \times _{i\in t_{j}}D_{i}}حيث يتم حساب الناتج باستخدام المؤشرات بترتيب تصاعدي. تقييم المتغيرات هو دالة من مجموعة فرعية من المتغيرات إلى مجموعة معينة من القيم في المجموعة الفرعية المقابلة من المجالات. التقييمv{\displaystyle v}يفي بشرط معين⟨تج،Rج⟩{\displaystyle \langle t_{j},R_{j}\rangle }إذا كانت القيم المخصصة للمتغيراتتج{\displaystyle t_{j}}تحقيق العلاقةRج{\displaystyle R_{j}}.

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

حل

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

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

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

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

الجوانب النظرية

التعقيد الحسابي

تُدرس مسائل إرضاء القيود (CSPs) أيضًا في نظرية التعقيد الحسابي ، ونظرية النماذج المحدودة ، والجبر الشامل . وقد تبيّن أن الأسئلة المتعلقة بتعقيد مسائل إرضاء القيود تُترجم إلى أسئلة جبرية شاملة مهمة حول الجبر الأساسي. يُعرف هذا النهج بالنهج الجبري لمسائل إرضاء القيود. [ 15 ]

بما أن كل مسألة قرار حسابية تُكافئ مسألة إرضاء القيود (CSP) ذات قالب لانهائي في زمن متعدد الحدود، [ 16 ] فإن مسائل إرضاء القيود العامة يمكن أن تتمتع بتعقيد عشوائي. وعلى وجه الخصوص، توجد أيضًا مسائل إرضاء قيود ضمن فئة المسائل الوسيطة من نوع NP ، والتي أثبت لادنر وجودها ، بافتراض أن P ≠ NP .

مع ذلك، فإن فئة كبيرة من مسائل إرضاء القيود (CSPs) الناشئة عن التطبيقات الطبيعية تُحقق ثنائية التعقيد، ما يعني أن كل مسألة إرضاء قيود ضمن هذه الفئة إما أن تكون ضمن فئة P أو NP-كاملة . وبالتالي، تُوفر هذه المسائل إحدى أكبر المجموعات الفرعية المعروفة من NP التي تتجنب المسائل الوسيطة NP- . وقد أثبت شيفر ثنائية التعقيد لأول مرة لمسائل إرضاء القيود البوليانية، أي مسائل إرضاء القيود على نطاق مكون من عنصرين حيث تكون جميع العلاقات المتاحة عبارة عن عوامل بوليانية . وقد عُممت هذه النتيجة لفئات مختلفة من مسائل إرضاء القيود، ولا سيما لجميع مسائل إرضاء القيود على نطاقات محدودة. وقد صاغ توماس فيدر وموشيه فاردي [ 17 ] فرضية ثنائية النطاق المحدود هذه لأول مرة ، وأثبتها بشكل مستقل أندريه بولاتوف [ 18 ] وديمتري جوك في عام 2017 [ 19 ].

الفئات الأخرى التي تم تأكيد وجود ثنائية في تعقيدها هي

معظم فئات مسائل إرضاء القيود المعروفة بأنها قابلة للمعالجة هي تلك التي يكون فيها الرسم البياني الفائق للقيود ذا عرض شجري محدود ، [ 27 ] أو التي تكون فيها القيود ذات شكل عشوائي ولكن توجد تعددات أشكال غير تافهة معادلة لمجموعة علاقات القيود. [ 28 ]

تم صياغة تخمين ثنائي المجال اللانهائي [ 29 ] لجميع CSPs المختزلات للهياكل المتجانسة المحدودة بشكل نهائي، ينص على أن CSP لمثل هذا الهيكل موجود في P إذا وفقط إذا كان استنساخ تعدد الأشكال الخاص به غير تافه من الناحية المعادلة، و NP-hard خلاف ذلك.

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

يمكن اعتبار كل مسألة إرضاء القيود (CSP) أيضًا مسألة احتواء استعلام اقتراني . [ 31 ]

مشاكل في الوظيفة

توجد حالة مشابهة بين الفئتين الوظيفيتين FP و #P . وبتعميم لنظرية لادنر ، توجد أيضًا مسائل ليست كاملة في FP ولا في #P طالما أن FP ≠ #P. وكما هو الحال في مسألة القرار، تُعرَّف المسألة في #CSP بمجموعة من العلاقات. تأخذ كل مسألة صيغة منطقية كمدخل، وتتمثل المهمة في حساب عدد التعيينات المُرضية. ويمكن تعميم ذلك باستخدام أحجام نطاق أكبر، وإسناد وزن لكل تعيين مُرضٍ، وحساب مجموع هذه الأوزان. ومن المعروف أن أي مسألة #CSP مُرَكَّبة وموزونة تقع إما في FP أو في #P-hard. [ 32 ]

المتغيرات

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

موفري خدمات السحابة الديناميكيين

تُعدّ مسائل إرضاء القيود الديناميكية ( DCSPs ) [ 34 ] مفيدةً عندما تتغير الصيغة الأصلية للمسألة، عادةً بسبب تطور مجموعة القيود التي يجب مراعاتها نتيجةً لتغير البيئة. [ 35 ] تُعتبر مسائل إرضاء القيود الديناميكية سلسلةً من مسائل إرضاء القيود الثابتة، حيث تُمثّل كل مسألة تحويلاً للمسألة السابقة، يُمكن من خلاله إضافة متغيرات وقيود (تقييد) أو إزالتها (تخفيف). يُمكن استخدام المعلومات المُستقاة من الصيغ الأولية للمسألة لتحسين الصيغ اللاحقة. يُمكن تصنيف طريقة الحل وفقًا لكيفية نقل المعلومات.

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

مزودو خدمات الاتصالات المرنة

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

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

مزودو خدمات الاتصالات اللامركزيون

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

انظر أيضاً

مراجع

  1. ↑ ليكوتر، كريستوف (2013). شبكات القيود: التقنيات والخوارزميات . وايلي. ص  26. ISBN 978-1-118-61791-5.
  2. ↑ "القيود - بما في ذلك خيار النشر المفتوح" . springer.com . تم الاطلاع عليه بتاريخ 2019-10-03 .
  3. ↑ شاندرا، ساتيش؛ غوردون، كولين س.؛ جانين، جان بابتيست؛ شليزنجر، كول؛ سريدهاران، مانو؛ تيب، فرانك؛ تشوي، يونغيل (2016). "استنتاج النوع للتجميع الثابت لجافا سكريبت" (ملف PDF) . وقائع مؤتمر ACM SIGPLAN الدولي لعام 2016 حول البرمجة الكائنية والأنظمة واللغات والتطبيقات . الصفحات 410-429 . doi : 10.1145/2983990.2984017 . ISBN  978-1-4503-4444-9.
  4. ↑ جيم، تريفور، وجينس بالسبيرج. " استدلال النوع في أنظمة الأنواع المتكررة مع التنميط الفرعي ." متاح على صفحة الويب الخاصة بالمؤلفين (1999).
  5. ↑ فرحي، إدوارد؛ آرام دبليو هارو (2016). "التفوق الكمي من خلال خوارزمية التحسين التقريبي الكمي". arXiv : 1602.07674 [ quant-ph ].
  6. ↑ مالك غلاب؛ دانا ناو؛ باولو ترافيرسو (21 مايو 2004). التخطيط الآلي: النظرية والتطبيق . إلسيفير. ص 1–. ISBN  978-0-08-049051-9.
  7. ↑ إرضاء القيود المرنة الديناميكية وتطبيقها على تخطيط الذكاء الاصطناعي ، مؤرشف في 2009-02-06 في Wayback Machine إيان ميغيل – شرائح.
  8. ↑ ديمتريو، جورج سي. " إزالة الغموض المعجمي باستخدام معالجة القيود في لغة برولوج (CHIP) ". وقائع المؤتمر السادس للفرع الأوروبي لرابطة اللغويات الحاسوبية. رابطة اللغويات الحاسوبية، 1993.
  9. ↑ ماكدونالد، ماري إيلين سي، ومارك إس. سايدنبرغ. " تفسيرات إرضاء القيود لفهم المفردات والجمل ". دليل علم اللغة النفسي (الطبعة الثانية). 2006. 581-611.
  10. ↑ ماوريسيو تورو، كارلوس أغون، كاميلو رويدا، جيرارد أساياغ. " جيليسب: إطار عمل لتمثيل مشاكل إرضاء القيود الموسيقية واستراتيجيات البحث ". مجلة تكنولوجيا المعلومات النظرية والتطبيقية 86 (2). 2016. 327-331.
  11. ↑ تطبيق نهج إرضاء القيود لحل مشاكل تكوين المنتج باستخدام قواعد التكوين القائمة على العددية ، دونغ يانغ ومينغ دونغ، مجلة التصنيع الذكي، المجلد 24، الصفحات 99-111 (2013)
  12. ↑ مودي، براغنيش جاي، وآخرون. " نهج ديناميكي موزع لإرضاء القيود لتخصيص الموارد ". المؤتمر الدولي حول مبادئ وممارسات البرمجة المقيدة. سبرينغر، برلين، هايدلبرغ، 2001.
  13. ↑ ستيوارت جوناثان راسل؛ بيتر نورفيج (2010). الذكاء الاصطناعي: منهج حديث . برنتيس هول. ص. الفصل 6. ISBN  9780136042594.
  14. ↑ ميلانو، ميكايلا ؛ فان هينتيريك، باسكال، محرران. (2011). التحسين الهجين : عشر سنوات من مؤتمر CPAIOR . المؤتمر الدولي حول دمج تقنيات الذكاء الاصطناعي وبحوث العمليات في البرمجة المقيدة لمسائل التحسين التوافقي. نيويورك: سبرينغر. ISBN  9781441916440. OCLC 695387020 . 
  15. ↑ بارتو، ليبور؛ برادي، زاراثوسترا؛ بولاتوف، أندريه؛ كوزيك، مارسين؛ جوك، ديمتري (15-05-2024). "توحيد المناهج الجبرية الثلاثة لمسألة إرضاء القيود عبر جبر تايلور الأدنى". ثيوريتكس . 3 11361. arXiv : 2104.11808 . doi : 10.46298/theoretics.24.14 . ISSN 2751-4838 . 
  16. ↑ بوديرسكي، مانويل؛ غروهي، مارتن (2008). "عدم الثنائية في تعقيد إرضاء القيود" . في: أسيتو، لوكا؛ دامغارد، إيفان؛ غولدبيرغ، ليزلي آن؛ هالدورسون، ماغنوس م.؛ إنغولفسدوتير، آنا؛ والوكيفيتش، إيغور (محررون). الأوتوماتا واللغات والبرمجة . سلسلة محاضرات في علوم الحاسوب. المجلد 5126. برلين، هايدلبرغ: سبرينغر. الصفحات 184-196 . doi : 10.1007/978-3-540-70583-3_16 . ISBN   978-3-540-70583-3.
  17. ↑ فيدر، توماس؛ فاردي، موشيه ي. (1998). "البنية الحسابية لـ SNP أحادي الرتابة وإرضاء القيود: دراسة من خلال داتالوج ونظرية الزمر" . مجلة SIAM للحوسبة . 28 (1): 57-104 . doi : 10.1137/S0097539794266766 . ISSN 0097-5397 . 
  18. ↑ بولاتوف، أندريه (2017). "نظرية ثنائية لمسائل إرضاء القيود غير المنتظمة". وقائع الندوة السنوية الثامنة والخمسين لمؤسسة مهندسي الكهرباء والإلكترونيات حول أسس علوم الحاسوب، FOCS 2017. جمعية مهندسي الكهرباء والإلكترونيات. الصفحات 319-330 . arXiv : 1703.03021 . doi : 10.1109/FOCS.2017.37 . ISBN  978-1-5386-3464-6.
  19. ↑ زوك، ديمتري (2020). "برهان على تخمين ثنائية CSP". مجلة ACM . 67 (5): 1-78 . arXiv : 1704.01914 . doi : 10.1145/3402029 .
  20. ↑ بوديرسكي، مانويل؛ كارا، يان (2010-02-08). "تعقيد مسائل إرضاء القيود الزمنية" . مجلة ACM . 57 (2): 9:1–9:41. doi : 10.1145/1667053.1667058 . ISSN 0004-5411 . 
  21. ↑ بوديرسكي، مانويل؛ بينسكر، مايكل (2011). "نظرية شيفر للرسوم البيانية". وقائع الندوة السنوية الثالثة والأربعين حول نظرية الحوسبة (STOC '11) . رابطة آلات الحوسبة . الصفحات 655-664 . arXiv : 1011.2894 . doi : 10.1145/1993636.1993724 . ISBN  978-1-4503-0691-1. S2CID 47097319 . 
  22. ↑ بوديرسكي، مانويل؛ جونسون، بيتر؛ فام، ترونغ فان (2017-08-02). "تعقيد مسائل إرضاء قيود علم الوراثة" . مجلة ACM للمعاملات في منطق الحاسوب . 18 (3): 23:1–23:42. arXiv : 1503.07310 . doi : 10.1145/3105907 . ISSN 1529-3785 . 
  23. ^ كومباتشر، مايكل. فام، ترونج فان (2017). “ثنائية التعقيد لرضا القيد”. الندوة الرابعة والثلاثون حول الجوانب النظرية لعلوم الكمبيوتر (STACS 2017) . إجراءات لايبنيز الدولية في المعلوماتية. المجلد. 66. شلوس داغستوهل – مركز لايبنيز للمعلوماتية. ص 47: 1-47: 12. دوى : 10.4230/LIPIcs.STACS.2017.47 . رقم ISBN   978-3-95977-028-6.
  24. ↑ بوديرسكي، مانويل؛ مارتن، بارنابي؛ بينسكر، مايكل؛ بونغراتش، أندراس (يناير 2019). "مسائل إرضاء القيود لاختزالات الرسوم البيانية المتجانسة" . مجلة SIAM للحوسبة . 48 (4): 1224-1264 . arXiv : 1602.05819 . doi : 10.1137/16M1082974 . ISSN 0097-5397 . 
  25. ↑ بوديرسكي، مانويل؛ موتيه، أنطوان (2018-05-20)، "ثنائية للاختزالات من الدرجة الأولى للهياكل الأحادية"، الأساليب المنطقية في علوم الحاسوب ، 14 (2) 3264، arXiv : 1601.04520 ، doi : 10.23638/LMCS-14(2:13)2018
  26. ↑ بوديرسكي، مانويل؛ مادلين، فلورنت؛ موتيه، أنطوان (9 يوليو 2018). "برهان جبري شامل لثنائية التعقيد لـ Monotone Monadic SNP" . وقائع الندوة السنوية الثالثة والثلاثين لجمعية ACM/IEEE حول المنطق في علوم الحاسوب . LICS '18. نيويورك، نيويورك، الولايات المتحدة الأمريكية: جمعية آلات الحوسبة. الصفحات 105-114 . arXiv : 1802.03255 . doi : 10.1145/3209108.3209156 . ISBN  978-1-4503-5583-4.
  27. ↑ بارتو، ليبور؛ كوزيك، مارسين (2014-01-01). "مسائل إرضاء القيود القابلة للحل باستخدام طرق الاتساق المحلي" . مجلة ACM . 61 (1): 3:1–3:19. doi : 10.1145/2556646 . ISSN 0004-5411 . 
  28. ↑ بوديرسكي، مانويل (2021). تعقيد إرضاء القيود في المجال اللانهائي . سلسلة محاضرات في المنطق. كامبريدج: مطبعة جامعة كامبريدج. ISBN 978-1-107-04284-1.
  29. ^ بوديرسكي، مانويل. بينسكر، مايكل. بونجراتش, أندراس (مارس 2021). “التماثل الإسقاطي للاستنساخ” . مجلة المنطق الرمزي . 86 (1): 148– 161. أرخايف : 1409.4601 . دوى : 10.1017/jsl.2019.23 . اتش دي ال : 2437/268560 . ISSN 0022-4812 . 
  30. ↑ بينسكر، مايكل (2022-03-31). "التحديات الحالية في إرضاء القيود في المجال اللانهائي: معضلات الأغنام اللانهائية". arXiv : 2203.17182 [ cs.LO ].
  31. ↑ كولايتيس، فوكيون ج.؛ فاردي، موشيه ي. (2000). "احتواء الاستعلام الاقتراني وإرضاء القيود" . مجلة علوم الحاسوب والنظم . 61 (2): 302-332 . doi : 10.1006/jcss.2000.1713 .
  32. ↑ كاي، جين-يي؛ تشين، شي (2012). "تعقيد حساب مسائل إرضاء القيود ذات الأوزان المركبة". وقائع الندوة السنوية الرابعة والأربعين لجمعية آلات الحوسبة حول نظرية الحوسبة (STOC '12) . الصفحات 909-920 . arXiv : 1111.2384 . doi : 10.1145/2213977.2214059 . ISBN  978-1-4503-1245-5. S2CID 53245129 . 
  33. ↑ ميغيل، إيان (يوليو 2001). حل القيود المرنة الديناميكية وتطبيقها على تخطيط الذكاء الاصطناعي (أطروحة دكتوراه). كلية المعلوماتية، جامعة إدنبرة . CiteSeerX 10.1.1.9.6733 . hdl : 1842/326 . 
  34. ↑ Dechter, R. and Dechter, A., Belief Maintenance in Dynamic Constraint Networks Archived 2012-11-17 at the Wayback Machine In Proc. of AAAI-88, 37–42.
  35. ↑ إعادة استخدام الحلول في مسائل إرضاء القيود الديناميكية ، توماس شيكس
  36. ↑ دافي، ك. ر.؛ ليث، د. ج. (أغسطس 2013)، "حل القيود اللامركزي"، معاملات IEEE/ACM في الشبكات، 21(4) ، المجلد 21، الصفحات 1298-1308 ، arXiv : 1103.3240 ، doi : 10.1109/TNET.2012.2222923 ، S2CID 11504393   

للمزيد من القراءة