نظرية كوك-ليفين

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

سُميت النظرية نسبةً إلى ستيفن كوك وليونيد ليفين . ويعود الفضل في برهانها إلى ريتشارد كارب ، استناداً إلى برهان سابق (باستخدام مفهوم مختلف للاختزال) لكوك. ^{[ 1 ]}

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

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

ازداد الاهتمام النظري بمسألة الاكتمال من فئة NP بفضل أعمال ثيودور بي. بيكر، وجون جيل، وروبرت سولوفاي، الذين أثبتوا عام 1975 أن حل مسائل NP في نماذج معينة من آلات التنبؤ يتطلب وقتًا أُسّيًا. أي، يوجد مُنبئ A بحيث أنه بالنسبة لجميع فئات التعقيد الزمني الحتمي شبه الأُسّي T، فإن فئة التعقيد النسبية NP ^{A ليست} مجموعة جزئية من T ^A. وبالتحديد، بالنسبة لهذا المُنبئ، P ^A  ≠  NP ^{A. [ 3} ]

في الاتحاد السوفيتي، نُشرت نتيجة مماثلة لنتيجة بيكر وجيل وسولوفاي في عام 1969 بواسطة م. دختيار. ^{[ 4 ]} وفي وقت لاحق ، نُشرت ورقة ليونيد ليفين بعنوان "مشكلات البحث الشامل" ^{[ 5 ]} في عام 1973، على الرغم من أنها ذُكرت في محادثات وقُدمت للنشر قبل ذلك ببضع سنوات.

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

تُصنف مسألة القرار ضمن فئة NP إذا كان من الممكن حلها بواسطة آلة تورينج غير حتمية في وقت متعدد الحدود .

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

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

يستند هذا البرهان إلى البرهان الذي قدمه غاري وجونسون 1979 ، الصفحات 38-44، القسم 2.6 . 

يتألف إثبات أن مسألة إرضاء العبارات المنطقية (SAT) هي مسألة كاملة من فئة NP من جزأين. الأول هو إثبات أن SAT هي مسألة من فئة NP. أما الثاني فهو إثبات إمكانية اختزال أي مسألة من فئة NP إلى حالة من مسائل SAT من خلال اختزال متعدد الحدود إلى مسألة واحدة .

