Angka 15 Menjelaskan Batas Rahasia dari Grid Tak Terbatas

Sebagai seorang sarjana di University of Chile, Bernardo Subercaseaux mengambil pandangan redup menggunakan komputer untuk melakukan matematika. Tampaknya bertentangan dengan penemuan intelektual yang nyata.

“Ada beberapa insting atau reaksi naluriah yang menentang penggunaan komputer untuk memecahkan masalah Anda, seperti bertentangan dengan kecantikan ideal atau keanggunan argumen yang fantastis,” katanya.

Namun kemudian di tahun 2020 Subercaseaux jatuh cinta, dan seperti yang sering terjadi, prioritasnya berubah. Objek obsesinya adalah pertanyaan yang dilihatnya di forum online. Sebagian besar masalah dia pindai dan lupakan, tetapi yang satu ini menarik perhatiannya. Dia menggesek ke kanan.

“Hal pertama yang saya lakukan adalah menyukai posting di grup Facebook, berharap mendapat pemberitahuan nanti ketika orang lain memposting solusi,” katanya.

Pertanyaannya adalah tentang mengisi kotak tak terbatas dengan angka. Ternyata, itu bukan jenis masalah yang dipecahkan oleh seekor burung. Untuk melakukannya, Subercaseaux harus meninggalkan Chili untuk sekolah pascasarjana di Universitas Carnegie Mellon.

Di sana, pada Agustus 2021, dia bertemu secara kebetulan Marijn Heule, seorang ilmuwan komputer yang menggunakan daya komputasi besar-besaran untuk menyelesaikan soal-soal matematika yang sulit. Subercaseaux bertanya kepada Heule apakah dia ingin mencoba masalah tersebut, memulai kolaborasi yang mencapai puncaknya pada bulan Januari ini sebuah bukti yang dapat dijumlahkan dengan satu angka: 15.

Setiap Cara yang Mungkin

Dalam 2002, Wayne Goddard dari Clemson University dan beberapa ahli matematika yang berpikiran sama sedang meludahi masalah dalam kombinatorik, mencoba untuk membuat putaran baru pada pertanyaan andalan lapangan tentang mewarnai peta dengan batasan tertentu.

Akhirnya mereka sampai pada masalah yang dimulai dengan kisi-kisi, seperti selembar kertas grafik yang berlangsung selamanya. Tujuannya adalah untuk mengisinya dengan angka. Hanya ada satu kendala: Jarak antara setiap kemunculan angka yang sama harus lebih besar dari angka itu sendiri. (Jarak diukur dengan menjumlahkan jarak vertikal dan horizontal, sebuah metrik yang dikenal sebagai jarak "taksi" karena menyerupai pergerakan di jalanan kota berjaringan.) Sepasang 1 tidak dapat menempati sel yang bersebelahan, yang memiliki jarak taksi 1, tetapi mereka dapat ditempatkan di sel diagonal langsung, yang memiliki jarak 2.

Awalnya, Goddard dan kolaboratornya ingin tahu apakah mungkin untuk mengisi kisi tak terbatas dengan kumpulan angka yang terbatas. Tetapi pada saat dia dan empat kolaboratornya menerbitkan masalah "pewarnaan pengepakan" ini dalam jurnal Kombinasi Ars pada tahun 2008, mereka telah membuktikan bahwa itu dapat diselesaikan dengan menggunakan 22 angka. Mereka juga tahu bahwa tidak mungkin diselesaikan hanya dengan lima angka. Itu berarti jawaban sebenarnya untuk masalah tersebut - jumlah minimum angka yang dibutuhkan - terletak di antara keduanya.

Para peneliti tidak benar-benar memenuhi grid yang tak terbatas. Mereka tidak perlu melakukannya. Alih-alih, cukup mengambil subset kecil dari kisi — katakanlah persegi 10 kali 10 — isi dengan angka, lalu tunjukkan bahwa salinan subset yang diisi dapat ditempatkan bersebelahan, seperti cara Anda menutupi lantai dengan salinan ubin.

Ketika Subercaseaux pertama kali mengetahui masalah tersebut, dia mulai mencari ubin menggunakan pena dan kertas. Dia akan membuat sketsa kisi-kisi angka, mencoretnya, mencoba lagi. Dia segera bosan dengan pendekatan itu, dan dia meminta seorang teman untuk merancang alat berbasis web yang mirip dengan game Minesweeper dan memungkinkannya untuk menguji kombinasi lebih cepat. Setelah beberapa minggu bekerja, dia meyakinkan dirinya sendiri bahwa tidak ada cara untuk mengemas kotak dengan delapan angka, tetapi dia tidak bisa lebih jauh dari itu - ada terlalu banyak bentuk potensial yang bisa diambil oleh ubin, dan terlalu banyak cara yang berbeda mereka bisa diisi dengan angka.

