Mengungkap Rahasia Keterbatasan Matematika di Balik Masalah Sulit Komputer

Masalah dalam ilmu komputer yang disebut traveling salesperson problem sangat terkenal karena kesulitannya. Para ilmuwan selama lebih dari 50 tahun mencoba membuktikan secara matematis bahwa masalah ini memang susah diselesaikan secara cepat, namun belum berhasil. Metamatematika adalah cabang ilmu yang mencoba mengkaji proses pembuktian matematika itu sendiri, dari asumsi dasar yang digunakan sampai hasil yang diperoleh. Lijie Chen mulai mempelajari metamatematika saat menyelesaikan doktoralnya dan menemukan ide baru menghubungkan dua teorema dalam teori kompleksitas melalui pendekatan reverse mathematics. Pendekatan ini membalik cara pembuktian biasa, yaitu dengan memasukkan teorema sebagai aksioma lalu membuktikan aksioma tersebut. Mereka bekerja dengan kerangka aksioma PV1 yang lebih lemah dari biasanya untuk memudahkan pemetaan hubungan teorema. Salah satu yang mereka buktikan adalah hubungan ekuivalen antara prinsip pigeonhole dan batas bawah komunikasi dalam masalah equality problem, di mana pemain harus menentukan apakah dua string identik dengan mengirim pesan seminimal mungkin. Hasil ini menakjubkan karena memperlihatkan keterkaitan erat antara konsep menghitung sederhana dengan batasan teoretis komunikasi dalam komputer. Selain itu, mereka menemukan bahwa batas waktu pengolahan untuk memeriksa apakah string sebuah palindrome pada mesin Turing satu pita juga memiliki hubungan yang sangat erat dengan prinsip pigeonhole dalam sistem aksioma PV1. Hal ini mengejutkan karena kedua teorema ini tampak berbeda tetapi secara logika saling terkait kuat. Hasil-hasil ini membuka wawasan bahwa banyak teorema dalam teori kompleksitas yang selama ini dianggap rumit sebenarnya memiliki hubungan mendalam yang bisa dipelajari melalui metamatematika. Ini juga menunjukkan bahwa sistem aksioma saat ini memiliki batasan tertentu sehingga penemuan baru sangat dibutuhkan untuk mencapai kemajuan dalam memahami kompleksitas komputasi.