سُورُ فريجه

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

قال: من اليسير أن تُبنى آلة تورنغ تأخذ صيغةً F من حساب المحمولات وعددًا طبيعيًّا n فتقرّر: أللصيغة برهانٌ طوله n رمزًا أم لا؟ فلتكن Ψ(F,n) عددَ الخطوات التي تستغرقها الآلة في ذلك، ولتكن φ(n) أكبرَ هذه الأعداد على اختلاف الصيغ. والسؤال: بأي سرعة تنمو φ(n) عند أمثل آلة؟ وفي الوسع أن يُبرهن أنّ φ(n) لا تقلّ عن kn، وليس عنده أكثر من هذا.

وكتب: «لو وُجدت حقًّا آلة تكون عندها φ(n) من رتبة kn، بل حتى kn² فحسب، لكانت العواقب بالغة الخطر. إذ يعني ذلك بيّنًا أنّ العمل الذهني للرياضياتي في المسائل التي جوابها بنعم أو لا يمكن أن تحلّ الآلات محلّه حلولًا تامّة، خلا وضعِ البديهيات. فليس على المرء إلا أن يختار n كبيرًا بحيث إذا لم تُخرج الآلة نتيجةً لم يبقَ معنًى للتفكير في المسألة بعدُ»^¹. ولم يقلها متوجّسًا ولا محذّرًا، بل أردف أنه «يرى ممكنًا تمامًا» أن تنمو φ(n) هذا النموّ البطيء، وعلّل: الحدّ الأدنى kn هو كلّ ما يُستخرج من تعميم برهان عدم الحسم، والاختصار المطلوب لا يزيد على ردّ عدد الخطوات من N إلى لوغاريتمها، ونظيرُ هذا الاختصار واقعٌ في مسائل منتهية أخرى. وختم بمثالٍ عابر: «ويحسُن أن يُعرف كيف الأمر، مثلًا، في تقرير ما إذا كان عددٌ ما أوّليًّا».

والفصلُ في وجود برهان لا يتجاوز طولًا معلومًا مسألةٌ تامّة في NP بلغة اليوم؛ فسؤال غودل هو P وNP بعينهما، قبل أن يوضع الاسم بخمس عشرة سنة، ومعه المطلبُ الكمّي في صورته الحادّة. ولا يُعرف للرسالة جواب. كان فون نويمان في آخر أشهره، ومات في فبراير 1957. وبقيت الورقة في أوراقه لا يعلم بها أحدٌ من أهل الميدان حتى أخرجها يوريس هارتمانِس سنة 1989^².

وفي تلك السنين الثلاث والثلاثين كان الميدان يعيد اكتشاف السؤال من غير أن يدري أنه مكتوب بخطّ اليد على بعد أميال منه. فلما نشر ستيفن كوك وروبرت ريكهاو سنة 1979 ورقتهما «الكفاءة النسبية للأنساق البرهانية القضوية» صدّراها بفقرةٍ نصّها: لو كانت P تساوي NP لوُجد كثيرُ حدود p وخوارزمية 𝒜 بحيث تُعطى أيَّ قضية S من قضايا نظرية المجموعات وأيَّ عدد صحيح n، فتقرّر في p(n) خطوةً فقط أَلِـS برهانٌ طوله n أو أقلّ في نظرية زِرْمِلو وفرنكل^³. هذه مسألة غودل بحروفها، أُعيد وضعُها على مكتب في تورنتو بعد إحدى وعشرين سنة، ووصلت الورقة إلى محرّري المجلة في مايو 1977، والرسالةُ يومئذ مطويّةٌ في أوراق لم تُنشر.

وعرّفا «النسق البرهاني» تعريفًا عاريًا من كل زخرف موروث: هو دالّةٌ تحسبها آلةٌ حتمية في زمن كثير الحدود، تأخذ نصًّا ما فتُخرج قضيةً قضوية تصدق مهما كانت قيم متغيراتها، أي صادقةً صورية tautology، وتبلغ في إخراجها كلَّ صادقة صورية بلا استثناء. فالنصّ الذي أخرج الصادقة هو «برهانها»، ولا يُشترط فيه شكلٌ ولا بديهيات ولا قواعد استدلال، بل يُشترط فيه شيء واحد: أن يكون التحقّق منه رخيصًا. والنسق عندهما محدودٌ بكثير حدود إن وُجد كثيرُ حدود يحدّ طولَ أقصر برهان بدلالة طول القضية. وبرهنا: NP مغلقةٌ على التتميم إذا وفقط إذا وُجد نسقٌ برهانيٌّ قضويٌّ محدود بكثير حدود^⁴.

