2- الرضا

وصف كروم (1967) إجراء القرار متعدد الحدود التالي لحل حالات الرضا من الدرجة 2. ^{[ 3 ]}

لنفترض أن حالة إرضاء من الدرجة الثانية تحتوي على عبارتين تستخدمان نفس المتغير x ، ولكن x منفي في إحدى العبارتين وليس في الأخرى. عندئذٍ، يمكن دمج العبارتين لإنتاج عبارة ثالثة، تحتوي على المتغيرين الآخرين الموجودين في العبارتين؛ ويجب أن تتحقق هذه العبارة الثالثة أيضًا كلما تحققت العبارتان الأوليان. يُسمى هذا بالحل . على سبيل المثال، يمكننا دمج العبارتين${\displaystyle (a\lor b)}$و${\displaystyle (\lnot b\lor \lnot c)}$بهذه الطريقة يتم إنتاج العبارة${\displaystyle (a\lor \lnot c)}$من حيث الصيغة الضمنية لصيغة 2-CNF، فإن هذه القاعدة تعني إيجاد نتيجتين.${\displaystyle \lnot a\Rightarrow b}$و${\displaystyle b\Rightarrow \lnot c}$واستنتاجًا عن طريق التعدي ، استلزامًا ثالثًا${\displaystyle \lnot a\Rightarrow \lnot c}$[ ^{3 ]​}

يكتب كروم أن الصيغة تكون متسقة إذا لم يتمكن التطبيق المتكرر لقاعدة الاستدلال هذه من توليد كلا البندين.${\displaystyle (x\lor x)}$و${\displaystyle (\lnot x\lor \lnot x)}$، لأي متغير${\displaystyle x}$كما يثبت، فإن صيغة 2-CNF تكون قابلة للتحقيق إذا وفقط إذا كانت متسقة. لأنه إذا لم تكن الصيغة متسقة، فلا يمكن تحقيق كلا البندين.${\displaystyle (x\lor x)}$و${\displaystyle (\lnot x\lor \lnot x)}$في آن واحد. وإذا كان ذلك متسقًا، فيمكن توسيع الصيغة بإضافة بند واحد بشكل متكرر على النحو التالي:${\displaystyle (x\lor x)}$أو${\displaystyle (\lnot x\lor \lnot x)}$في كل خطوة، مع الحفاظ على الاتساق، حتى تتضمن الصيغة بندًا لكل متغير. في كل خطوة من خطوات التوسيع هذه، يمكن دائمًا إضافة أحد هذين البندين مع الحفاظ على الاتساق، وإلا فيمكن توليد البند الآخر باستخدام قاعدة الاستدلال. بمجرد أن تحتوي جميع المتغيرات على بند من هذا الشكل في الصيغة، يمكن توليد تعيين مُرضٍ لجميع المتغيرات عن طريق تعيين متغير.${\displaystyle x}$تصبح صحيحة إذا كانت الصيغة تحتوي على العبارة${\displaystyle (x\lor x)}$وتعيينها إلى خطأ إذا كانت الصيغة تحتوي على العبارة${\displaystyle (\lnot x\lor \lnot x)}$[ ^{3 ]​}

