- Terungkap bahwa teori himpunan deskriptif, bidang teknis yang meneliti struktur himpunan tak hingga, dapat ditafsirkan ulang dalam bahasa algoritme
- Matematikawan Anton Bernshteyn membuktikan bahwa masalah pada graf tak hingga dapat ditulis ulang sebagai masalah komunikasi pada jaringan komputer
- Keterkaitan ini menunjukkan hubungan korespondensi antara measurability dan efisiensi algoritme terdistribusi
- Para peneliti kini menggunakan jembatan ini untuk saling mengonversi teorema dan masalah dari kedua bidang dan menghasilkan temuan baru
- Penemuan ini mendefinisikan ulang batas antara tak hingga dan komputasi, serta memperluas kemungkinan kolaborasi antara matematika dan ilmu komputer
Pendahuluan: teori himpunan dan dunia tak hingga
- Fondasi matematika modern bertumpu pada teori himpunan, dan sebagian besar matematikawan menangani masalah dengan asumsi tersebut
- Namun, ahli teori himpunan deskriptif (descriptive set theorists) adalah kelompok kecil peneliti yang terus mengeksplorasi hakikat himpunan tak hingga
- Pada 2023, Anton Bernshteyn menemukan keterkaitan mendalam antara teori himpunan deskriptif dan ilmu komputer
- Ia menunjukkan bahwa persoalan pada himpunan tak hingga tertentu dapat diubah menjadi masalah komunikasi pada jaringan komputer
- Hasil ini dinilai sebagai jembatan yang menghubungkan bahasa yang tampak berlawanan: logika dan algoritme, serta tak hingga dan hingga
Latar belakang teori himpunan deskriptif
- Asal-usul teori himpunan bermula dari penelitian Georg Cantor, yang membuktikan adanya ukuran tak hingga yang berbeda-beda
- Konsep untuk menyatakan ukuran himpunan mencakup kardinalitas (cardinality) dan ukuran (measure)
- Contoh: himpunan bilangan real pada interval 0~1 dan himpunan bilangan real pada interval 0~10 memiliki kardinalitas yang sama, tetapi ukurannya masing-masing 1 dan 10
- Teori himpunan deskriptif membedakan himpunan terukur dan himpunan tak terukur, lalu mengelompokkannya ke dalam hierarki kompleksitas (hierarchy)
- Hierarki ini menjadi patokan untuk memilih alat yang tepat di bidang matematika lain, seperti teori probabilitas, sistem dinamis, dan teori grup
Graf tak hingga dan masalah pewarnaan
- Bernshteyn meneliti graf tak hingga, dengan memodelkan node dan sisi setiap graf sebagai struktur yang terhubung tanpa batas
- Contoh: jika titik-titik pada lingkaran dihubungkan dengan jarak tertentu, maka pada jarak rasional akan terbentuk loop tertutup, sedangkan pada jarak irasional akan terbentuk struktur terhubung tak hingga
- Ketika node graf diwarnai dengan dua warna, hal itu bisa dilakukan menggunakan aksioma pilihan (axiom of choice), tetapi menghasilkan himpunan tak terukur
- Sebaliknya, jika menggunakan metode pewarnaan kontinu, dibutuhkan tiga warna tetapi diperoleh himpunan terukur
- Perbedaan ini berperan sebagai faktor kunci yang menentukan posisi dalam hierarki kompleksitas teori himpunan
Pertemuan dengan algoritme terdistribusi
- Pada 2019, Bernshteyn menghadiri kuliah ilmu komputer tentang algoritme terdistribusi (distributed algorithms) dan menemukan kemiripan
- Contoh: masalah memilih frekuensi (warna) yang berbeda agar router Wi-Fi tidak saling mengganggu
- Setiap node menentukan warnanya dengan algoritme lokal (local algorithm) yang hanya berkomunikasi dengan node tetangga
- Dua warna tidak efisien, tetapi jika tiga warna diizinkan, masalah dapat diselesaikan secara efisien
- Bernshteyn menyadari bahwa ambang jumlah warna (threshold) ini identik dengan ambang pada masalah pewarnaan terukur dalam teori himpunan deskriptif
Bukti kesetaraan dua dunia
- Bernshteyn secara matematis membuktikan kesetaraan antara algoritme lokal yang efisien ↔ metode pewarnaan terukur
- Pada graf berhingga, setiap node dapat diberi nomor unik, tetapi pada graf tak hingga tak terhitung (uncountable) hal itu tidak mungkin
- Ia merancang metode pelabelan yang tidak bertumpang tindih antar node bertetangga, sehingga algoritme dapat diperluas ke graf tak hingga
- Hasilnya, terbukti bahwa “setiap algoritme lokal berkorespondensi dengan metode pewarnaan terukur dalam teori himpunan deskriptif”
- Ini menunjukkan keterkaitan matematis yang mendalam antara komputabilitas dan keterdefinisian (definability)
Perluasan riset dan penerapan
- Václav Rozhoň dan lainnya menggunakan keterkaitan ini untuk menyelesaikan masalah pewarnaan graf pohon (tree) dan menurunkan alat penelitian untuk sistem dinamis
- Sebaliknya, ada pula riset yang memakai metode teori himpunan untuk meningkatkan estimasi tingkat kesulitan masalah
- Jembatan ini melampaui sekadar alat penyelesaian masalah, dan turut berkontribusi pada penataan ulang sistem klasifikasi teori himpunan
- Para ahli teori himpunan deskriptif kini dapat merapikan masalah yang belum terklasifikasi dengan merujuk pada cara klasifikasi sistematis dalam ilmu komputer
- Bernshteyn berharap riset ini menjadi momentum untuk membuat konsep tak hingga dipandang sebagai bagian nyata dari matematika praktis
Belum ada komentar.