بحلول يناير 2020 ، كان باباديميتريو يفكر في مبدأ حمامة لمدة 30 عامًا. لذلك فوجئ عندما قادتهم محادثة مرحة مع متعاون متكرر إلى تطور بسيط حول المبدأ الذي لم يفكروا فيه أبدًا: ماذا لو كان هناك حمام أقل من الثقوب؟ في هذه الحالة ، يجب أن يترك أي ترتيب من الحمام بعض الثقوب الفارغة. مرة أخرى ، يبدو واضحا. ولكن هل يكون لعقل مبدأ حمامة أي عواقب رياضية مثيرة للاهتمام؟
قد يبدو الأمر كما لو أن مبدأ “بيجونول الفارغ” هو مجرد اسم الأصلي بآخر. لكنها ليست كذلك ، وقد جعلتها طابعها مختلفًا بمهارة أداة جديدة ومثمرة لتصنيف المشكلات الحسابية.
لفهم مبدأ ثقب البيجون الفارغ ، دعنا نعود إلى مثال بطاقة البنوك ، الذي تم نقله من ملعب كرة القدم إلى قاعة للحفلات الموسيقية التي تحتوي على 3000 مقعد-عدد أقل من إجمالي دبابيس أربعة أرقام ممكنة. يملي مبدأ الفراغ الفارغ أن بعض المسامير الممكنة لا تمثل على الإطلاق. إذا كنت ترغب في العثور على واحدة من هذه المسامير المفقودة ، على الرغم من ذلك ، لا يبدو أن هناك طريقة أفضل من مجرد سؤال كل شخص. حتى الآن ، فإن مبدأ البيجون الفارغ يشبه نظيره الأكثر شهرة.
الفرق يكمن في صعوبة التحقق من الحلول. تخيل أن شخصًا ما يقول إنه عثر على شخصين محددين في ملعب كرة القدم ولديهما نفس الدبوس. في هذه الحالة ، المقابلة لسيناريو الحمام الأصلي ، هناك طريقة بسيطة للتحقق من هذه المطالبة: فقط تحقق مع الشخصين المعنيين. ولكن في قاعة الحفلات الموسيقية ، تخيل أن شخصًا ما يؤكد أنه لا يوجد أي شخص لديه دبوس يبلغ 5926. هنا ، من المستحيل التحقق دون أن يسأل الجميع في الجمهور. وهذا يجعل مبدأ البيجون الفارغ أكثر تحرشًا لمنظري التعقيد.
بعد شهرين من بدء Papadimitriou في التفكير في مبدأ البيجون الفارغ ، قدمها في محادثة مع طالب دراسات عليا محتملين. إنه يتذكر ذلك بوضوح ، لأنه اتضح أنه آخر محادثته الشخصية مع أي شخص قبل قفلات Covid-19. تحظى في المنزل خلال الأشهر التالية ، وتصارع مع تداعيات المشكلة على نظرية التعقيد. في نهاية المطاف ، نشر هو وزملاؤه ورقة حول مشاكل البحث التي تضمن أن يكون لها حلول بسبب مبدأ البيجون الفارغ. كانوا مهتمين بشكل خاص بالمشاكل التي تكون فيها فتحات الحمام وفيرة – أي ، حيث يفوق عدد الحمام. تمشيا مع تقليد اختصارات غير عملية في نظرية التعقيد ، أطلقوا على هذه الفئة من المشكلات APEPP ، من أجل “مبدأ الوفرة الفارغة متعدد الحدود”.
كانت إحدى المشكلات في هذا الفصل مستوحاة من دليل شهير يبلغ من العمر 70 عامًا من قبل عالم الكمبيوتر الرائد كلود شانون. أثبتت شانون أن معظم المشكلات الحسابية يجب أن يكون من الصعب حلها بطبيعتها ، باستخدام حجة تعتمد على مبدأ البيجون الفارغ (على الرغم من أنه لم يسميها). ومع ذلك ، على مدى عقود ، حاول علماء الكمبيوتر وفشلوا في إثبات أن المشكلات المحددة صعبة حقًا. مثل مفقود دبابيس بطاقة البنوك ، يجب أن تكون هناك مشاكل صعبة ، حتى لو لم نتمكن من التعرف عليها.
تاريخيا ، لم يفكر الباحثون في عملية البحث عن مشاكل صعبة كمشكلة بحث يمكن تحليلها رياضيا. كان نهج Papadimitriou ، الذي قام بتجميع تلك العملية بمشكلات البحث الأخرى المرتبطة بمبدأ بيجونول الفارغ ، له نكهة مرجعية ذاتيًا عن الكثير من العمل الحديثة في نظرية التعقيد-عرضت طريقة جديدة لسبب صعوبة إثبات الصعوبة الحسابية.