قابلية الإرضاء

مسألة NP كاملة
	قابلية الإرضاء 3سات; NAE; أو آي تي; ;
	تلوين مخطط تلوين مخطط بثلاثة ألوان; تلوين مخطط مستو بثلاثة ألوان; ;
	زمرة كبرى
	مسار هاملتونياني
	عدل

قابلية الإرضاء تعبير في الرياضيات وفي نظرية التعقيد الحسابي ذو أهمية كبيرة جدا.^[1]^[2]^[3]

الصيغة العادية لعطف عبارات مكونة من فصل المتغيرات

هي عبارة عن صيغة عناصرها متغيرات تقبل فقط القيم صحيح خطأ 0 1 لا نعم موزعة على أقواس وتستعمل العمليات المنطقية عطف وفصل ونفي كما في هذا المثال: $(a \lor \neg b \lor c) \land (a \lor b \lor \neg d) \land (a \lor c \lor e) \land (b \lor d \lor \neg e)$ .

جعل الصيغة صحيحة

المسألة الخاصة هو البحث عن قيم المتغيرات بحيث تكون الصيغة صحيحة يعني أن كل قوس يجب أن يكون صحيحا يعني أن يكون هناك على الأقل متغير في كل قوس له القيمة 1 نعم صحيح.

محاولة تجريب كل الاحتمالات الممكنة يحتاج لوقت أسي $O (c^{n})$ .

مراجع

^ Baier, Christel (2012). "Chapter 1.3 Undecidability of FOL". Lecture Notes — Advanced Logics. Technische Universität Dresden — Institute for Technical Computer Science. ص. 28–32. مؤرشف من الأصل (PDF) في 2020-10-14. اطلع عليه بتاريخ 2012-07-21.
^ Alexander Bockmayr؛ Volker Weispfenning (2001). "Solving Numerical Constraints". في John Alan Robinson؛ Andrei Voronkov (المحررون). Handbook of Automated Reasoning Volume I. Elsevier and MIT Press. (ردمك 0-444-82949-0) (Elsevier) (ردمك 0-262-18221-1) (MIT Press).
^ فرانز بادر؛ Tobias Nipkow (1998). Term Rewriting and All That. Cambridge University Press. ص. 58–92. ISBN:0-521-77920-0.

هذه بذرة مقالة عن الرياضيات او موضوع متعلق بها بحاجة للتوسيع. فضلًا شارك في تحريرها.

[1] Baier, Christel (2012). "Chapter 1.3 Undecidability of FOL". Lecture Notes — Advanced Logics. Technische Universität Dresden — Institute for Technical Computer Science. ص. 28–32. مؤرشف من الأصل (PDF) في 2020-10-14. اطلع عليه بتاريخ 2012-07-21.

[2] Alexander Bockmayr؛ Volker Weispfenning (2001). "Solving Numerical Constraints". في John Alan Robinson؛ Andrei Voronkov (المحررون). Handbook of Automated Reasoning Volume I. Elsevier and MIT Press. (ردمك 0-444-82949-0) (Elsevier) (ردمك 0-262-18221-1) (MIT Press).

[3] فرانز بادر؛ Tobias Nipkow (1998). Term Rewriting and All That. Cambridge University Press. ص. 58–92. ISBN:0-521-77920-0.

[1]

[2]

[3]