كان كروم مهتمًا في المقام الأول باكتمال أنظمة قواعد الاستدلال، وليس بكفاءة الخوارزميات. ومع ذلك، تؤدي طريقته إلى حد زمني متعدد الحدود لحل مسائل الإرضاء من الدرجة الثانية. من خلال تجميع جميع البنود التي تستخدم المتغير نفسه، وتطبيق قاعدة الاستدلال على كل زوج من البنود، يُمكن إيجاد جميع الاستدلالات الممكنة من حالة معينة من حالات 2-CNF، واختبار ما إذا كانت متسقة، وذلك في زمن إجمالي قدره ^O ( n³ ) ، حيث n هو عدد المتغيرات في الحالة. تأتي هذه الصيغة من ضرب عدد المتغيرات في عدد أزواج البنود التي تتضمن متغيرًا معينًا، والتي يمكن تطبيق قاعدة الاستدلال عليها، وهو O( n² ) . وبالتالي، يُمكن تحديد ما إذا كانت حالة معينة من حالات 2-CNF قابلة للإرضاء في زمن قدره ^{O (} n³ ) . ولأن إيجاد تعيين مُرضٍ باستخدام طريقة كروم يتضمن سلسلة من عمليات التحقق من الاتساق O( n ) ، فسيستغرق ذلك زمنًا قدره ^O ( n⁴ ) . حتى أن إيتاي وشامير (1976) ذكرا حدًا زمنيًا أسرع قدره O( n² ⁾ لهذه الخوارزمية ، استنادًا إلى ترتيب أكثر دقة لعملياتها. ^{[ 7 ]} ومع ذلك، فقد تحسن هذا الحد الزمني الأصغر بشكل كبير بفضل خوارزميات الزمن الخطي اللاحقة لإيفان وإيتاي وشامير (1976) وأسبفال وبلاس وتارجان (1979) . ^{[ 8 ]}

فيما يتعلق بمخطط الاستلزام لمسألة الإرضاء من الدرجة الثانية، يمكن تفسير قاعدة استدلال كروم على أنها تُنشئ الإغلاق المتعدي للمخطط. وكما لاحظ كوك (1971) ، يمكن اعتبارها أيضًا مثالًا على خوارزمية ديفيس-بوتنام لحل مسائل الإرضاء باستخدام مبدأ الاستدلال . وتستند صحتها إلى صحة خوارزمية ديفيس-بوتنام الأكثر عمومية. أما حدها الزمني متعدد الحدود فيستند إلى حقيقة أن كل خطوة استدلال تزيد من عدد البنود في المسألة، وهو حد أعلى لدالة تربيعية لعدد المتغيرات. ^{[ 9 ]}

حتى أن إيتاي وشامير (1976) يصفان تقنية تتضمن التراجع المحدود لحل مسائل إرضاء القيود ذات المتغيرات الثنائية والقيود الزوجية. وقد طبقا هذه التقنية على مسألة جدولة الفصول الدراسية، لكنهما لاحظا أيضًا أنها قابلة للتطبيق على مسائل أخرى، بما في ذلك مسألة إرضاء القيود الثنائية (2-SAT). ^{[ 6 ]}

تعتمد الفكرة الأساسية لنهجهم على بناء عملية إسناد جزئية للحقيقة، متغيرًا تلو الآخر. تُعدّ بعض خطوات الخوارزميات "نقاط اختيار"، وهي نقاط يمكن عندها إعطاء المتغير إحدى قيمتين مختلفتين للحقيقة، وقد تؤدي الخطوات اللاحقة في الخوارزمية إلى التراجع إلى إحدى نقاط الاختيار هذه. مع ذلك، لا يمكن التراجع إلا إلى الاختيار الأخير. جميع الاختيارات التي تم إجراؤها قبل الاختيار الأخير نهائية. ^{[ 6 ]}

في البداية، لا توجد نقطة اختيار، وجميع المتغيرات غير مُخصصة. في كل خطوة، تختار الخوارزمية المتغير الذي سيتم تعيين قيمته، كما يلي: ^{[ 6 ]}

• إذا وُجد شرطٌ مُعَيَّنَت مُتغيراته مُسبقًا بطريقةٍ تُبطل هذا الشرط، فإن الخوارزمية تتراجع إلى آخر نقطة اختيارٍ لها، مُلغيةً بذلك التعيينات التي أجرتها منذ ذلك الاختيار، وتُعكس القرار الذي اتخذته عند ذلك الاختيار. أما إذا لم تكن هناك نقطة اختيار، أو إذا كانت الخوارزمية قد تراجعت بالفعل إلى آخر نقطة اختيارٍ لها، فإنها تُنهي البحث وتُبلغ بأن صيغة 2-CNF المُدخلة غير قابلة للتحقيق. ^{[ 6 ]}
• إذا كانت هناك عبارة تم فيها تحديد أحد متغيري العبارة بالفعل، ولا يزال من الممكن أن تصبح العبارة صحيحة أو خاطئة، فسيتم تحديد المتغير الآخر بطريقة تجبر العبارة على أن تصبح صحيحة. ^{[ 6 ]}
• في الحالة المتبقية، يُضمن أن تصبح كل عبارة صحيحة بغض النظر عن كيفية تعيين المتغيرات المتبقية، أو لم يتم تعيين أي من متغيريها بعد. في هذه الحالة، تُنشئ الخوارزمية نقطة اختيار جديدة وتُعيّن قيمة عشوائية لأي من المتغيرات غير المُعيّنة. ^{[ 6 ]}

بشكل بديهي، تتبع الخوارزمية جميع سلاسل الاستدلال بعد كل اختيار من اختياراتها. يؤدي هذا إما إلى تناقض وخطوة تراجع، أو، إذا لم يُستنتج أي تناقض، فإن الاختيار كان صحيحًا ويؤدي إلى تعيين مُرضٍ. لذلك، إما أن تجد الخوارزمية تعيينًا مُرضيًا بشكل صحيح، أو أنها تُحدد بشكل صحيح أن المُدخل غير قابل للتنفيذ. ^{[ 6 ]}

لم يصف إيفن وزملاؤه بالتفصيل كيفية تطبيق هذه الخوارزمية بكفاءة. واكتفوا بالقول إنه باستخدام "هياكل البيانات المناسبة لتحديد تبعات أي قرار"، يمكن تنفيذ كل خطوة من خطوات الخوارزمية (باستثناء التراجع) بسرعة. مع ذلك، قد تتسبب بعض المدخلات في تراجع الخوارزمية عدة مرات، حيث تُنفذ في كل مرة خطوات عديدة قبل التراجع، مما قد يجعل تعقيدها الإجمالي غير خطي. لتجنب هذه المشكلة، عدّلوا الخوارزمية بحيث تبدأ، بعد الوصول إلى كل نقطة اختيار، باختبار كلا التعيينين للمتغير المحدد عند نقطة الاختيار في آنٍ واحد، مع تخصيص عدد متساوٍ من الخطوات لكل تعيين. بمجرد أن يؤدي اختبار أحد هذين التعيينين إلى إنشاء نقطة اختيار أخرى، يتوقف الاختبار الآخر، بحيث لا يتبقى في أي مرحلة من مراحل الخوارزمية سوى فرعين من شجرة التراجع قيد الاختبار. وبهذه الطريقة، يتناسب إجمالي الوقت المستغرق في إجراء الاختبارين لأي متغير مع عدد المتغيرات وبنود صيغة الإدخال التي تُحدد قيمها بشكل دائم. ونتيجة لذلك، تستغرق الخوارزمية وقتًا خطيًا إجمالًا. ^{[ 6 ]} في المقارنات التجريبية على حالات تم إنشاؤها عشوائياً، كان إصدار من خوارزمية التراجع هذه أسرع من خوارزميات أخرى ذات وقت خطي. ^{[ 2 ]}

وجد Aspvall و Plass و Tarjan (1979) إجراءً خطيًا أبسط لحل مسائل الرضا من الدرجة 2، استنادًا إلى مفهوم المكونات المتصلة بقوة من نظرية الرسم البياني . ^{[ 5 ]}

يُقال إن رأسين في رسم بياني موجه متصلان اتصالاً قوياً إذا كان هناك مسار موجه من أحدهما إلى الآخر والعكس صحيح. هذه علاقة تكافؤ ، ويمكن تقسيم رؤوس الرسم البياني إلى مكونات متصلة اتصالاً قوياً، وهي مجموعات فرعية يكون فيها كل رأسين متصلين اتصالاً قوياً. توجد عدة خوارزميات فعالة ذات زمن خطي لإيجاد المكونات المتصلة اتصالاً قوياً في الرسم البياني، تعتمد على البحث العميق أولاً : خوارزمية تارجان للمكونات المتصلة اتصالاً قوياً ^{[ 10 ]} وخوارزمية المكونات القوية القائمة على المسار ^{[ 11 ]} تُجري كل منهما بحثاً عميقاً أولاً واحداً. أما خوارزمية كوساراجو فتُجري بحثين عميقين أولاً، لكنها بسيطة للغاية. ^{[ 12 ]}

فيما يتعلق بمخطط الاستلزام، ينتمي متغيران حرفيان إلى نفس المكون المتصل بقوة كلما وُجدت سلاسل استلزام من أحدهما إلى الآخر والعكس. لذا، يجب أن يكون للمتغيرين الحرفيين نفس القيمة في أي عملية إسناد مُرضية لحالة الإرضاء الثنائي المُعطاة. على وجه الخصوص، إذا كان متغير ونفيه ينتميان إلى نفس المكون المتصل بقوة، فلا يمكن إرضاء الحالة، لأنه من المستحيل إسناد نفس القيمة لكلا المتغيرين الحرفيين. وكما أوضح أسبفال وآخرون، هذا شرط ضروري وكافٍ : صيغة 2-CNF قابلة للإرضاء إذا وفقط إذا لم يكن هناك متغير ينتمي إلى نفس المكون المتصل بقوة الذي ينتمي إليه نفيه. ^{[ 5 ]}

يؤدي هذا مباشرةً إلى خوارزمية خطية لاختبار قابلية إرضاء صيغ 2-CNF: ببساطة، يتم إجراء تحليل اتصال قوي على مخطط الاستلزام والتحقق من أن كل متغير ونفيه ينتميان إلى مكونات مختلفة. مع ذلك، وكما أوضح أسبفال وآخرون، يؤدي هذا أيضًا إلى خوارزمية خطية لإيجاد تعيين مُرضٍ، إن وُجد. تُنفذ خوارزميتهم الخطوات التالية: ^{[ 5 ]}

• قم بإنشاء مخطط الاستلزام للمثال، وابحث عن مكوناته المتصلة بقوة باستخدام أي من خوارزميات الوقت الخطي المعروفة لتحليل الاتصال القوي. ^{[ 5 ]}
• تحقق مما إذا كان أي مكون متصل بقوة يحتوي على متغير ونفيه. إذا كان الأمر كذلك، فأبلغ عن أن الحالة غير قابلة للتحقيق وتوقف. ^{[ 5 ]}
• أنشئ تكثيفًا لمخطط الاستلزام، وهو مخطط أصغر يحتوي على رأس واحد لكل مكون متصل بقوة، وحافة من المكون i إلى المكون j كلما احتوى مخطط الاستلزام على حافة uv بحيث ينتمي u إلى المكون i وينتمي v إلى المكون j . يكون التكثيف تلقائيًا مخططًا موجهًا غير دوري ، ومثل مخطط الاستلزام الذي تم تكوينه منه، فهو متناظر عكسيًا . ^{[ 5 ]}
• رتب رؤوس التكثيف ترتيبًا طوبولوجيًا . ^{[ 5 ]} عمليًا، يمكن تحقيق ذلك بكفاءة كنتيجة ثانوية للخطوة السابقة، حيث يتم توليد المكونات بواسطة خوارزمية كوساراجو بترتيب طوبولوجي، وبواسطة خوارزمية تارجان بترتيب طوبولوجي عكسي. ^{[ 12 ] [ 13 ]}
• لكل مكون في الترتيب الطوبولوجي العكسي، إذا لم تكن متغيراته قد تم تعيين قيم منطقية لها مسبقًا، فعيّن جميع القيم الحرفية في المكون على أنها صحيحة. يؤدي هذا أيضًا إلى تعيين جميع القيم الحرفية في المكون المكمل على أنها خاطئة. ^{[ 5 ]}

بسبب الترتيب الطوبولوجي العكسي والتناظر المائل، عندما تُعيَّن قيمة حرفية ما على أنها صحيحة، فإن جميع القيم الحرفية التي يمكن الوصول إليها منها عبر سلسلة من الاستلزام ستكون قد عُيِّنت بالفعل على أنها صحيحة. وبالمثل، عندما تُعيَّن قيمة حرفية x على أنها خاطئة، فإن جميع القيم الحرفية التي تؤدي إليها عبر سلسلة من الاستلزام ستكون قد عُيِّنت هي الأخرى على أنها خاطئة. لذلك، فإن تعيين القيمة الصحيحة الذي تم إنشاؤه بهذه الطريقة يُحقق الصيغة المعطاة، مما يُكمل أيضًا برهان صحة الشرط الضروري والكافي الذي حدده أسبفال وآخرون ^{[ 5 ] .}

كما يوضح أسبفال وآخرون، يمكن أيضًا استخدام إجراء مماثل يتضمن الترتيب الطوبولوجي للمكونات المتصلة بقوة في الرسم البياني للاستلزام لتقييم الصيغ المنطقية الكمية بالكامل، حيث تكون الصيغة المراد قياسها صيغة 2-CNF. ^{[ 5 ]}

تعتمد العديد من الخوارزميات الدقيقة والتقريبية لحل مشكلة وضع التسميات تلقائيًا على مبدأ الإرضاء الثنائي. تتعلق هذه المشكلة بوضع تسميات نصية على عناصر الرسم التخطيطي أو الخريطة. عادةً، تكون مجموعة المواقع الممكنة لكل تسمية محدودة للغاية، ليس فقط بسبب الخريطة نفسها (يجب أن تكون كل تسمية قريبة من العنصر الذي تُشير إليه، ويجب ألا تحجب العناصر الأخرى)، بل أيضًا بسبب بعضها البعض: يجب ألا تتداخل أي تسميتين، وإلا ستصبحان غير قابلتين للقراءة. بشكل عام، يُعد إيجاد موضع تسمية يُلبي هذه القيود مشكلة صعبة الحل (NP-hard) . مع ذلك، إذا كان لكل عنصر موقعان محتملان فقط لتسميته (على سبيل المثال، الامتداد إلى يسار العنصر ويمينه)، فيمكن حل مشكلة وضع التسميات في وقت متعدد الحدود. في هذه الحالة، يمكن إنشاء حالة إرضاء ثنائي تحتوي على متغير لكل تسمية، وتحتوي على شرط لكل زوج من التسميات التي قد تتداخل، مما يمنع تعيين مواقع متداخلة لها. إذا كانت جميع التصنيفات عبارة عن مستطيلات متطابقة، فيمكن إثبات أن حالة الإرضاء من الدرجة الثانية المقابلة لا تحتوي إلا على عدد خطي من القيود، مما يؤدي إلى خوارزميات ذات زمن شبه خطي لإيجاد التصنيف. ^{[ 14 ]} يصف بون، تشو ، وتشين (1998) مشكلة تصنيف الخرائط حيث يكون كل تصنيف عبارة عن مستطيل يمكن وضعه في أحد ثلاثة مواضع بالنسبة لقطعة مستقيمة يُصنّفها: إما أن تكون القطعة المستقيمة أحد أضلاعه، أو أن يكون مركزه عليها. ويمثلون هذه المواضع الثلاثة باستخدام متغيرين ثنائيين، بحيث يصبح اختبار وجود تصنيف صحيح، مرة أخرى، مشكلة إرضاء من الدرجة الثانية. ^{[ 15 ]}

استخدم فورمان وواغنر (1991) مبدأ الإرضاء الثنائي كجزء من خوارزمية تقريبية لحل مشكلة إيجاد مربعات ذات أكبر حجم ممكن لمجموعة معينة من النقاط، مع مراعاة أن يكون أحد أركان كل مربع على النقطة التي يُشير إليها. ولإيجاد مربع ذي حجم محدد، استبعدا المربعات التي إذا تضاعفت ستتداخل مع نقطة أخرى، واستبعدا النقاط التي يمكن تسميتها بطريقة لا يمكن أن تتداخل مع تسمية نقطة أخرى. وقد أظهرا أن قواعد الاستبعاد هذه تجعل النقاط المتبقية تحتوي على موضعين محتملين فقط للتسمية لكل نقطة، مما يسمح بإيجاد موضع تسمية صالح (إن وُجد) كحل لمسألة الإرضاء الثنائي. ومن خلال البحث عن أكبر حجم للتسمية يؤدي إلى مسألة إرضاء ثنائي قابلة للحل، وجدا موضع تسمية صالحًا تكون فيه مربعات التسمية على الأقل نصف حجم الحل الأمثل. أي أن نسبة التقريب لخوارزميتهم لا تتجاوز اثنين. ^{[ 14 ] [ 16 ]} وبالمثل، إذا كان كل ملصق مستطيلاً ويجب وضعه بحيث تكون النقطة التي يشير إليها في مكان ما على طول حافته السفلية، فإن استخدام خاصية الرضا من الدرجة الثانية لإيجاد أكبر حجم للملصق الذي يوجد له حل بحيث تكون النقطة التي يشير إليها كل ملصق في زاوية سفلية يؤدي إلى نسبة تقريب لا تتجاوز اثنين. ^{[ 17 ]}

تم تطبيق مبدأ الإرضاء الثنائي (2-satisfiability) على مسائل أخرى تتعلق بتحديد المواقع الهندسية. ففي رسم المخططات ، إذا كانت مواقع الرؤوس ثابتة، وكان يجب رسم كل حافة كقوس دائري بموقعين محتملين (على سبيل المثال، كمخطط قوس )، فإن مسألة اختيار القوس المناسب لكل حافة لتجنب التقاطعات تُعدّ مسألة إرضاء ثنائي (2-satisfiability) بمتغير لكل حافة وقيد لكل زوج من المواقع التي قد تؤدي إلى تقاطع. مع ذلك، في هذه الحالة، يمكن تسريع الحل، مقارنةً بخوارزمية تبني ثم تبحث في تمثيل صريح لمخطط الاستلزام، وذلك بالبحث في المخطط ضمنيًا . ^{[ 18 ]} في تصميم الدوائر المتكاملة VLSI ، إذا كان لا بد من توصيل مجموعة من الوحدات بأسلاك يمكن لكل منها أن ينحني مرة واحدة على الأكثر، فإنه يوجد مساران محتملان للأسلاك، ويمكن حل مشكلة اختيار أي من هذين المسارين بحيث يمكن توجيه جميع الأسلاك في طبقة واحدة من الدائرة، كمسألة إرضاء من الدرجة الثانية. ^{[ 19 ]}

تناول بوروس وآخرون (1999) مشكلة أخرى في تصميم الدوائر المتكاملة واسعة النطاق (VLSI): وهي مسألة عكس اتجاه كل وحدة في تصميم الدائرة. لا يؤثر هذا العكس على وظائف الوحدة، ولكنه يُغير ترتيب نقاط اتصال إشارات الإدخال والإخراج بها، مما قد يؤثر على مدى اندماجها في بقية التصميم. درس بوروس وآخرون نسخة مبسطة من المشكلة، حيث وُضعت الوحدات مسبقًا على طول قناة خطية واحدة، ويجب توجيه الأسلاك بينها، مع وجود حد أقصى ثابت لكثافة القناة (الحد الأقصى لعدد الإشارات التي يجب أن تمر عبر أي مقطع عرضي منها). لاحظوا أن هذه النسخة من المشكلة يُمكن حلها كمسألة إرضاء ثنائية، حيث تربط القيود اتجاهات أزواج الوحدات المتقابلة مباشرةً عبر القناة. ونتيجةً لذلك، يُمكن أيضًا حساب الكثافة المثلى بكفاءة، من خلال إجراء بحث ثنائي، حيث تتضمن كل خطوة حل مسألة إرضاء ثنائية. ^{[ 20 ]}

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

يمكن استخدام الطريقة نفسها كإجراء فرعي عندما تكون أقطار المجموعات الفردية غير معروفة. لاختبار إمكانية تحقيق مجموع معين من الأقطار دون معرفة أقطار المجموعات الفردية، يمكن تجربة جميع أزواج الأقطار المستهدفة التي لا يتجاوز مجموعها المجموع المحدد، مع تمثيل كل زوج من الأقطار كحالة إرضاء من الدرجة الثانية، واستخدام خوارزمية إرضاء من الدرجة الثانية لتحديد ما إذا كان من الممكن تحقيق هذا الزوج من خلال التجميع. لإيجاد المجموع الأمثل للأقطار، يمكن إجراء بحث ثنائي تكون فيه كل خطوة بمثابة اختبار جدوى من هذا النوع. كما ينجح النهج نفسه في إيجاد عمليات تجميع تُحسّن تركيبات أخرى غير مجموع أقطار المجموعات، وتستخدم أرقام عدم تشابه عشوائية (بدلاً من المسافات في فضاء متري) لقياس حجم المجموعة. ^{[ 21 ]} يهيمن على الحد الزمني لهذه الخوارزمية الوقت اللازم لحل سلسلة من مسائل الإرضاء من الدرجة الثانية المرتبطة ارتباطًا وثيقًا ببعضها البعض، وقد أوضح رامناث (2004) كيفية حل هذه المسائل المرتبطة بسرعة أكبر مما لو تم حلها بشكل مستقل عن بعضها البعض، مما يؤدي إلى ^حد زمني إجمالي قدره O ( n³ ) لمسألة تجميع مجموع الأقطار. ^{[ 22 ]}

حتى أن إيتاي وشامير (1976) قد وضعا نموذجًا لجدولة الفصول الدراسية حيث يجب جدولة مجموعة من n معلمًا لتدريس كل مجموعة من m من الطلاب. عدد الساعات في الأسبوع التي يقضيها كل معلم${\displaystyle i}$يقضي مع المجموعة${\displaystyle j}$يتم وصفه من خلال المدخل${\displaystyle R_{ij}}$من مصفوفة${\displaystyle R}$تُعطى هذه البيانات كمدخلات للمسألة، ولكل معلم أيضًا مجموعة من الساعات التي يكون متاحًا خلالها للجدولة. وكما هو موضح، فإن المسألة من فئة NP-complete ، حتى عندما يكون لدى كل معلم ثلاث ساعات متاحة على الأكثر، ولكن يمكن حلها كحالة من حالات 2-satisfiability عندما يكون لدى كل معلم ساعتان متاحتان فقط. (يمكن استبعاد المعلمين الذين لديهم ساعة واحدة متاحة فقط من المسألة بسهولة). في هذه المسألة، كل متغير${\displaystyle v_{ij}}$يتوافق ذلك مع ساعة يقوم بها المعلم${\displaystyle i}$يجب أن يقضي الوقت مع المجموعة${\displaystyle j}$^{[6] يحدد التخصيص للمتغير ما إذا كانت تلك الساعة هي الأولى أو الثانية من الساعات المتاحة للمعلم ،} وهناك شرط قابلية إرضاء من نوعين يمنع أي تعارض من أي نوعين: مجموعتان مخصصتان لمعلم واحد في نفس الوقت، أو مجموعة واحدة مخصصة لمعلمين في نفس ^{الوقت .}

قام مياشيرو وماتسوي (2005) بتطبيق مفهوم الرضا الثنائي على مشكلة جدولة المباريات الرياضية، حيث تم اختيار مباريات بطولة بنظام الدوري مسبقًا، ويجب تحديد ملاعب الفرق التي ستُقام عليها المباريات. في هذه المشكلة، يُفضّل التناوب بين مباريات الذهاب والإياب قدر الإمكان، مع تجنب فترات الراحة التي يلعب فيها الفريق مباراتين متتاليتين على أرضه أو مباراتين متتاليتين خارج أرضه. يمكن لفريقين على الأكثر تجنب فترات الراحة تمامًا، بالتناوب بين مباريات الذهاب والإياب؛ ولا يمكن لأي فريق آخر أن يلعب نفس جدول مباريات الذهاب والإياب، لأنه في هذه الحالة لن يتمكن من اللعب ضد الفريق الذي يلعب معه نفس الجدول. لذلك، يتضمن الجدول الأمثل فريقين لا يحصلان على فترات راحة، وفترة راحة واحدة لكل فريق آخر. بمجرد اختيار أحد الفريقين اللذين لا يحصلان على فترات راحة، يمكن صياغة مسألة إرضاء ثنائية، حيث يمثل كل متغير فيها جدول مباريات الفريق (على أرضه أو خارجها) في مباراة واحدة، وتضمن القيود الخصائص التالية: أن يكون لأي فريقين جدول مباريات ثابت، وأن يحصل كل فريق على فترة راحة واحدة على الأكثر قبل المباراة مع الفريق الذي لا يحصل على فترات راحة، وفترة راحة واحدة على الأكثر بعد المباراة معه، وألا يحصل أي فريق على فترتي راحة. بالتالي، يمكن اختبار ما إذا كان الجدول الزمني يسمح بحلٍّ يتضمن العدد الأمثل لفترات الراحة عن طريق حل عدد خطي من مسائل الإرضاء الثنائية، مسألة واحدة لكل اختيار للفريق الذي لا يحصل على فترات راحة. كما تسمح تقنية مماثلة بإيجاد جداول زمنية يحصل فيها كل فريق على فترة راحة واحدة، مع التركيز على زيادة عدد فترات الراحة بدلاً من تقليله (لتقليل إجمالي المسافة التي تقطعها الفرق). ^{[ 23 ]}

التصوير المقطعي هو عملية استعادة الأشكال من مقاطعها العرضية. في التصوير المقطعي المنفصل ، وهو نسخة مبسطة من المشكلة التي دُرست بكثرة، يكون الشكل المراد استعادته هو متعدد المربعات (مجموعة فرعية من المربعات في الشبكة المربعة ثنائية الأبعاد )، وتوفر المقاطع العرضية معلومات إجمالية حول مجموعات المربعات في الصفوف والأعمدة الفردية للشبكة. ^{[ 24 ]} على سبيل المثال، في ألغاز النونوجرام الشائعة ، والمعروفة أيضًا باسم التلوين بالأرقام أو ألعاب الشبكة، تمثل مجموعة المربعات المراد تحديدها وحدات البكسل الداكنة في صورة ثنائية ، وتخبر المدخلات المُعطاة لحل اللغز المستخدم بعدد كتل وحدات البكسل الداكنة المتتالية التي يجب تضمينها في كل صف أو عمود من الصورة، وطول كل كتلة من هذه الكتل. ^{[ 25 ]} في أشكال أخرى من التصوير المقطعي الرقمي، تُعطى معلومات أقل عن كل صف أو عمود: فقط العدد الإجمالي للمربعات، بدلاً من عدد وطول كتل المربعات. تتمثل نسخة مكافئة من المشكلة في أنه يجب علينا استعادة مصفوفة 0-1 معينة بمعرفة مجموع القيم في كل صف وفي كل عمود من المصفوفة فقط. ^{[ 24 ]}

على الرغم من وجود خوارزميات ذات زمن متعدد الحدود لإيجاد مصفوفة بمجاميع صفوف وأعمدة معينة، ^{[ 26 ]} إلا أن الحل قد لا يكون فريدًا: إذ يمكن استكمال أي مصفوفة فرعية على شكل مصفوفة وحدة  2 ×  2 دون التأثير على صحة الحل. لذلك، بحث الباحثون عن قيود على الشكل المراد إعادة بنائه لتقييد فضاء الحلول. على سبيل المثال، يمكن افتراض أن الشكل متصل؛ ومع ذلك، فإن اختبار وجود حل متصل يُعد مسألة NP-كاملة. ^{[ 27 ]} وهناك نسخة أكثر تقييدًا وأسهل حلًا، وهي أن يكون الشكل محدبًا متعامدًا : أي يحتوي على كتلة مربعات متجاورة واحدة في كل صف وعمود. وقد حسّن كروباك ودور (1999) العديد من الحلول السابقة، موضحين كيفية إعادة بناء الأشكال المحدبة المتعامدة المتصلة بكفاءة، باستخدام 2-SAT. ^{[ 24 ]} تقوم فكرة حلهم على تخمين مؤشرات الصفوف التي تحتوي على الخلايا الموجودة في أقصى اليسار واليمين من الشكل المراد إعادة بنائه، ثم وضع مسألة إرضاء ثنائية لاختبار ما إذا كان هناك شكل متسق مع هذه التخمينات ومع مجاميع الصفوف والأعمدة المعطاة. يستخدمون أربعة متغيرات إرضاء ثنائية لكل مربع قد يكون جزءًا من الشكل المعطى، واحد منها يشير إلى ما إذا كان ينتمي إلى كل من "مناطق الزاوية" الأربع المحتملة للشكل، ويستخدمون قيودًا تجبر هذه المناطق على أن تكون منفصلة، ​​وأن يكون لها الأشكال المطلوبة، وأن تشكل شكلًا عامًا بصفوف وأعمدة متجاورة، وأن يكون لها مجاميع الصفوف والأعمدة المطلوبة. تستغرق خوارزميتهم وقتًا قدره O ( m³n ) ^، حيث m هو البعد الأصغر من بين بعدي الشكل المدخل و n هو البعد الأكبر من بين البعدين. تم توسيع نفس الطريقة لاحقًا لتشمل الأشكال المحدبة المتعامدة التي قد تكون متصلة قطريًا فقط بدلاً من اشتراط الاتصال المتعامد. ^{[ 28 ]}

في جزء من برنامج لحل ألغاز النونوجرام الكاملة، استخدم باتنبورغ وكوسترز ( 2008 ، 2009 ) مبدأ الرضا الثنائي لدمج المعلومات المستقاة من عدة طرق استدلالية أخرى. وبالنظر إلى حل جزئي للغز، يستخدمان البرمجة الديناميكية داخل كل صف أو عمود لتحديد ما إذا كانت قيود ذلك الصف أو العمود تجبر أيًا من مربعاته على أن يكون أبيض أو أسود، وما إذا كان من الممكن ربط أي مربعين في نفس الصف أو العمود بعلاقة ضمنية. كما يحولان النونوجرام إلى مسألة تصوير مقطعي رقمي عن طريق استبدال تسلسل أطوال الكتل في كل صف وعمود بمجموعها، ويستخدمان صيغة التدفق الأقصى لتحديد ما إذا كانت مسألة التصوير المقطعي الرقمي هذه، التي تجمع جميع الصفوف والأعمدة، تحتوي على أي مربعات يمكن تحديد حالتها أو أزواج من المربعات يمكن ربطها بعلاقة ضمنية. إذا حددت أي من هاتين الطريقتين الاستدلاليتين قيمة أحد المربعات، يتم تضمينه في الحل الجزئي وتُكرر نفس العمليات الحسابية. مع ذلك، إذا فشلت كلتا الطريقتين الاستدلاليتين في تحديد أي مربعات، تُدمج النتائج التي توصلتا إليها في مسألة إرضاء من الدرجة الثانية، ويُستخدم حلّ خاص بهذه المسألة لإيجاد مربعات تُحدد قيمتها، ثم تُكرر العملية. قد تنجح هذه العملية في إيجاد حل أو لا، ولكن من المضمون أن تعمل في وقت متعدد الحدود. يُشير باتنبورغ وكوسترز إلى أنه على الرغم من أن معظم ألغاز الصحف لا تحتاج إلى كامل إمكانيات هذه الطريقة، فإن كلاً من هذه الطريقة وطريقة أخرى أكثر فعالية ولكن أبطأ تجمع بين منهج الإرضاء من الدرجة الثانية والتراجع المحدود لإيفن وإيتاي وشامير (1976) ^{[ 6 ]} ، أكثر فعالية بشكل ملحوظ من البرمجة الديناميكية وأساليب التدفق الاستدلالية التي لا تعتمد على الإرضاء من الدرجة الثانية عند تطبيقها على ألغاز النونوغرام العشوائية الأكثر صعوبة. ^{[ 25 ]} 

إلى جانب مسائل الإرضاء من النوع 2، تُعدّ مسائل الإرضاء من نوع هورن الفئة الفرعية الرئيسية الأخرى من مسائل الإرضاء التي يُمكن حلّها في وقت متعدد الحدود . في هذه الفئة من مسائل الإرضاء، يكون المُدخل عبارة عن صيغة في شكلها الطبيعي الاقتراني. يُمكن أن تحتوي هذه الصيغة على عدد غير محدود من المتغيرات في كل بند، ولكن على الأكثر متغير موجب واحد. وقد وجد لويس (1978) تعميمًا لهذه الفئة، وهو مسائل الإرضاء من نوع هورن القابلة لإعادة التسمية ، والتي يُمكن حلّها أيضًا في وقت متعدد الحدود باستخدام حالة مساعدة من مسائل الإرضاء من النوع 2. تُوصف الصيغة بأنها قابلة لإعادة التسمية من نوع هورن عندما يكون من الممكن تحويلها إلى شكل هورن عن طريق استبدال بعض المتغيرات بنفيها. وللقيام بذلك، يُنشئ لويس حالة من مسائل الإرضاء من النوع 2 بمتغير واحد لكل متغير من متغيرات حالة الإرضاء من نوع هورن القابلة لإعادة التسمية، حيث تُشير متغيرات الإرضاء من النوع 2 إلى ما إذا كان ينبغي نفي متغيرات الإرضاء من نوع هورن القابلة لإعادة التسمية المُقابلة لها أم لا. لإنتاج نموذج هورن، يجب ألا يظهر أي متغيرين في نفس بند نموذج هورن القابل لإعادة التسمية بشكل إيجابي في ذلك البند؛ يُعرف هذا القيد على زوج من المتغيرات بقيد قابلية الإرضاء من الدرجة الثانية. من خلال إيجاد تعيين مُرضٍ لنموذج قابلية الإرضاء من الدرجة الثانية الناتج، يُبين لويس كيفية تحويل أي نموذج هورن قابل لإعادة التسمية إلى نموذج هورن في وقت متعدد الحدود. ^{[ 29 ]} بتقسيم البنود الطويلة إلى بنود أصغر متعددة، وتطبيق خوارزمية قابلية الإرضاء من الدرجة الثانية ذات وقت خطي، يُمكن اختزال ذلك إلى وقت خطي. ^{[ 30 ]}

كما تم تطبيق مفهوم قابلية الإرضاء من الدرجة الثانية على مشاكل التعرف على الرسوم البيانية غير الموجهة التي يمكن تقسيمها إلى مجموعة مستقلة وعدد قليل من الرسوم البيانية الفرعية الثنائية الكاملة ، ^{[ 31 ]} واستنتاج العلاقات التجارية بين الأنظمة الفرعية المستقلة للإنترنت، ^{[ 32 ]} وإعادة بناء الأشجار التطورية . ^{[ 33 ]}

يمكن وصف خوارزمية غير حتمية لتحديد ما إذا كانت حالة إرضاء من الدرجة الثانية غير قابلة للإرضاء، باستخدام مقدار لوغاريتمي فقط من الذاكرة القابلة للكتابة، بسهولة: ببساطة، اختر (بطريقة غير حتمية) متغيرًا v وابحث (بطريقة غير حتمية) عن سلسلة من الاستلزام تؤدي من v إلى نفيه ثم تعود إلى v . إذا تم العثور على مثل هذه السلسلة، فإن الحالة لا يمكن إرضاؤها. ^{[ 34 ]} وبحسب نظرية إيمرمان-سيليبكسيني ، من الممكن أيضًا في فضاء لوغاريتمي غير حتمي التحقق من أن حالة إرضاء من الدرجة الثانية قابلة للإرضاء. ^{[ 35 ]}

تُعدّ مسألة الإرضاء الثنائي مسألةً كاملةً في فئة NL ، ^{[ 34 ]} مما يعني أنها من أصعب المسائل أو أكثرها تعبيرًا في فئة التعقيد NL للمسائل القابلة للحل غير الحتمي في الفضاء اللوغاريتمي. ويعني الاكتمال هنا أن آلة تورينغ حتمية تستخدم الفضاء اللوغاريتمي فقط قادرة على تحويل أي مسألة أخرى في NL إلى مسألة إرضاء ثنائي مكافئة. وبالمثل، كما هو الحال في فئة التعقيد NP الأكثر شهرة ، يسمح هذا التحويل، بالإضافة إلى نظرية إيمرمان-سزيليبسيني، بتمثيل أي مسألة في NL كصيغة منطقية من الدرجة الثانية ذات مسند واحد مُكمّم وجوديًا، مع بنود محدودة الطول إلى 2. تُعرف هذه الصيغ باسم SO-Krom. ^{[ 36 ]} وبالمثل، يمكن التعبير عن الشكل الطبيعي الضمني في منطق الدرجة الأولى بإضافة عامل للإغلاق المتعدي . ^{[ 36 ]}

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

يصف فيدر (1994) خوارزميةً لحصر جميع حلول مسألة إرضاء من الدرجة الثانية بكفاءة، ولحل العديد من المسائل ذات الصلة. ^{[ 38 ]} كما توجد خوارزميات لإيجاد تعيينين مُرضيين لهما أقصى مسافة هامينغ بينهما. ^{[ 39 ]}

تُعرف مسألة #2SAT بأنها مسألة حساب عدد التعيينات المُرضية لصيغة 2-CNF مُعطاة. تُصنف هذه المسألة ضمن فئة #P-complete ، ^{[ 40 ]} مما يعني أنها غير قابلة للحل في زمن متعدد الحدود إلا إذا كانت P  =  NP . علاوة على ذلك، لا توجد طريقة تقريب عشوائية متعددة الحدود بالكامل لمسألة #2SAT إلا إذا كانت NP = RP ، ويظل هذا صحيحًا حتى عند تقييد المُدخلات بصيغ 2-CNF الرتيبة، أي صيغ 2-CNF التي يكون فيها كل حرف عبارة عن ظهور موجب لمتغير. ^{[ 41 ]}

أسرع خوارزمية معروفة لحساب العدد الدقيق للتعيينات المُرضية لصيغة 2SAT تعمل في وقت${\displaystyle O(1.2377^{n})}$[ ^{42 ] [ 43 ] [ 44 ]​}

يمكن تكوين حالة إرضاء ثنائية عشوائيًا، لعدد n من المتغيرات و m من البنود، باختيار كل بند عشوائيًا وبشكل منتظم من مجموعة جميع البنود الممكنة ذات المتغيرين. عندما يكون m صغيرًا نسبيًا مقارنةً بـ n ، فمن المرجح أن تكون هذه الحالة قابلة للإرضاء، ولكن القيم الأكبر لـ m تقلل من احتمالية كونها قابلة للإرضاء. بتعبير أدق، إذا تم تثبيت m / n كثابت α ≠ 1، فإن احتمالية الإرضاء تؤول إلى حد معين عندما يؤول n إلى اللانهاية: إذا كان α  <  1، فإن الحد يساوي واحدًا، بينما إذا كان α  >  1، فإن الحد يساوي صفرًا. وبالتالي، تُظهر المسألة انتقالًا طوريًا عند α  =  1. ^{[ 45 ]}

في مسألة إرضاء شرطين كحد أقصى ( MAX-2-SAT )، يكون المدخل عبارة عن صيغة في شكل اقتراني عادي تحتوي على متغيرين حرفيين لكل بند، والمهمة هي تحديد الحد الأقصى لعدد البنود التي يمكن إرضاؤها في آن واحد من خلال عملية إسناد. ومثل مسألة الإرضاء القصوى الأكثر عمومية ، فإن MAX-2-SAT هي مسألة صعبة الحل من فئة NP . ويتم إثباتها بالاختزال من مسألة 3SAT . ^{[ 46 ]}

بصياغة مسألة MAX-2-SAT كمسألة إيجاد قطع (أي تقسيم الرؤوس إلى مجموعتين فرعيتين) يُعظّم عدد الحواف التي لها طرف في المجموعة الفرعية الأولى وطرف في الثانية، في رسم بياني مرتبط برسم بياني الاستلزام، وتطبيق أساليب البرمجة شبه المحددة على مسألة القطع هذه، يُمكن إيجاد حل تقريبي في وقت متعدد الحدود يُحقق على الأقل 0.940... ضعف العدد الأمثل للشروط. ^{[ 47 ]} تُعرف حالة MAX-2-SAT المتوازنة بأنها حالة من MAX-2-SAT حيث يظهر كل متغير بشكل إيجابي وسلبي بنفس الوزن. وقد حسّن أوسترين نسبة التقريب لهذه المسألة إلى${\displaystyle \min \left\{(3-\cos \theta )^{-1}(2+(2/\pi )\theta )\,:\,\pi /2\leq \theta \leq \pi \right\}=0.943...}$[ ^{48 ]​}

إذا صحّت فرضية الألعاب الفريدة ، فإنه يستحيل تقريب مسألة MAX 2-SAT، سواء كانت متوازنة أم لا، بثابت تقريب أفضل من 0.943... في زمن متعدد الحدود. ^{[ 49 ]} وبافتراض أضعف، وهو أن P  ≠  NP ، فإن المسألة معروفة فقط بأنها غير قابلة للتقريب بثابت أفضل من 21/22 = 0.95454... ^{[ 50 ]}

وقد استكشف العديد من المؤلفين أيضًا حدود الوقت الأسية في أسوأ الحالات للحل الدقيق لحالات MAX-2-SAT. ^{[ 51 ]}

في مسألة الرضا الموزون من الدرجة الثانية ( W2SAT )، يكون المدخل عبارة عن${\displaystyle n}$لدينا مثال 2SAT ذو متغير واحد وعدد صحيح k ، والمشكلة هي تحديد ما إذا كان هناك تعيين مُرضٍ يكون فيه k من المتغيرات صحيحة بالضبط. ^{[ 52 ]}

تتضمن مسألة W2SAT، كحالة خاصة، مسألة تغطية الرؤوس ، وهي إيجاد مجموعة من k رؤوس تلامس جميع حواف رسم بياني غير موجه مُعطى. لأي حالة مُعطاة من مسألة تغطية الرؤوس، يُمكن إنشاء مسألة W2SAT مُكافئة بمتغير لكل رأس من رؤوس الرسم البياني. يُمكن تمثيل كل حافة uv من الرسم البياني بشرط 2SAT u ∨ v ، والذي لا يُمكن تحقيقه إلا بتضمين إما u أو v ضمن المتغيرات الحقيقية للحل. عندئذٍ، تُشفّر الحالات المُرضية لصيغة 2SAT الناتجة حلولًا لمسألة تغطية الرؤوس، ويوجد تعيين مُرضٍ مع k متغيرات حقيقية إذا وفقط إذا كان هناك تغطية رؤوس مع k رؤوس. لذلك، مثل مسألة تغطية الرؤوس، فإن W2SAT هي مسألة NP-كاملة . ^{[ 53 ]}

علاوة على ذلك، في حالة التعقيد المُعَلم ، تُشكل مسألة W2SAT مسألةً كاملةً طبيعيةً من النوع W[1] ، ^{[ 52 ]} مما يعني أن W2SAT غير قابلة للحل باستخدام المعاملات الثابتة إلا إذا تحقق هذا الشرط لجميع المسائل في W[1] . أي أنه من غير المرجح وجود خوارزمية لـ W2SAT يكون زمن تشغيلها على الصورة f ( k )· nO ^{(1) . بل وأكثر من ذلك} ، لا يمكن حل W2SAT في زمن ^nO ( ^{k ) إلا} إذا فشلت فرضية الزمن الأسي . ^{[ 54 ]}

إلى جانب اكتشافه أول خوارزمية ذات زمن متعدد الحدود لحل مشكلة قابلية الإرضاء من الدرجة الثانية، صاغ كروم (1967) أيضًا مشكلة تقييم الصيغ البوليانية الكمية بالكامل، حيث تكون الصيغة المراد تحديد كميتها صيغة من الدرجة الثانية من نوع CNF. تُعد مشكلة قابلية الإرضاء من الدرجة الثانية حالة خاصة من مشكلة CNF الكمية هذه، حيث تكون جميع المحددات الكمية وجودية . كما طور كروم إجراءً فعالًا لاتخاذ القرار بشأن هذه الصيغ. وقد أظهر أسبفال وبلاس وتارجان (1979) أنه يمكن حلها في زمن خطي، وذلك بتوسيع تقنيتهم ​​الخاصة بالمكونات المتصلة بقوة والترتيب الطوبولوجي. ^{[ 3 ] [ 5 ]}

يمكن أيضًا طرح مسألة الإرضاء الثنائي لمنطق القضايا متعدد القيم . لا تكون الخوارزميات عادةً خطية، بل إن المسألة تُصنف ضمن مسائل NP-الكاملة في بعض أنواع المنطق. للاطلاع على دراسات استقصائية، يُرجى مراجعة Hähnle ( 2001 ، 2003 ) . ^{[ 55 ]}