Teknologi pemecah SAT yang kuat dapat bekerja dengan hipotesis Collatz yang terkenal. Namun, kemungkinannya tidak terlalu tinggi.
Dalam beberapa tahun terakhir, Mariin Hijul telah menggunakan teknologi pencarian bukti terkomputerisasi yang disebut pemecah SAT (SAT untuk kepuasan) untuk menaklukkan daftar masalah matematika yang mengesankan. Kembar tiga Pythagoras pada tahun 2016, Schur nomor 5 pada tahun 2017, dan baru-baru ini hipotesis Keller dalam dimensi ketujuh, yang kami tulis belum lama ini dalam artikel " Penelusuran komputer membantu menangani masalah matematika berusia 90 tahun ".
Namun, sekarang, Hijul, seorang ilmuwan komputer di Universitas Carnegie Mellon, telah mengarahkan pandangannya pada tujuan yang lebih ambisius: dugaan Collatz, yang dianggap oleh banyak orang sebagai masalah terbuka yang paling sulit dalam matematika (dan bisa dibilang yang paling sederhana untuk dirumuskan). Matematikawan lain, mengetahui dari saya bahwa Khiyul melakukan upaya seperti itu, merasa skeptis tentang hal itu.
“Saya tidak melihat bagaimana masalah ini dapat diselesaikan sepenuhnya dengan pemecah SAT,” kata Thomas Hales dari University of Pittsburgh, pakar terkemuka dalam bukti komputer. Teknologi ini pada dasarnya membantu matematikawan memecahkan masalah - beberapa di antaranya memiliki jumlah pilihan yang tak terbatas - dengan mengubahnya menjadi masalah diskrit dan terbatas.
Namun, Hales, seperti yang lainnya, juga berhati-hati dalam meremehkan Khiyul. “Dia sangat pandai menemukan cara cerdas untuk merumuskan masalah dalam bahasa SAT. Dia sangat pandai dalam hal itu. "
Scott Aaronsondari University of Texas di Austin, bekerja dengan Hiyul pada dugaan Collatz, menambahkan: “Marin adalah seorang pria dengan palu, yaitu, pemecah SAT, dan mungkin pembawa palu ini yang paling layak di dunia. Dan dia mencoba menerapkannya pada hampir semua hal. " Tapi hanya waktu yang akan menjawab apakah dia bisa mengubah hipotesis Collatz menjadi paku.
Solusi SAT memerlukan perumusan ulang masalah dalam bahasa yang dapat dimengerti komputer yang menggunakan logika proposisional , dan kemudian menghubungkan komputer untuk memutuskan apakah ada cara untuk membuat pernyataan tersebut benar. Berikut contoh sederhananya.
Katakanlah Anda adalah orang tua yang mencoba mengatur pengasuhan anak. Salah satu pengasuh Anda boleh bekerja sepanjang minggu kecuali Selasa dan Kamis. Yang lainnya selain hari Selasa dan Jumat. Ketiga - kecuali Kamis dan Jumat. Anda perlu duduk bersama anak Anda pada hari Selasa, Kamis, dan Jumat. Bisakah ini dicapai?
Salah satu cara untuk mengujinya adalah dengan mengubah kendala pengasuh menjadi rumus dan memberikannya ke pemecah SAT. Program ini akan mencari cara untuk membagikan hari-hari di antara para pengasuh sehingga rumusnya ternyata benar, atau "puas" - yaitu, sehingga Anda mendapatkan tiga hari yang Anda butuhkan. Jika berhasil, metode seperti itu akan ada.
Sayangnya, tidak segera jelas bagaimana merumuskan kembali banyak pertanyaan matematika yang paling penting ke dalam bahasa SAT. Tetapi terkadang mereka dapat diutarakan kembali sebagai pertanyaan kepuasan dengan cara yang tidak terduga.
“Sulit untuk memprediksi kapan tugas akan dikurangi menjadi komputasi yang besar namun terbatas,” kata Aaronson.
Dugaan Collatz adalah salah satu pertanyaan matematika yang pada awalnya tidak tampak seperti masalah pengasuh sama sekali. Dia menyarankan hal berikut: ambil nomor apa pun (integer, bukan nol). Jika ganjil, kalikan dengan 3 dan tambahkan 1. Jika genap, bagi dengan 2. Hasilnya, Anda mendapatkan angka baru. Terapkan aturan yang sama untuk itu dan lanjutkan. Hipotesis memprediksi bahwa terlepas dari angka awal, Anda berakhir dengan 1, dan kemudian Anda terjebak dalam lingkaran: 1, 4, 2, 1.
Dan, terlepas dari fakta bahwa hipotesis ini telah dikerjakan selama hampir 100 tahun, para ahli matematika belum bisa membuktikannya.
Tapi ini tidak menghentikan Khiyul. Pada tahun 2018, ia dan Aronson - saat menjadi rekan universitas - menerima hibah dari National Science Foundation untuk menerapkan pemecah SAT pada dugaan Collatz.
Ambil nomor berapa saja. Jika ganjil, kalikan dengan 3 dan tambahkan 1. Jika ganjil, bagi dengan 2. Hasilnya, Anda mendapatkan angka baru. Terapkan aturan yang sama untuk itu dan lanjutkan. Dapatkah Anda menemukan angka yang tidak mengarah ke 1? Anda bisa mencobanya sendiri .
Pertama-tama, Aaronson, seorang ilmuwan komputer, mengajukan rumusan alternatif dari hipotesis Collatz, yang disebut. Sebuah "sistem aturan substitusi" yang memudahkan komputer untuk bekerja.
Dalam sistem aturan substitusi, Anda bekerja dengan sekumpulan karakter, seperti huruf A, B, dan C. Anda menggunakannya untuk membentuk urutan: ACACBACB. Anda juga memiliki aturan untuk mengubah urutan ini. Satu aturan mungkin mengatakan bahwa ketika Anda bertemu AC, Anda menggantinya dengan BC. Orang lain bisa mengganti pesawat dengan AAA. Anda dapat menentukan sejumlah aturan yang menentukan transformasi apa pun.
Ilmuwan komputer umumnya perlu tahu apakah JV tertentu selalu berakhir. Artinya, terlepas dari baris mana untuk memulai dan dalam urutan apa untuk menerapkan aturan, apakah benar bahwa baris pada akhirnya akan berubah menjadi keadaan di mana tidak ada aturan yang dapat diterapkan?
Aaronson menemukan SP dengan tujuh simbol dan 11 aturan, mirip dengan hipotesis Collatz. Jika mereka dapat membuktikan bahwa JV-nya selalu selesai, mereka akan membuktikan bahwa hipotesisnya benar.
Untuk mengubah dugaan Collatz menjadi masalah pemecah SAT, Aaronson dan Hiyul harus mengambil langkah lain yang melibatkan matriks, atau deretan angka. Mereka perlu menetapkan matriks unik untuk setiap simbol di SP mereka. Pendekatan ini - cara umum untuk mencari bukti bahwa SP sedang menyelesaikan pekerjaan - akan memungkinkan mereka untuk bernalar tentang transformasi bilangan melalui perkalian matriks. Tujuh matriks yang menunjukkan tujuh simbol dengan SP harus memenuhi seluruh rangkaian kendala, yang mencerminkan korespondensi 11 aturan satu sama lain.
"Pertama, Anda mencoba menemukan matriks yang memenuhi batasan ini," kataEmre Yolchu , seorang mahasiswa PhD di Carnegie Mellon University, menangani masalah ini dengan Hijul. “Jika Anda berhasil, Anda membuktikan bahwa eksekusi berhenti,” dan karena itu hipotesis Collatz benar.
Pemecah SAT dapat menjawab pertanyaan tentang keberadaan matriks yang memenuhi batasan ini. Aaronson dan Hijul pertama kali menjalankan pemecah SAT pada matriks 2x2 kecil. Mereka tidak menemukan pilihan kerja. Kemudian mereka mencoba matriks 3x3. Dan lagi-lagi tidak berhasil. Mereka terus meningkatkan ukuran matriks dengan harapan dapat ditemukan.
Namun, pendekatan ini tidak dapat berkembang tanpa batas, karena kompleksitas pencarian matriks yang sesuai tumbuh secara eksponensial seiring dengan ukurannya. Hijul menyarankan bahwa komputer modern tidak dapat menangani matriks yang lebih besar dari 12x12.
“Ketika matriks menjadi terlalu rumit, Anda tidak bisa menyelesaikan masalah,” katanya.
Hijul masih bekerja untuk mengoptimalkan pencarian, mencoba membuatnya lebih efisien sehingga pemecah SAT dapat memeriksa matriks yang lebih besar dan lebih besar. Dia dan rekan-rekannya sedang mengerjakan sebuah artikel yang merangkum penemuan mereka saat ini, tetapi mereka hampir kehabisan ide dan mungkin harus segera menyerah - setidaknya untuk sementara.
Lagipula, daya tarik dari pemecah SAT adalah jika Anda hanya dapat mengetahui cara memeriksa kasus lain, menelepon pengasuh lain, memperpanjang pencarian meskipun hanya sebentar, Anda mungkin dapat menemukan apa yang Anda cari. Dalam hal ini, keuntungan utama Khiyul mungkin bukan pengalamannya dengan pemecah SAT, tetapi cintanya untuk mengejar hasil.
“Saya hanya seorang yang optimis,” katanya. "Saya sering merasa beruntung, jadi saya hanya mencoba dan melihat seberapa jauh saya bisa mendapatkannya."