تُصنَّف مسألة SAT ضمن فئة NP لأن أي إسناد لقيم منطقية لمتغيرات منطقية، يُزعم أنه يحقق التعبير المُعطى، يمكن التحقق منه في وقت متعدد الحدود بواسطة آلة تورينغ حتمية. (العبارات التي يمكن التحقق منها في وقت متعدد الحدود بواسطة آلة تورينغ حتمية ، والتي يمكن حلها في وقت متعدد الحدود بواسطة آلة تورينغ غير حتمية، متكافئة، ويمكن إيجاد البرهان في العديد من الكتب الدراسية، على سبيل المثال كتاب Sipser's Introduction to the Theory of Computing ، القسم 7.3، وكذلك في مقالة ويكيبيديا حول NP ).

لنفترض الآن أن مشكلة معينة في فئة NP يمكن حلها بواسطة آلة تورينج غير الحتمية${\displaystyle M=(Q,\Sigma ,s,F,\delta )}$، أين${\displaystyle Q}$هي مجموعة الحالات،${\displaystyle \Sigma }$هي أبجدية رموز الشريط،${\displaystyle s\in Q}$هي الحالة الابتدائية،${\displaystyle F\subseteq Q}$هي مجموعة الحالات المقبولة، و${\displaystyle \delta \subseteq ((Q\setminus F)\times \Sigma )\times (Q\times \Sigma \times \{-1,+1\})}$هي علاقة الانتقال. لنفترض كذلك أن${\displaystyle M}$يقبل أو يرفض حالة من حالات المشكلة بعد مدة لا تتجاوز${\displaystyle p(n)}$خطوات الحساب، حيث${\displaystyle n}$حجم المثيل و${\displaystyle p}$هي دالة متعددة الحدود.

لكل مدخل،${\displaystyle I}$حدد تعبيرًا منطقيًا${\displaystyle B}$وهذا قابل للتنفيذ إذا وفقط إذا كانت الآلة${\displaystyle M}$يقبل${\displaystyle I}$.

يستخدم التعبير المنطقي المتغيرات الموضحة في الجدول التالي. هنا،${\displaystyle q\in Q}$هي حالة الآلة،${\displaystyle -p(n)\leq i\leq p(n)}$هو موضع الشريط،${\displaystyle j\in \Sigma }$هو رمز شريط لاصق، و${\displaystyle 0\leq k\leq p(n)}$يمثل رقم خطوة الحساب.

المتغيرات	التفسير المقصود	كم عددهم؟ [ 6 ]
${\displaystyle T_{i,j,k}}$	صحيح إذا كانت الخلية الشريطية${\displaystyle i}$يحتوي على رمز${\displaystyle j}$الخطوة${\displaystyle k}$من الحساب.	${\displaystyle O(p(n)^{2})}$
${\displaystyle H_{i,k}}$	صحيح إذا${\displaystyle M}$رأس القراءة/الكتابة موجود في خلية الشريط${\displaystyle i}$الخطوة${\displaystyle k}$من الحساب.	${\displaystyle O(p(n)^{2})}$
${\displaystyle Q_{q,k}}$	صحيح إذا${\displaystyle M}$هو في الولاية${\displaystyle q}$الخطوة${\displaystyle k}$من الحساب.	${\displaystyle O(p(n))}$

عرّف التعبير المنطقي${\displaystyle B}$ليكون اقتران التعبيرات الفرعية في الجدول التالي، لجميع${\displaystyle -p(n)\leq i\leq p(n)}$و${\displaystyle 0\leq k\leq p(n)}$:

تعبير	شروط	تفسير	كم عدد؟
${\displaystyle T_{i,j,0}}$	خلية شريطية${\displaystyle i}$يحتوي في البداية على رمز${\displaystyle j}$	المحتويات الأولية للشريط. لـ${\displaystyle i>n-1}$و${\displaystyle i<0}$، خارج نطاق المدخلات الفعلية${\displaystyle I}$، الرمز الأولي هو الرمز الافتراضي/الفارغ الخاص.	${\displaystyle O(p(n))}$
${\displaystyle Q_{s,0}}$		الحالة الأولية لـ${\displaystyle M}$.	1
${\displaystyle H_{0,0}}$		الموضع الابتدائي لرأس القراءة/الكتابة.	1
${\displaystyle \neg T_{i,j,k}\lor \neg T_{i,j',k}}$	${\displaystyle j\neq j'}$	رمز واحد على الأكثر لكل خلية شريط.	${\displaystyle O(p(n)^{2})}$
${\displaystyle \bigvee _{j\in \Sigma }T_{i,j,k}}$		رمز واحد على الأقل لكل خلية شريط.	${\displaystyle O(p(n)^{2})}$
${\displaystyle \lnot Q_{q,k}\lor \lnot Q_{q',k}}$	${\displaystyle q\neq q'}$	ولاية واحدة على الأكثر في كل مرة.	${\displaystyle O(p(n))}$
${\displaystyle \bigvee _{q\in Q}Q_{q,k}}$		ولاية واحدة على الأقل في كل مرة.	${\displaystyle O(p(n))}$
${\displaystyle \lnot H_{i,k}\lor \lnot H_{i',k}}$	${\displaystyle i\neq i'}$	وضعية رأس واحدة على الأكثر في كل مرة.	${\displaystyle O(p(n)^{3})}$
${\displaystyle \bigvee _{-p(n)\leq i\leq p(n)}H_{i,k}}$		وضعية رأس واحدة على الأقل في كل مرة.	${\displaystyle O(p(n)^{2})}$
${\displaystyle T_{i,j,k}\land T_{i,j',k+1}\rightarrow H_{i,k}}$	${\displaystyle j\neq j'}$	يبقى الشريط دون تغيير ما لم يكتب عليه رئيس القسم.	${\displaystyle O(p(n)^{2})}$
${\displaystyle {\begin{array}{l}(H_{i,k}\land Q_{q,k}\land T_{i,\sigma ,k})\to \\\bigvee _{((q,\sigma ),(q',\sigma ',d))\in \delta }(H_{i+d,\ k+1}\land Q_{q',\ k+1}\land T_{i,\ \sigma ',\ k+1})\end{array}}}$	${\displaystyle k<p(n)}$	التحولات المحتملة في خطوة الحساب${\displaystyle k}$عندما يكون الرأس في الوضع${\displaystyle i}$.	${\displaystyle O(p(n)^{2})}$
${\displaystyle \bigvee _{0\leq k\leq p(n)}\bigvee _{f\in F}Q_{f,k}}$		يجب الانتهاء في حالة قبول، في موعد لا يتجاوز الخطوة${\displaystyle p(n)}$.	1

إذا كانت هناك عملية حسابية مقبولة لـ${\displaystyle M}$عند الإدخال${\displaystyle I}$، ثم${\displaystyle B}$يمكن تحقيق ذلك عن طريق التعيين${\displaystyle T_{i,j,k}}$،${\displaystyle H_{i,k}}$و${\displaystyle Q_{i,k}}$تفسيراتهم المقصودة. من ناحية أخرى، إذا${\displaystyle B}$إذا كانت قابلة للإرضاء، فهناك حساب مقبول لـ${\displaystyle M}$عند الإدخال${\displaystyle I}$والتي تتبع الخطوات المشار إليها في عمليات إسناد المتغيرات.

هناك${\displaystyle O(p(n)^{2})}$متغيرات منطقية، كل منها قابل للترميز في الفضاء${\displaystyle O(\log p(n))}$عدد البنود هو${\displaystyle O(p(n)^{3})}$^{[ 7 ]} لذا فإن حجم${\displaystyle B}$يكون${\displaystyle O(\log(p(n))p(n)^{3})}$وبالتالي فإن التحويل هو بالتأكيد اختزال متعدد الحدود، كما هو مطلوب.

الصف الأول فقط من الجدول (${\displaystyle T_{i,j,0}}$يعتمد ذلك في الواقع على سلسلة الإدخال${\displaystyle I}$أما الأسطر المتبقية فتعتمد فقط على طول المدخلات.${\displaystyle n}$وعلى الآلة${\displaystyle M}$فهي تُضفي طابعًا رسميًا على عملية حسابية عامة لـ${\displaystyle M}$لمدة تصل إلى${\displaystyle p(n)}$خطوات.

يعتمد التحويل بشكل كبير على متعدد الحدود${\displaystyle p(n)}$وبالتالي، فإن البرهان المذكور أعلاه ليس بناءً : حتى لو${\displaystyle M}$إذا عُرفت قيمة معينة، مما يدل على انتماء المسألة المعطاة إلى فئة NP، فلا يمكن حساب التحويل بشكل فعال، إلا إذا تم تحديد حد أعلى.${\displaystyle p(n)}$ل${\displaystyle M}$كما أن تعقيد الوقت معروف أيضًا.

بينما تقوم الطريقة المذكورة أعلاه بترميز آلة تورينج غير حتمية في تعقيد${\displaystyle O(\log(p(n))p(n)^{3})}$تصف الأدبيات مناهج أكثر تطوراً في مجال التعقيد${\displaystyle O(p(n)\log(p(n)))}$[ ^{8 ] [ 9 ] [ 10 ] [ 11 ] [ 12 ]} ظهرت النتيجة شبه الخطية لأول مرة بعد سبع سنوات من نشر كوك الأصلي ^.

يمكن توسيع نطاق استخدام SAT لإثبات وجود مسألة NP-كاملة ليشمل مسائل حسابية أخرى في المنطق، وليشمل أيضًا إثبات اكتمالها لفئات تعقيد أخرى . تتضمن مسألة الصيغة البولية الكمية (QBF) صيغًا بولية موسعة لتشمل مُكمِّمات شاملة متداخلة ومُكمِّمات وجودية لمتغيراتها. يمكن استخدام مسألة QBF لترميز الحساب باستخدام آلة تورينج محدودة بتعقيد مساحة متعدد الحدود ، مما يثبت وجود مسألة (التعرف على الصيغ البولية الكمية الصحيحة) كاملة من فئة PSPACE . وبالمثل، تُرمِّز الصيغ البولية الكمية التابعة الحساب باستخدام آلة تورينج محدودة بتعقيد مساحة لوغاريتمي ، مما يثبت وجود مسألة كاملة من فئة NL . ^{[ 13 ] [ 14 ]}

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

لقد تجلى أهمية اكتمال NP من خلال نشر ورقة ريتشارد كارب الرائدة عام 1972 بعنوان "الاختزال بين المسائل التوافقية"، والتي أظهر فيها أن 21 مسألة متنوعة في مجال التوافقية ونظرية الرسوم البيانية ، كل منها مشهورة بصعوبة حلها، هي مسائل كاملة من فئة NP. ^{[ 1 ]}

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

قدم غاري وجونسون أكثر من 300 مشكلة كاملة من نوع NP في كتابهما " الحواسيب والاستعصاء: دليل لنظرية اكتمال NP" ، ^{[ 16 ]} ولا تزال تُكتشف مشاكل جديدة ضمن فئة التعقيد هذه.

على الرغم من إمكانية حل العديد من الحالات العملية لمسألة SAT باستخدام الطرق الاستدلالية ، إلا أن مسألة وجود خوارزمية حتمية متعددة الحدود لحل SAT (وبالتالي جميع مسائل NP-complete الأخرى) لا تزال مشكلة شهيرة لم تُحل، على الرغم من عقود من الجهود المكثفة التي بذلها علماء نظرية التعقيد وعلماء المنطق الرياضي وغيرهم. لمزيد من التفاصيل، انظر مقالة "مسألة P مقابل NP" .