Masalahnya, seperti yang akan menjadi jelas nanti, adalah jauh lebih sulit untuk menunjukkan bahwa grid tidak dapat dicakup oleh sekumpulan angka tertentu daripada menunjukkan bahwa itu bisa. “Ini tidak hanya menunjukkan bahwa satu cara tidak berhasil, ini menunjukkan bahwa setiap cara yang mungkin tidak berhasil,” kata Goddard.

Setelah Subercaseaux memulai di CMU dan meyakinkan Heule untuk bekerja dengannya, mereka dengan cepat menemukan cara untuk menutup grid dengan 15 angka. Mereka juga mampu mengesampingkan kemungkinan penyelesaian soal hanya dengan 12 angka. Tetapi perasaan kemenangan mereka berumur pendek, karena mereka menyadari bahwa mereka hanya mereproduksi hasil yang telah ada sejak lama: Sejauh tahun 2017, para peneliti telah mengetahui jawabannya tidak kurang dari 13 atau lebih besar dari 15 .

Untuk seorang mahasiswa pascasarjana tahun pertama yang telah mengikat seorang profesor besar untuk mengerjakan masalah hewan peliharaannya, itu adalah penemuan yang meresahkan. “Saya merasa ngeri. Saya pada dasarnya telah mengerjakan suatu masalah selama beberapa bulan tanpa menyadarinya, dan lebih buruk lagi, saya telah membuat Marijn membuang waktunya untuk itu!” Sub-kasus menulis dalam posting blog rekap pekerjaan mereka.

Heule, bagaimanapun, menemukan penemuan hasil masa lalu yang menyegarkan. Ini menunjukkan bahwa peneliti lain menemukan masalah yang cukup penting untuk dikerjakan, dan menegaskan baginya bahwa satu-satunya hasil yang layak diperoleh adalah menyelesaikan masalah secara tuntas.

“Begitu kami mengetahui bahwa sudah ada 20 tahun pengerjaan masalah, itu benar-benar mengubah gambarannya,” katanya.

Menghindari Vulgar

Selama bertahun-tahun, Heule berkarir dengan menemukan cara yang efisien untuk mencari di antara banyak kemungkinan kombinasi. Pendekatannya disebut pemecahan SAT - kependekan dari "kepuasan". Ini melibatkan pembuatan rumus panjang, yang disebut rumus Boolean, yang dapat memiliki dua kemungkinan hasil: 0 atau 1. Jika hasilnya 1, rumusnya benar, dan masalahnya terpenuhi.

Untuk masalah pewarnaan kemasan, setiap variabel dalam rumus dapat mewakili apakah sel tertentu ditempati oleh nomor tertentu. Komputer mencari cara untuk menetapkan variabel agar memenuhi rumus. Jika komputer dapat melakukannya, Anda tahu bahwa mungkin untuk mengemas kisi-kisi di bawah kondisi yang telah Anda atur.

Sayangnya, pengkodean langsung dari masalah pewarnaan kemasan sebagai rumus Boolean dapat meluas hingga jutaan istilah - komputer, atau bahkan armada komputer, dapat berjalan selamanya menguji semua cara berbeda dalam menetapkan variabel di dalamnya.

"Mencoba melakukan kekerasan ini akan memakan waktu sampai alam semesta berakhir jika Anda melakukannya dengan naif," kata Goddard. “Jadi, Anda memerlukan beberapa penyederhanaan yang keren untuk membawanya ke sesuatu yang bahkan mungkin.”

Selain itu, setiap kali Anda menambahkan nomor ke masalah pewarnaan kemasan, itu menjadi sekitar 100 kali lebih sulit, karena kemungkinan kombinasinya berlipat ganda. Ini berarti bahwa jika bank komputer yang bekerja secara paralel dapat mengesampingkan 12 dalam satu hari perhitungan, mereka membutuhkan waktu perhitungan 100 hari untuk mengesampingkan 13.

Heule dan Subercaseaux menganggap peningkatan pendekatan komputasi brute-force sebagai sesuatu yang vulgar. “Kami memiliki beberapa ide yang menjanjikan, jadi kami mengambil pola pikir 'Mari coba optimalkan pendekatan kami hingga kami dapat menyelesaikan masalah ini dalam waktu kurang dari 48 jam komputasi di cluster,'” kata Subercaseaux.

Untuk melakukan itu, mereka harus menemukan cara untuk membatasi jumlah kombinasi yang harus dicoba oleh cluster komputasi.

