Masalah Terumit Matematika Berhasil Dipecahkan Setelah 30 Tahun

KOMPAS.com - Seorang ahli matematika asal Emory University, Atlanta berhasil memecahkan masalah matematika paling rumit yang telah menjadi misteri selama 30 tahun.

Misteri yang dimaksud adalah Dugaan Sensitivitas. Salah satu masalah terpenting sekaligus paling membingungkan dalam ilmu komputer teoretis selama hampir tiga dekade.

Adalah Hao Huang, asisten profesor matematika yang membuktikan Dugaan Sensitivitas ada, dengan sangat inovatif dan sederhana dalam acara Konferensi Internasional tentang Struktur dan Algoritma Acak di Zurich, Swiss, 15-19 Juli 2019 lalu.

Baca juga: Kisah Deepmind, AI Terbaik Google yang Gagal Ujian Matematika SMA

Dugaan Sensitivitas secara simpel mengubah input ke fungsi, tanpa mengubah output. Di sinilah kenapa disebut sensitivitas.

Sejak Dugaan Sensitivitas diusulkan untuk kali pertama, tanpa pembuktian saat itu. Para ahli komputer teoretis menyadari, Dugaan Sensitivitas berimplikasi besar untuk menentukan cara paling efisien dalam memproses informasi.

Para ahli lain sangat mengapresiasi Huang karena ia tak hanya berhasil membuktikan Dugaan Sensitivitas, tapi juga bagaimana cara Huang melakukan pembuktian dengan sederhana dan mudah dimengerti.

Bukti Dugaan Sensitivitas dari Huang memang belum secara resmi diterbitkan dalam jurnal matematika mana pun. Namun, setelah Huang memublikasikan bukti ini pada 1 Juli 2019, para ahli lain dapat menerima hal ini.

"Setiap kali ada ahli membuktikan tentang hal ini, sekitar 99 persen pembuktiannya salah atau terlalu rumit. Namun, bukti (Huang) ini berbeda. Saya yakin bahwa pembuktiannya benar. Mengapa? Karena saya sudah membaca dan memahaminya, hanya butuh waktu sekitar setengah jam," ungkap ahli komputer dari University of Texas di Austin Scott Aaronson dalam blognya seperti dilansir Live Science, Selasa (31/7/2019).

Baca juga: Para Ilmuwan Ajari Lebah Matematika, Ini Kisahnya

Ryan O'Donnell, seorang profesor ilmu komputer yang mempelajari teori bilangan di Universitas Carnegie Mellon di Pittsburgh, menunjukkan bahwa bukti Huang dapat diringkas dalam satu twit berikut:

Hao Huang@Emory:

Ex.1: ∃edge-signing of n-cube with 2^{n-1} eigs each of +/-sqrt(n)

Interlacing=>Any induced subgraph with >2^{n-1} vtcs has max eig >= sqrt(n)

Ex.2: In subgraph, max eig <= max valency, even with signs

Hence [GL92] the Sensitivity Conj, s(f) >= sqrt(deg(f))

— Ryan O'Donnell (@BooleanAnalysis) July 1, 2019