فمسألةُ الآلات وأزمنةِ حسابها صارت مسألةً في أطوال البراهين: أيوجد حسابٌ منطقي يبرهن كلَّ صادقة صورية برهانًا قصيرًا؟ ولم يعد تعقيدُ الحساب وتعقيدُ البرهان بابين متجاورين، بل بابًا واحدًا يُدخل منه من الجهتين. وبرنامج كوك المترتّب على هذا: خذ الأنساق البرهانية واحدًا واحدًا، وأثبت في كلّ نسق أنّ ثمّة عائلةً من الصادقات الصورية لا تُبرهن فيه إلا ببراهين تنمو نموًّا أُسّيًّا. فمتى استُنفدت الأنساق كلها ثبت أنّ NP لا تساوي coNP، ولزم منه أنّ P لا تساوي NP.

والطبقة الوسطى من هذه الأنساق هي أنساق هيلبرت المعتادة التي يدرسها كل طالب منطق في سنته الأولى: بديهياتٌ مصوغة على شاكلات، وقاعدةُ استدلال واحدة هي قاعدة الفصل modus ponens. وقد سمّاها كوك وريكهاو في الفقرة الثانية من ورقتهما اسمًا لم يتغيّر منذئذ: «أنساق فريجه»، وعلّلا التسمية بثلاث كلمات: «نسبةً إلى فريجه»^⁵. بل في تعريف النسق نفسه أثرٌ من الرجل الذي كُتبت إليه رسالة 1956: فنسقُ فريجه في «الخط المفهومي» لا يطابق التعريف الحديث، لأنه يقوم على بديهيات معدودة وقاعدة تعويض مضمرة؛ والفكرة التي حلّت شاكلاتُ البديهيات بها محلّ قاعدة التعويض منسوبةٌ، بنصّ كوك وريكهاو نقلًا عن تشرش، إلى فون نويمان^⁶.

وكان لا بدّ للبرنامج من حجرٍ يُجرَّب عليه، فوقع الاختيار على أسخف قضية في الرياضيات وأشدّها عنادًا: مبدأ بيوت الحمام pigeonhole principle. إذا أدخلتَ n+1 حمامةً في n وَكرًا فلا بدّ أن يجتمع في وكرٍ اثنتان. لا يماري في هذا طفل. وتُصاغ الدعوى صياغةً قضوية في متغيرات عددها n(n+1)، فتصير عائلةً من الصادقات الصورية، ويصير السؤال: كم يطول برهانها في كل نسق؟

الجواب في أضعف الأنساق، وهو «الحلّ» resolution الذي لا يعرف إلا قاعدةً واحدة تأخذ «أ أو س» و«ب أو ليس س» فتنتج «أ أو ب»: أُسّيّ. برهنه أرمين هاكن سنة 1985، وكان أول حدّ أدنى حقيقي في تاريخ الميدان^⁷. والجواب في نسق فريجه محدود العمق، أي حين يُشترط ألا يزيد تداخل الروابط في أي سطر على عمق ثابت: فوق كثير الحدود. برهنه ميكلوش أيتاي سنة 1988، ولم ينله بالتوافيق وحدها: بنى نموذجًا غير قياسي nonstandard model من نماذج الحساب، وأجرى الحجّة فيه على عدد لا متناهٍ، ونزل بها إلى المتناهي بمبرهنة التراصّ compactness. فحدٌّ أدنى على طول برهان قضوي في نسق مقيَّد، وهو دعوى توافيقية محضة عن أشياء متناهية، لم يُنَل أول مرة إلا بنظرية النماذج^⁸. ورقّى غيرُه الحدَّ إلى أُسّيّ ونزع منه النماذج غير القياسية^⁹.

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

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

