Sebuah terobosan besar dalam memecahkan hipotesis 60 tahun ini menyoroti bagaimana keteraturan mulai muncul di dalamnya dengan pertumbuhan sistem acak.
Sebuah tim ahli matematika dan ilmuwan komputer akhirnya menunjukkan kemajuan dalam penyelesaian, pada pandangan pertama, tugas sederhana yang mengganggu para peneliti selama hampir enam dekade.
Tugas ini, yang ditetapkan oleh matematikawan Pal Erdös dan Richard Rado pada tahun 1960, menyangkut seberapa sering seseorang dapat mengharapkan penampilan pola yang menyerupai bunga matahari dalam set besar objek - misalnya, dalam sejumlah besar titik yang tersebar di pesawat. Meskipun
hasil baru tidak sepenuhnya menyelesaikan hipotesis Erdös dan Rado, itu mempromosikan pemahaman matematikawan dalam penampilan struktur yang sangat kompleks dalam kelompok acak. Untuk tujuan ini, tugas itu dirumuskan kembali dalam hal fungsi komputer, mengambil keuntungan dari meningkatnya hubungan antara ilmu komputer teoretis dan matematika murni.
“Dalam karya ini, ide matematika memanifestasikan dirinya dengan cara baru, yang akan menjadi ide utama zaman kita. Hasilnya sendiri luar biasa, ”kata
Gil Kalai dari Hebrew University di Jerusalem.
Hipotesis bunga matahari mengacu pada set, atau set objek. Paling mudah untuk membayangkan menggunakan contoh sekumpulan titik pada bidang xy. Pertama, pilih sejumlah poin tetap yang akan dimasukkan dalam setiap set. Kemudian buat loop acak sehingga setiap loop, atau set, menyertakan sejumlah titik yang dipilih. Loop dapat berpotongan, dan beberapa titik dapat jatuh ke dalam beberapa set, menyerupai diagram Venn.
Jika Anda menggambar banyak loop berisi banyak titik, sebagian besar dari mereka akan berpotongan dan akan menyerupai seluk-beluk tanaman merambat. Tetapi Erdös dan Rado memperkirakan bahwa struktur yang disempurnakan juga akan menghasilkan: tiga set atau lebih set akan saling berpotongan, meninggalkan subset titik yang sama di persimpangan, sementara tidak ada set ini akan berpotongan dengan set lainnya.
Jika Anda menghapus subset poin umum ini, maka tiga set akan terletak di sekitar kekosongan, dan akan sepenuhnya terpisah satu sama lain - seperti kelopak bunga di sekitar tengah gelap bunga matahari. Bunga matahari paling sederhana dianggap memiliki tiga set yang tidak bersinggungan dengan yang lain; pulau-pulau seperti itu disebut set terpisah.
Erdös dan Rado mengemukakan bahwa ketika jumlah loop meningkat, bunga matahari seperti itu pasti akan muncul, baik dalam bentuk set yang terpisah, atau dalam bentuk set yang saling bertumpukan satu sama lain dengan cara yang ditunjukkan. Hipotesis bunga matahari ini adalah bagian dari bidang matematika yang lebih umum disebut
teori Ramsey, yang mempelajari bagaimana keteraturan mulai muncul di dalamnya dengan meningkatnya ukuran sistem acak.
"Jika Anda memiliki objek matematika yang cukup besar, sebuah struktur harus disembunyikan di dalamnya," kata
Shachar Lovet dari University of California, San Diego, rekan penulis karya baru yang juga dikerjakan oleh
Ryan Alweis dari Universitas Princeton, Keven Wu dari Universitas Peking dan
Jiapeng Zhang dari Universitas Harvard.
Erdös dan Rado ingin tahu persis berapa banyak set dan ukuran apa yang dibutuhkan untuk menjamin bunga matahari. Mereka mengambil langkah sederhana pertama menuju penyelesaian masalah dengan mendefinisikan parameter w, menunjukkan jumlah poin di masing-masing set. Kemudian mereka membuktikan bahwa dibutuhkan kira-kira seperangkat ukuran w untuk memastikan bahwa bunga matahari yang terdiri dari tiga set dijamin muncul di dalamnya. Jadi, jika Anda ingin menggunakan set 100 poin, maka Anda akan membutuhkan 100 hingga
100 set untuk menjamin penampilan bunga matahari.
Pada saat yang sama, Erdös dan Rado menyarankan bahwa sebenarnya jumlah set yang menjamin bunga matahari jauh lebih sedikit daripada
ww - dan lebih seperti konstanta dalam derajat w (misalnya, 3
w atau 80
w atau 5 000 000
w ). Namun, mereka tidak dapat menemukan cara untuk membuktikan dugaan mereka.
"Mereka mengatakan bahwa tugas itu tampak sangat sederhana, dan terkejut bahwa mereka tidak dapat mencapai kemajuan di dalamnya," kata Alveys.
Dan mereka tidak sendirian. Pada periode dari hasil pertama mereka dan karya baru ini, yang muncul 60 tahun kemudian, hanya dua matematikawan yang membuat setidaknya beberapa kemajuan dalam masalah ini - dan kemudian mereka melangkah secara bertahap, mengambil satu langkah pada 1997, dan yang
kedua tahun ini .
"Semua orang sudah mencoba semua ide yang membuat orang merasa nyaman," kata
Anup Rao dari University of Washington, yang menerbitkan
karya tambahan yang menyederhanakan metode yang diperoleh dalam hasil baru. "Dan tidak ada yang bisa memperbaiki garis dasar yang ditetapkan oleh Erds dan Rado."
Tetapi bukti baru membuat terobosan besar.
Empat peneliti, termasuk matematikawan dan ilmuwan komputer, mampu melakukan ini dengan membagi tugas menjadi dua skenario yang berbeda. Yang pertama, yang lebih mudah, mereka melihat apa yang akan terjadi ketika set berpotongan secara signifikan satu sama lain, membuatnya lebih mudah untuk memahami kapan bunga matahari muncul di sana.
"Ketika Anda memiliki satu set elemen yang termasuk set yang lebih besar, Anda dapat menggunakan struktur ini," untuk mencari bunga matahari, kata Lovet.
Pada awalnya, para peneliti bertanya-tanya apakah ada satu set poin milik sebagian besar dari semua set dalam sistem. Setelah menemukan titik seperti itu, dalam pencarian mereka untuk bunga matahari, mereka membatasi diri hanya pada bagian set yang berisi set poin ini. Kemudian mereka terus bertindak dengan cara yang sama, menyempurnakan pencarian, termasuk di dalamnya semakin sedikit jumlah set sistem, yang memiliki poin lebih banyak dan lebih umum. Pemangkasan ini berlanjut sampai mereka menemukan bunga matahari mereka.
Dalam skenario kedua yang lebih kompleks, mereka menganalisis apa yang akan terjadi jika set tidak berpotongan kuat. Dalam hal ini, cara yang paling mungkin untuk mendapatkan bunga matahari adalah dengan mengambil tiga set terpisah. Namun, untuk membuktikan bahwa tiga set terpisah bersembunyi di set sedikit lebih berpotongan tidak mudah.
Di sinilah ilmu komputer ikut bermain. Dua rekan penulis, Lovet dan Zhang, telah mencoba selama beberapa tahun untuk menganalisis masalah bunga matahari menggunakan alat yang sama yang digunakan para ilmuwan komputer untuk mempelajari fungsi Boolean. Fungsi-fungsi ini melakukan operasi pada urutan bit - satu dan nol - dan menghasilkan bit tunggal pada akhirnya, sesuai dengan apakah pernyataan komputasi benar atau salah. Misalnya, fungsi Boolean dapat diprogram untuk mengembalikan 1 jika setidaknya satu dari bit input adalah 1, dan 0 jika tidak ada bit input yang 1.
Tiga tahun lalu, Lovet dan Zhang menyadari bahwa pertanyaan yang sama dapat diajukan tentang apakah ada tiga set yang terpisah di antara set yang tidak saling berpotongan kuat. Pertama, tetapkan label untuk setiap titik di set: 1 jika hanya terdapat di set ini, dan 0 dalam kasus lain. Fungsi Boolean mengembalikan 1 (benar) jika setiap titik pada input adalah 1 - artinya, setiap titik set ada secara eksklusif dalam set ini, yang membuat set ini terpisah. Hasil sebenarnya menunjukkan bahwa ada kondisi yang cocok untuk menemukan bunga matahari.
Sebagai bukti kuat korespondensi ini, para peneliti menggunakan pengetahuan luas tentang fungsi Boolean untuk menyerang masalah bunga matahari, yang sebelumnya kekurangan sumber daya. Mereka membuktikan bahwa (log w) set cukup untuk mendapatkan bunga matahari. Hasil seperti itu tidak cukup untuk membuktikan hipotesis bahwa konstanta tertentu dalam derajat w cukup untuk mendapatkan bunga matahari. Tapi ini adalah urutan besarnya hasil yang lebih baik daripada yang diperoleh Erdös dan Rado, dan kira-kira bertepatan dengan jumlah set yang mereka prediksi.
Setelah setengah abad kegagalan, pekerjaan baru menunjukkan bahwa kita akan segera melihat solusi lengkap. Ini juga meningkatkan pemahaman tentang bagaimana bentuk-bentuk khusus pasti muncul dalam sifat matematika liar peluang.