Versi aslinya dari cerita ini muncul di Berapa banyak majalah.
Mereka mengatakan seekor burung di tangan bernilai dua di semak -semak, tetapi untuk para ilmuwan komputer, dua burung di dalam lubang masih lebih baik. Itu karena burung -burung kohabit itu adalah protagonis dari teorema matematika sederhana yang disebut prinsip pigeonhole. Sangat mudah untuk menyimpulkan dalam satu kalimat pendek: Jika enam merpati bersarang menjadi lima lubang merpati, setidaknya dua dari mereka harus berbagi lubang. Itu saja – itulah semuanya.
“Prinsip Pigeonhole adalah teorema yang memunculkan senyum,” kata Christos Papadimitriouseorang ilmuwan komputer teoretis di Columbia University. “Ini bagian percakapan yang fantastis.”
Tapi prinsip Pigeonhole bukan hanya untuk burung -burung. Meskipun kedengarannya sangat mudah, itu menjadi alat yang ampuh bagi para peneliti yang terlibat dalam proyek sentral ilmu komputer teoritis: Memetakan koneksi tersembunyi antara berbagai masalah.
Prinsip Pigeonhole berlaku untuk situasi apa pun di mana item ditetapkan untuk kategori, dan item lebih banyak dari kategori. Misalnya, ini menyiratkan bahwa di stadion sepak bola yang penuh sesak dengan 30.000 kursi, beberapa peserta harus memiliki kata sandi empat digit yang sama, atau pin, untuk kartu bank mereka. Di sini merpati adalah penggemar sepak bola, dan lubangnya adalah 10.000 pin yang berbeda, 0000 hingga 9999. Itu kemungkinan lebih sedikit daripada jumlah total orang, sehingga beberapa orang harus memiliki angka yang sama.
Bukti ini penting bukan hanya karena kesederhanaannya, tetapi juga untuk apa yang ditinggalkannya. Banyak metode matematika untuk membuktikan bahwa ada sesuatu yang “konstruktif,” yang berarti mereka juga menunjukkan kepada Anda bagaimana menemukannya. Bukti “nonkonstruktif”, seperti yang didasarkan pada prinsip pigeonhole, tidak memiliki properti ini. Dalam contoh stadion sepak bola, mengetahui bahwa beberapa orang harus memiliki pin yang sama tidak akan memberi tahu Anda apa adanya. Anda selalu dapat melewati tribun meminta setiap orang secara bergantian. Tapi apakah ada cara yang lebih sederhana?
Pertanyaan seperti ini, tentang cara paling efisien untuk menyelesaikan masalah, adalah inti dari cabang ilmu komputer yang dikenal sebagai teori kompleksitas komputasi. Para ahli teori kompleksitas mempelajari pertanyaan -pertanyaan seperti itu dengan menyatukan masalah ke dalam kelas berdasarkan properti bersama tertentu. Kadang -kadang langkah pertama menuju terobosan hanyalah mendefinisikan kelas baru untuk menyatukan masalah yang sebelumnya tidak dipelajari para peneliti bersama.
Itulah yang terjadi pada 1990 -an, ketika papadimitriou dan ahli teori kompleksitas lainnya mulai belajar Kelas Masalah Barudi mana tujuannya adalah untuk menemukan sesuatu yang harus ada karena prinsip hole atau bukti nonkonstruktif lainnya. Garis pekerjaan itu telah menyebabkan kemajuan penting dalam bidang ilmu komputer yang berbeda kriptografi ke Teori Game Algoritmik.
Christos Papadimitriou (Inset) dan Oliver Korten menunjukkan bahwa prinsip pigeonhole kosong terhubung ke masalah penting dalam matematika dan ilmu komputer.
Pada Januari 2020, Papadimitriou telah memikirkan prinsip Pigeonhole selama 30 tahun. Jadi dia terkejut ketika percakapan lucu dengan kolaborator yang sering membawa mereka ke sentuhan sederhana pada prinsip yang tidak pernah mereka pertimbangkan: bagaimana jika ada lebih sedikit merpati daripada lubang? Dalam hal ini, setiap pengaturan merpati harus meninggalkan beberapa lubang kosong. Sekali lagi, sepertinya jelas. Tetapi apakah membalikkan prinsip Pigeonhole memiliki konsekuensi matematika yang menarik?
Mungkin terdengar seolah-olah prinsip “piweonhole” ini hanyalah yang asli dengan nama lain. Tapi tidak, dan karakternya yang berbeda telah menjadikannya alat baru dan bermanfaat untuk mengklasifikasikan masalah komputasi.
Untuk memahami prinsip pigeonhole kosong, mari kita kembali ke contoh kartu bank, ditransmisikan dari stadion sepak bola ke ruang konser dengan 3.000 kursi-jumlah yang lebih kecil dari total kemungkinan pin empat digit. Prinsip pigeonhole kosong menentukan bahwa beberapa pin yang mungkin tidak terwakili sama sekali. Namun, jika Anda ingin menemukan salah satu dari pin yang hilang ini, tampaknya tidak ada cara yang lebih baik daripada sekadar meminta setiap orang PIN mereka. Sejauh ini, prinsip pigeonhole kosong itu seperti rekannya yang lebih terkenal.
Perbedaannya terletak pada kesulitan memeriksa solusi. Bayangkan seseorang mengatakan mereka telah menemukan dua orang tertentu di stadion sepak bola yang memiliki pin yang sama. Dalam hal ini, sesuai dengan skenario lubang merpati asli, ada cara sederhana untuk memverifikasi klaim itu: cukup periksa dengan dua orang yang dimaksud. Tetapi dalam kasus ruang konser, bayangkan bahwa seseorang menegaskan bahwa tidak ada orang yang memiliki pin 5926. Di sini, tidak mungkin untuk memverifikasi tanpa bertanya kepada semua orang di antara hadirin apa pin mereka. Itu membuat prinsip pigeonhole kosong jauh lebih menjengkelkan bagi para ahli teori kompleksitas.
Dua bulan setelah Papadimitriou mulai berpikir tentang prinsip pigeonhole kosong, ia membawanya dalam percakapan dengan calon mahasiswa pascasarjana. Dia mengingatnya dengan jelas, karena ternyata menjadi percakapan langsung terakhirnya dengan siapa pun sebelum kuncian Covid-19. Cooled di rumah selama beberapa bulan berikutnya, ia bergulat dengan implikasi masalah untuk teori kompleksitas. Akhirnya dia dan rekan -rekannya menerbitkan a kertas tentang masalah pencarian yang dijamin memiliki solusi karena prinsip pigeonhole kosong. Mereka terutama tertarik pada masalah di mana lubang merpati berlimpah – yaitu, di mana mereka jauh melebihi jumlah merpati. Sesuai dengan tradisi akronim yang berat Dalam teori kompleksitas, mereka dijuluki kelas masalah ini, untuk “prinsip polinomial pigeonhole yang berlimpah.”
Salah satu masalah di kelas ini terinspirasi oleh yang terkenal Bukti berusia 70 tahun oleh ilmuwan komputer perintis Claude Shannon. Shannon membuktikan bahwa sebagian besar masalah komputasi harus secara inheren sulit dipecahkan, menggunakan argumen yang mengandalkan prinsip pigeonhole kosong (meskipun dia tidak menyebutnya demikian). Namun selama beberapa dekade, para ilmuwan komputer telah mencoba dan gagal membuktikan bahwa masalah spesifik benar -benar sulit. Seperti pin kartu bank yang hilang, masalah sulit harus ada di luar sana, bahkan jika kita tidak dapat mengidentifikasinya.
Secara historis, para peneliti belum memikirkan proses mencari masalah keras sebagai masalah pencarian yang sendiri dapat dianalisis secara matematis. Pendekatan papadimitriou, yang mengelompokkan proses itu dengan masalah pencarian lain yang terhubung dengan prinsip pigeonhole kosong, memiliki karakteristik rasa referensi diri dari banyak pekerjaan terbaru Dalam teori kompleksitas – ia menawarkan cara baru untuk bernalar tentang kesulitan membuktikan kesulitan komputasi.
“Anda menganalisis tugas teori kompleksitas menggunakan teori kompleksitas,” kata Kartu Oliverseorang peneliti di Columbia.
Korten adalah calon siswa yang dengannya Papadimitriou telah membahas prinsip-prinsip pigeonhole yang kosong tepat sebelum pandemi. Dia datang ke Columbia untuk bekerja dengan papadimitriou, dan di tahun pertamanya di sekolah pascasarjana dia membuktikan bahwa pencarian masalah komputasi yang sulit adalah terkait erat dengan semua masalah lain di Apepp. Dalam arti matematika tertentu, kemajuan apa pun pada masalah yang satu ini akan secara otomatis diterjemahkan menjadi kemajuan pada sejumlah orang lain yang telah lama dipelajari oleh para ilmuwan komputer dan ahli matematika, seperti pencarian Jaringan yang tidak memiliki substruktur sederhana.
Makalah Korten segera menarik perhatian dari peneliti lain. “Saya cukup terkejut ketika melihatnya,” kata Rahul Santhanamahli teori kompleksitas di University of Oxford. “Ini sangat menarik.” Dia dan yang lainnya telah membangun di atas terobosan Korten untuk membuktikan a kebingungan dari baru Hasil tentang koneksi antara kesulitan komputasi dan keacakan.
“Ada kekayaan luar biasa untuk ini,” kata Papadimitriou. “Ini masuk ke tulang masalah penting dalam kompleksitas.”
Cerita asli dicetak ulang dengan izin dari Berapa banyak majalah, publikasi editorial independen dari Yayasan Simons yang misinya adalah untuk meningkatkan pemahaman publik tentang sains dengan meliput perkembangan penelitian dan tren matematika dan ilmu fisik dan kehidupan.