ولمّا استعصت المسألة من جهة الأنساق أُتيت من جهة الحساب. ففي 1975 وضع كوك نظريةً معادلاتية سمّاها PV، رموزُها الدالّية هي بعينها الدوالّ التي تُحسب في زمن كثير الحدود^¹¹. وصنع بَس سنة 1986 في رسالته «الحساب المحدود» bounded arithmetic سلسلةً من النظريات أشهرُها S¹₂، وقيّد فيها الاستقراء الرياضي induction تقييدًا دقيقًا: لا على العدد بل على طوله، أي على عدد أرقامه^¹². والنتيجة التي يقوم عليها البناء كلّه تسمّى مبرهنة الشهادة witnessing theorem: إذا برهنت S¹₂ أنّ لكلّ x يوجد y تتحقّق فيه علاقةٌ من صنف معيّن، فثمّة دالّةٌ تُحسب في زمن كثير الحدود، وتبرهن النظريةُ نفسها أنّ قيمتها عند x هي الـy المطلوب.

وهي نظريةٌ لا تستطيع أن تفكّر إلا في زمن كثير الحدود. كلُّ ما تُثبت وجوده تستطيع أن تجده، ولا تُثبت وجود ما لا تقدر على بلوغه؛ فالوجود عندها والبلوغُ إليه شيء واحد. وهي أدقّ صياغة صورية لمعنى «الاستدلال المُجدي»: استدلالٌ لا يستبيح خطوةً لا يقدر على دفع ثمنها. وتُشدّ هذه النظريات إلى الأنساق القضوية بترجمة: فالبرهان في S¹₂ لقضية من صنف مناسب يُترجم إلى برهان قضوي طولُه كثيرُ حدود في نسق فريجه الممدَّد، والبرهان في نظرية أضعف يُترجم إلى برهان في فريجه محدود العمق. فتمّ المثلث: صنفُ تعقيد يقابله نظريةٌ حسابية تقابلها نسقٌ برهاني، والثلاثة وجوهٌ لشيء واحد، ومن حرّك ضلعًا حرّك الضلعين.

وعلى هذا المثلث برهن ألكسندر رازبوروف سنة 1995: بشرط وجود مولّدات شبه عشوائية قوية، وهو الشرط الذي تقوم عليه كلُّ حمايةٍ معمّاة تُستعمل اليوم في العالم، فإنّ نظريةً من هذه النظريات المقيَّدة عاجزةٌ عن أن تدحض القضية القائلة إنّ ثمّة دارةً صغيرة تحلّ مسألة الإشباع^¹³. فالاستدلال المُجدي عاجزٌ عن أن يبرهن أنّ SAT لا تحلّها دارةٌ صغيرة؛ وP لا تساوي NP، إن كانت صادقة، قد تكون صادقةً لا يبلغها برهانٌ رخيص.

وهو غودل مرةً أخرى، منزلةً واحدة إلى أسفل. فمبرهنة عدم التمام تقول إنّ في كلّ نظرية كافية صادقاتٍ لا تُبرهن فيها البتّة؛ وهذه تقول إنّ في الاستدلال المُجدي صادقاتٍ لا تُبرهن فيه رخيصًا. تلك في اللانهاية وهذه في المتناهي، وقد سمّى بافل بودلاك البرنامج كلّه باسمه الصحيح: «عدم التمام في الميدان المتناهي»^¹⁴. وليس في الرياضيات موضعٌ آخر يكون فيه العجزُ عن البرهنة مبرهنةً لها شروط ونتائج.

