Pada Januari 2020, Papadimitriou telah memikirkan prinsip lubang merpati selama 30 tahun. Jadi dia terkejut ketika percakapan santai dengan rekan kerja sering membawa mereka ke twist sederhana pada prinsip yang belum pernah mereka pertimbangkan: Bagaimana jika ada lebih sedikit merpati daripada lubang? Dalam hal ini, setiap susunan merpati harus meninggalkan beberapa lubang kosong. Sekali lagi, itu tampak jelas. Tapi apakah membalikkan prinsip lubang merpati memiliki konsekuensi matematika yang menarik? Terdengar seolah-olah prinsip “lubang merpati kosong” ini hanya yang asli dengan nama lain. Tapi itu tidak, dan karakter yang sedikit berbeda membuatnya menjadi alat baru dan bermanfaat untuk mengklasifikasikan masalah komputasi. Untuk memahami prinsip lubang merpati kosong, mari kita kembali ke contoh kartu bank, dipindahkan dari stadion sepak bola ke aula konser dengan 3.000 kursi—jumlah yang lebih kecil dari total PIN empat digit yang mungkin. Prinsip lubang merpati kosong menentukan bahwa beberapa PIN mungkin tidak terwakili sama sekali. Jika Anda ingin menemukan salah satu PIN yang hilang ini, meskipun, tidak ada cara yang lebih baik selain hanya bertanya pada setiap orang PIN mereka. Jadi jauh, prinsip lubang merpati kosong sama seperti rekan terkenalnya. Perbedaannya terletak pada kesulitan memeriksa solusi. Bayangkan seseorang mengatakan bahwa mereka telah menemukan dua orang tertentu di stadion sepak bola yang memiliki PIN yang sama. Dalam kasus ini, sesuai dengan skenario lubang merpati asli, ada cara sederhana untuk memverifikasi klaim tersebut: Cukup periksa dengan dua orang yang bersangkutan. Tetapi dalam kasus aula konser, bayangkan seseorang menegaskan bahwa tidak ada orang yang memiliki PIN 5926. Di sini, tidak mungkin untuk diverifikasi tanpa bertanya pada semua orang di audiens apa PIN mereka. Itu membuat prinsip lubang merpati kosong jauh lebih menjengkelkan bagi teoris kompleksitas. Dua bulan setelah Papadimitriou mulai memikirkan prinsip lubang merpati kosong, dia membicarakannya dalam percakapan dengan seorang calon mahasiswa pascasarjana. Dia mengingatnya dengan jelas, karena ternyata itu adalah percakapan terakhirnya secara langsung dengan siapa pun sebelum lockdown Covid-19. Terkurung di rumah selama beberapa bulan berikutnya, dia bergulat dengan implikasi masalah tersebut untuk teori kompleksitas. Akhirnya dia dan rekan-rekannya menerbitkan makalah tentang masalah pencarian yang dijamin memiliki solusi karena prinsip lubang merpati kosong. Mereka terutama tertarik pada masalah di mana lubang merpati melimpah—yaitu, di mana mereka jauh melampaui jumlah merpati. Sesuai dengan tradisi akronim yang rumit dalam teori kompleksitas, mereka menamai kelas masalah ini APEPP, untuk “abundant polynomial empty-pigeonhole principle.” Salah satu masalah dalam kelas ini terinspirasi oleh bukti terkenal 70 tahun oleh ilmuwan komputer pionir Claude Shannon. Shannon membuktikan bahwa sebagian besar masalah komputasi harus sulit dipecahkan secara inheren, menggunakan argumen yang bergantung pada prinsip lubang merpati kosong (meskipun dia tidak menyebutnya begitu). Namun selama beberapa dekade, ilmuwan komputer telah mencoba dan gagal membuktikan bahwa masalah tertentu benar-benar sulit. Seperti PIN kartu bank yang hilang, masalah sulit pasti ada di luar sana, meskipun kita tidak dapat mengidentifikasinya. Secara historis, para peneliti belum memikirkan proses mencari masalah sulit sebagai masalah pencarian yang bisa dianalisis secara matematis. Pendekatan Papadimitriou, yang mengelompokkan proses tersebut dengan masalah pencarian lain yang terhubung dengan prinsip lubang merpati kosong, memiliki rasa referensial diri yang merupakan ciri khas dari banyak karya terbaru dalam teori kompleksitas—menawarkan cara baru untuk berpikir tentang kesulitan membuktikan kesulitan komputasi.