“[Mereka] ingin tidak hanya menyelesaikannya, tetapi menyelesaikannya dengan cara yang mengesankan,” kata Alexander Soifer dari Universitas Colorado, Colorado Springs.

Heule dan Subercaseaux mengakui bahwa banyak kombinasi pada dasarnya sama. Jika Anda mencoba mengisi petak berbentuk wajik dengan delapan angka berbeda, tidak masalah jika angka pertama yang Anda tempatkan adalah satu di atas dan satu di kanan kotak tengah, atau satu di bawah dan satu di kiri alun-alun tengah. Kedua penempatan itu simetris satu sama lain dan membatasi langkah Anda selanjutnya dengan cara yang persis sama, jadi tidak ada alasan untuk memeriksa keduanya.

Heule dan Subercaseaux menambahkan aturan yang memungkinkan komputer memperlakukan kombinasi simetris sebagai ekuivalen, mengurangi total waktu pencarian dengan faktor delapan. Mereka juga menggunakan teknik yang telah dikembangkan Heule dalam karya sebelumnya yang disebut kubus dan taklukkan, yang memungkinkan mereka menguji lebih banyak kombinasi secara paralel satu sama lain. Jika Anda mengetahui sel tertentu harus berisi 3, 5, atau 7, Anda dapat membagi masalahnya dan menguji masing-masing dari tiga kemungkinan secara bersamaan pada perangkat komputer yang berbeda.

Pada Januari 2022 perbaikan ini memungkinkan Heule dan Subercaseaux mengesampingkan 13 sebagai jawaban untuk masalah pewarnaan kemasan dalam percobaan yang membutuhkan waktu komputasi kurang dari dua hari. Ini membuat mereka memiliki dua kemungkinan jawaban: 14 atau 15.

Nilai Tambah Besar

Untuk mengesampingkan 14 — dan menyelesaikan masalah — Heule dan Subercaseaux harus menemukan cara tambahan untuk mempercepat pencarian komputer.

Awalnya, mereka telah menulis rumus Boolean yang menugaskan variabel ke setiap sel individu dalam kisi. Namun pada September 2022, mereka menyadari bahwa mereka tidak perlu melanjutkan berdasarkan sel demi sel. Sebaliknya, mereka menemukan bahwa lebih efektif untuk mempertimbangkan daerah kecil yang terdiri dari lima sel dalam bentuk tanda tambah.

Mereka menulis ulang rumus Boolean mereka sehingga beberapa variabel mewakili pertanyaan seperti: Apakah ada angka 7 di suatu tempat dalam wilayah berbentuk plus ini? Komputer tidak perlu mengidentifikasi dengan tepat di wilayah mana 7 mungkin berada. Itu hanya perlu menentukan apakah itu ada di sana atau tidak - sebuah pertanyaan yang membutuhkan sumber daya komputasi yang jauh lebih sedikit untuk dijawab.

“Memiliki variabel yang hanya berbicara tentang plus daripada lokasi tertentu ternyata jauh lebih baik daripada membicarakannya di sel tertentu,” kata Heule.

Dibantu oleh efisiensi pencarian plus, Heule dan Subercaseaux mengesampingkan 14 dalam percobaan komputer pada November 2022 yang akhirnya membutuhkan waktu lebih sedikit untuk dijalankan daripada yang mereka gunakan untuk mengesampingkan 13. Mereka menghabiskan empat bulan berikutnya untuk memverifikasi bahwa kesimpulan komputer itu benar — hampir sebanyak waktu yang mereka habiskan untuk memungkinkan komputer sampai pada kesimpulan itu sejak awal.

“Sungguh menyenangkan untuk berpikir bahwa apa yang kami munculkan sebagai semacam pertanyaan sampingan di beberapa jurnal acak telah menyebabkan sekelompok orang menghabiskan, ternyata, waktu berbulan-bulan mereka mencoba mencari cara untuk menyelesaikannya,” Goddard dikatakan.

Bagi Subercaseaux, itu adalah kemenangan nyata pertama dalam karir penelitiannya. Dan meskipun itu mungkin bukan jenis penemuan yang dia idealkan ketika dia pertama kali berpikir untuk bekerja dalam matematika, dia menemukan bahwa pada akhirnya, itu memiliki penghargaan intelektualnya sendiri.

“Itu bukan pemahaman tentang formulir di mana Anda memberi saya papan tulis dan saya bisa menunjukkan mengapa itu 15,” katanya. “Tapi kami telah mendapatkan pemahaman tentang bagaimana batasan masalah beroperasi, betapa lebih baik memiliki 6 di sini atau 7 di sana. Kami telah memperoleh banyak pemahaman intuitif.”