والحواجز الثلاثة التي أوقفت كلّ محاولة في نصف قرن مبرهناتٌ داخل النظرية نفسها، تقول ما الذي لا يصلح أن يكون طريقًا إلى الجواب. أوّلها التنسيب relativization: برهن بيكر وغِلّ وسولوفاي سنة 1975 أنّ ثمّة مجيبًا oracle، أي صندوقًا يُلحق بالآلتين فيجيب عن سؤال بعينه في خطوة واحدة، تتساوى عنده P وNP، وثمّة مجيبًا آخر تفترقان عنده^¹⁵. فكلُّ حجّة تعامل الآلة معاملة الصندوق المغلق، وهذا شأن الحجّة القطرية diagonalization الموروثة عن غودل وتورنغ، ساقطةٌ سلفًا، لأنها لو صلحت لصلحت في الحالين وهما متناقضان. وثانيها البراهين الطبيعية natural proofs: برهن رازبوروف ورودِتش أنّ كلّ حجّة في الحدود الدنيا تكون بنّاءةً وتنطبق على أكثر الدوالّ، وهذان وصفان يجتمعان في كلّ ما نُقل عن التوافيق في هذا الباب، لو صحّت لكسرت مولّدات شبه العشوائية، فهدمت التعمية كلها^¹⁶. وثالثها الجبرنة algebrization: برهن آرونسون وويغدرسون سنة 2009 أنّ الطرائق الجبرية التي نُقض بها الحاجز الأول، وهي التي أعطت IP = PSPACE ومبرهنة PCP، تتنسّب هي أيضًا إذا أُخذ المجيب في صورة تمديد قليل الدرجة^¹⁷.

فعلى كلّ تقنية مقترحة أن تجتاز ثلاثة اختبارات معًا: ألا تتنسّب، وألا تكون طبيعية، وألا تتجبرن. وليس في الجَعبة كلها ما يجتازها إلا النادر. وأصرحُ صورةٍ لهذا الاشتباك طريقةٌ في تعقيد البرهان تسمّى الإقحام المُجدي feasible interpolation وضعها يان كرايتشِك: إن كان النسق يقبلها فكلُّ برهان قصير فيه يتحوّل إلى دارة صغيرة تفصل بين مجموعتين، فتصير الحدودُ الدنيا على الدارات حدودًا دنيا على البراهين. ونجحت الطريقة في الأنساق الضعيفة نجاحًا تامًّا. أما نسق فريجه فقد برهن بونيه وبيتاسّي ورَزّ أنه لا يقبلها إلا أن تكون أعداد بلوم تُحلَّل إلى عواملها في زمن كثير الحدود^¹⁸. فالذي يمنع الطريقةَ من الصعود إلى فريجه هو بعينه الذي يجعل التعمية آمنة: كلّما اشتدّ يقيننا بأنّ أسرارنا محفوظة اشتدّ يقيننا بأنّ براهيننا ممنوعة.

وينزل هذا كلّه إلى حديد الآلات في موضع واحد. فبرامج حلّ الإشباع SAT solvers التي يقوم عليها اليوم تحقيقُ العتاد والتخطيطُ وتحليلُ البرمجيات تعمل كلها بخوارزمية واحدة هي التعلّم من التعارض؛ وكلُّ مسار لهذه الخوارزمية على صيغة غير مُشبَعة هو دحضٌ بالحلّ، وقد ثبت أنّ الخوارزمية بإعادة التشغيل تحاكي الحلّ العامّ محاكاةً كثيرة الحدود^¹⁹. فمبرهنة هاكن سنة 1985 ليست دعوى في المنطق النظري، بل حكمٌ غير مشروط على صناعة بأسرها: لا توجد ولن توجد أداةٌ من هذه الأسرة تفكّ مبدأ بيوت الحمام. حدٌّ أدنى بُرهن على الورق قبل أن تُكتب هذه البرامج بعقود، يحدّها اليوم ويحدّ ما سيُكتب منها غدًا، ولا سبيل إلى نقضه بذكاء مهندس ولا بسرعة معالج.

والميدان لم يقف. ففي أبريل من هذه السنة نشر يان بيخ ورَهول سانثانام ورقةً عنوانها «نحو P ≠ NP انطلاقًا من الحدود الدنيا لفريجه الممدَّد»، يبنيان فيها لكلّ دالّة تُحسب في زمن كثير الحدود عائلةَ صيغٍ شاهدة، ويبرهنان أنّ هذه الصيغ إن كانت صادقاتٍ صورية فإنّ أيّ حدّ أدنى فوق كثير الحدود على نسق فريجه الممدَّد مزيدًا عليه هذه الصيغُ بديهياتٍ يستلزم أنّ الإشباع يحتاج إلى دارات فوق كثيرة الحدود^²⁰. فالبرنامج الذي بدأه كوك وريكهاو سنة 1979 لا يزال، بعد سبع وأربعين سنة، يُشدّ إلى المسألة الكبرى شدًّا أوثق كل عقد.

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

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

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