Fri. Jun 24th, 2022

SEBUAH TIM DARImatematikawan akhirnya menyelesaikan dugaan Keller, tetapi tidak dengan mengerjakannya sendiri. Sebaliknya, mereka mengajarkan armada komputer untuk melakukannya untuk mereka.

Dugaan Keller, yang diajukan 90 tahun lalu oleh Ott-Heinrich Keller, adalah masalah tentang menutupi ruang dengan ubin yang identik. Ini menegaskan bahwa jika Anda menutupi ruang dua dimensi dengan ubin persegi dua dimensi, setidaknya dua ubin harus berbagi tepi. Itu membuat prediksi yang sama untuk ruang setiap dimensi bahwa dalam menutupi, katakanlah, ruang 12 dimensi menggunakan ubin “persegi” 12 dimensi, Anda akan mendapatkan setidaknya dua ubin yang berbatasan persis satu sama lain.

Selama bertahun-tahun, matematikawan telah menghilangkan dugaan, membuktikannya benar untuk beberapa dimensi dan salah untuk yang lain. Pada musim gugur yang lalu, pertanyaan itu tetap tidak terpecahkan hanya untuk ruang tujuh dimensi.

Tetapi bukti baru yang dihasilkan komputer akhirnya menyelesaikan masalah. Buktinya, diposting online Oktober lalu, adalah contoh terbaru tentang bagaimana kecerdikan manusia, dikombinasikan dengan kekuatan komputasi mentah, dapat menjawab beberapa masalah paling menjengkelkan dalam matematika.

Baca juga di informasikita untuk mendapatkan informasi tentang teknologi terbaru sesuai dengan keinginan anda.

Penulis karya baru Joshua Brakensiek dari Universitas Stanford, Marijn Heule dan John Mackey dari Universitas Carnegie Mellon, dan David Narváez dari Institut Teknologi Rochester memecahkan masalah dengan menggunakan 40 komputer. Setelah hanya 30 menit, mesin menghasilkan jawaban satu kata: Ya, dugaan itu benar dalam tujuh dimensi. Dan kita tidak harus mengambil kesimpulan mereka tentang iman.

Jawabannya dikemas dengan bukti panjang yang menjelaskan mengapa itu benar. Argumen ini terlalu luas untuk dipahami oleh manusia, tetapi dapat diverifikasi oleh program komputer terpisah sebagai benar.

Dengan kata lain, bahkan jika kita tidak tahu apa yang dilakukan komputer untuk memecahkan dugaan Keller, kita dapat meyakinkan diri sendiri bahwa mereka melakukannya dengan benar.

Dimensi Ketujuh yang Misterius

Sangat mudah untuk melihat bahwa dugaan Keller benar dalam ruang dua dimensi. Ambil selembar kertas dan coba tutupi dengan kotak berukuran sama, tanpa celah di antara kotak dan tidak tumpang tindih. Anda tidak akan pergi jauh sebelum Anda menyadari bahwa setidaknya dua kotak harus berbagi keunggulan. Jika Anda memiliki balok-balok yang tergeletak di sekitarnya, mudah untuk melihat bahwa dugaan itu benar dalam ruang tiga dimensi. Pada tahun 1930, Keller menduga bahwa hubungan ini berlaku untuk ruang dan ubin yang sesuai dari dimensi apa pun.

Hasil awal mendukung prediksi Keller. Pada tahun 1940, Oskar Perron membuktikan bahwa dugaan itu benar untuk ruang dalam dimensi satu sampai enam. Tetapi lebih dari 50 tahun kemudian, generasi baru matematikawan menemukan contoh tandingan pertama untuk dugaan tersebut: Jeffrey Lagarias dan Peter Shor membuktikan bahwa dugaan itu salah dalam dimensi 10 pada tahun 1992.

Argumen sederhana menunjukkan bahwa sekali dugaan salah dalam satu dimensi, itu pasti salah di semua dimensi yang lebih tinggi. Jadi setelah Lagarias dan Shor, satu-satunya dimensi yang tidak pasti adalah tujuh, delapan dan sembilan. Pada tahun 2002, Mackey membuktikan dugaan Keller salah dalam dimensi delapan (dan karena itu juga dalam dimensi sembilan).

Yang tersisa hanya dimensi tujuh yang terbuka itu adalah dimensi tertinggi di mana dugaan itu bertahan atau dimensi terendah di mana ia gagal.

“Tidak ada yang tahu persis apa yang terjadi di sana,” kata Heule.

Hubungkan titik-titik

Ketika matematikawan memecahkan masalah selama beberapa dekade, metode mereka berubah. Perron mengerjakan enam dimensi pertama dengan pensil dan kertas, tetapi pada 1990-an, para peneliti telah belajar bagaimana menerjemahkan dugaan Keller ke dalam bentuk yang sama sekali berbeda bentuk yang memungkinkan mereka menerapkan komputer pada masalah tersebut.

Formulasi asli dari dugaan Keller adalah tentang ruang yang mulus dan berkelanjutan. Di dalam ruang itu, ada banyak cara untuk menempatkan ubin yang tidak terbatas. Tetapi komputer tidak pandai memecahkan masalah yang melibatkan opsi tak terbatas untuk mengerjakan keajaibannya, mereka membutuhkan semacam objek terbatas dan terpisah untuk dipikirkan.

Pada tahun 1990, Keresztély Corrádi dan Sándor Szabó datang dengan objek diskrit seperti itu. Mereka membuktikan bahwa Anda dapat mengajukan pertanyaan tentang objek yang setara dengan dugaan Keller—sehingga jika Anda membuktikan sesuatu tentang objek ini, Anda juga harus membuktikan dugaan Keller. Ini secara efektif mengurangi pertanyaan tentang tak terhingga menjadi masalah yang lebih mudah tentang aritmatika beberapa angka.

Berikut cara kerjanya:

Katakanlah Anda ingin memecahkan dugaan Keller di dimensi dua. Corrádi dan Szabó menemukan metode untuk melakukan ini dengan membangun apa yang mereka sebut grafik Keller.

Untuk memulai, bayangkan 16 dadu di atas meja, masing-masing diposisikan sedemikian rupa sehingga wajah dengan dua titik menghadap ke atas. (Fakta bahwa itu adalah dua titik mencerminkan fakta bahwa Anda menangani dugaan untuk dimensi dua; kita akan melihat mengapa itu 16 dadu dalam sekejap.) Sekarang warnai setiap titik menggunakan salah satu dari empat warna: merah, hijau, putih atau hitam.

Posisi titik pada satu dadu tidak dapat dipertukarkan: Pikirkan satu posisi mewakili koordinat x dan yang lainnya mewakili koordinat y . Setelah dadu diwarnai, kita akan mulai menggambar garis, atau tepi, di antara pasangan dadu jika dua kondisi terpenuhi: Dadu memiliki titik-titik di satu posisi yang berbeda warna, dan di posisi lain mereka memiliki titik-titik yang warnanya tidak hanya berbeda tetapi berpasangan, dengan merah dan hijau membentuk satu pasangan dan hitam dan putih yang lain.

Jadi, misalnya, jika satu dadu memiliki dua titik merah dan yang lain memiliki dua titik hitam, mereka tidak terhubung: Meskipun mereka memenuhi kriteria untuk satu posisi (warna berbeda), mereka tidak memenuhi kriteria untuk yang lain ( warna berpasangan). Namun, jika satu dadu berwarna merah-hitam dan yang lainnya berwarna hijau-hijau, maka mereka terhubung, karena mereka memiliki warna berpasangan di satu posisi (merah-hijau) dan warna lain di posisi lain (hitam-hijau).

Ada 16 kemungkinan cara menggunakan empat warna untuk mewarnai dua titik (itulah sebabnya kami bekerja dengan 16 dadu). Susun 16 kemungkinan di depan Anda. Hubungkan semua pasangan dadu yang sesuai dengan aturan. Sekarang untuk pertanyaan penting: Dapatkah Anda menemukan empat dadu yang semuanya terhubung satu sama lain?

Subset dadu yang terhubung sepenuhnya seperti itu disebut klik. Jika Anda dapat menemukannya, Anda telah membuktikan dugaan Keller salah di dimensi dua. Tapi Anda tidak bisa, karena itu tidak akan ada. Fakta bahwa tidak ada klik empat dadu berarti dugaan Keller benar di dimensi dua.

Dadu sebenarnya bukan ubin yang dipermasalahkan dalam dugaan Keller, tetapi Anda dapat menganggap setiap dadu mewakili ubin. Pikirkan warna yang diberikan pada titik-titik sebagai koordinat yang menempatkan dadu di ruang angkasa. Dan pikirkan keberadaan tepi sebagai deskripsi tentang bagaimana dua dadu diposisikan relatif satu sama lain.

Jika dua dadu memiliki warna yang sama persis, mereka mewakili ubin yang berada di posisi yang sama persis di ruang angkasa. Jika mereka tidak memiliki warna yang sama dan tidak ada warna berpasangan (satu dadu berwarna hitam-putih dan yang lainnya berwarna hijau-merah), mereka mewakili ubin yang sebagian tumpang tindih yang, ingat, tidak diperbolehkan di ubin. Jika dua dadu memiliki satu set warna berpasangan dan satu set dengan warna yang sama (satu merah-hitam dan yang lainnya hijau-hitam), mereka mewakili ubin yang berbagi wajah.

Terakhir, dan yang paling penting, jika mereka memiliki satu set warna berpasangan dan satu set warna lain yang hanya berbeda yaitu, jika mereka dihubungkan oleh tepi  itu berarti dadu mewakili ubin yang saling menyentuh tetapi digeser saling menjauh sedikit, sehingga wajah mereka tidak benar-benar sejajar. Ini adalah kondisi yang benar-benar ingin Anda selidiki. Dadu yang dihubungkan oleh tepi mewakili ubin yang terhubung tanpa berbagi wajah jenis susunan ubin yang diperlukan untuk menyangkal dugaan Keller.

“Mereka perlu menyentuh satu sama lain, tetapi mereka tidak dapat sepenuhnya menyentuh satu sama lain,” kata Heule.

Peningkatan

Tiga puluh tahun yang lalu, Corrádi dan Szabó membuktikan bahwa matematikawan dapat menggunakan prosedur ini untuk mengatasi dugaan Keller dalam dimensi apa pun dengan menyesuaikan parameter eksperimen. Untuk membuktikan dugaan Keller dalam tiga dimensi, Anda dapat menggunakan 216 dadu dengan tiga titik di wajahnya, dan mungkin tiga pasang warna (meskipun ada fleksibilitas dalam hal ini). Kemudian Anda akan mencari delapan dadu (2³) di antara dadu yang terhubung penuh satu sama lain menggunakan dua kondisi yang sama seperti yang kita gunakan sebelumnya.

Sebagai aturan umum, untuk membuktikan dugaan Keller dalam dimensi n, Anda menggunakan dadu dengan n titik dan mencoba menemukan klik berukuran 2 n . Anda dapat menganggap klik ini mewakili semacam “ubin super” (terdiri dari 2 n ubin yang lebih kecil) yang dapat menutupi seluruh ruang n- dimensi.

Jadi, jika Anda dapat menemukan ubin super ini (yang tidak mengandung ubin berbagi wajah), Anda dapat menggunakan salinan yang diterjemahkan, atau digeser, untuk menutupi seluruh ruang dengan ubin yang tidak berbagi wajah, sehingga menyangkal dugaan Keller.

“Jika Anda berhasil, Anda dapat menutupi seluruh ruang dengan terjemahan. Blok tanpa wajah yang sama akan meluas ke seluruh ubin, ”kata Lagarias, yang sekarang di University of Michigan.

Mackey dibantah dugaan Keller dalam dimensi delapan dengan menemukan sebuah klik dari 256 dadu (2 8 ), sehingga menjawab dugaan Keller untuk dimensi tujuh diperlukan mencari sebuah klik dari 128 dadu (2 7 ). Temukan klik itu, dan Anda telah membuktikan dugaan Keller salah di dimensi tujuh. Buktikan bahwa klik seperti itu tidak mungkin ada, di sisi lain, dan Anda telah membuktikan dugaan itu benar.

Sayangnya, menemukan klik 128 dadu adalah masalah yang sangat pelik. Dalam karya sebelumnya, para peneliti dapat menggunakan fakta bahwa dimensi delapan dan 10 dapat “difaktorkan”, dalam arti tertentu, ke dalam ruang berdimensi lebih rendah yang lebih mudah untuk dikerjakan. Tidak ada keberuntungan di sini.

“Dimensi tujuh buruk karena bilangan prima, yang berarti Anda tidak dapat membaginya menjadi benda-benda berdimensi lebih rendah,” kata Lagarias. “Jadi tidak ada pilihan selain berurusan dengan kombinatorik penuh dari grafik ini.”

Mencari kelompok berukuran 128 mungkin merupakan tugas yang sulit bagi otak manusia tanpa bantuan, tetapi itulah jenis pertanyaan yang dapat dijawab dengan baik oleh komputer terutama jika Anda memberikannya sedikit bantuan.

Bahasa Logika

Untuk mengubah pencarian klik menjadi masalah yang dapat ditangani oleh komputer, Anda memerlukan representasi masalah yang menggunakan logika proposisional. Ini adalah jenis penalaran logis yang menggabungkan serangkaian kendala.

Katakanlah Anda dan dua orang teman sedang merencanakan pesta. Anda bertiga mencoba menyusun daftar tamu, tetapi Anda memiliki minat yang agak bersaing. Mungkin Anda ingin mengundang Avery atau mengecualikan Kemba. Salah satu rekan kerja Anda ingin mengundang Kemba atau Brad atau keduanya. Coplanner Anda yang lain, dengan kapak untuk digiling, ingin meninggalkan Avery atau Brad atau keduanya. Mengingat kendala ini, Anda dapat bertanya: Apakah ada daftar tamu yang memenuhi ketiga perencana pesta?

Dalam istilah ilmu komputer, jenis pertanyaan ini dikenal sebagai masalah satisfiability. Anda menyelesaikannya dengan menggambarkannya dalam apa yang disebut rumus proposisional yang dalam hal ini terlihat seperti ini, di mana huruf A, K dan B mewakili calon tamu: (A ATAU NOT K) AND (K ATAU B) AND (NOT A ATAU TIDAK B).

Komputer mengevaluasi rumus ini dengan memasukkan 0 atau 1 untuk setiap variabel. A 0 berarti variabel itu salah, atau dimatikan, dan 1 berarti itu benar, atau dihidupkan. Jadi jika Anda memasukkan 0 untuk “A” itu berarti Avery tidak diundang, sedangkan 1 berarti dia. Ada banyak cara untuk menetapkan 1 dan 0 ke rumus sederhana ini atau membuat daftar tamu dan mungkin saja setelah menjalankannya, komputer akan menyimpulkan bahwa tidak mungkin memenuhi semua tuntutan yang bersaing. Namun, dalam kasus ini, ada dua cara untuk menetapkan 1 dan 0 yang cocok untuk semua orang: A = 1, K = 1, B = 0 (artinya mengundang Avery dan Kemba) dan A = 0, K = 0, B = 1 (artinya hanya mengundang Brad).

Program komputer yang memecahkan pernyataan logika proposisional seperti ini disebut pemecah SAT, di mana “SAT” berarti “kepuasan.” Ini mengeksplorasi setiap kombinasi variabel dan menghasilkan jawaban satu kata: YA, ada cara untuk memenuhi rumus, atau TIDAK, tidak ada.

“Anda tinggal memutuskan apakah setiap variabel benar atau salah dengan cara membuat seluruh rumus menjadi benar, dan jika Anda bisa melakukannya, rumusnya memuaskan, dan jika tidak, rumusnya tidak memuaskan,” kata Thomas Hales dari Universitas dari Pittsburgh.

Pertanyaan apakah mungkin menemukan klik berukuran 128 adalah masalah yang serupa. Itu juga dapat ditulis sebagai rumus proposisi dan dicolokkan ke pemecah SAT. Mulailah dengan sejumlah besar dadu dengan masing-masing tujuh titik dan enam kemungkinan warna. Bisakah Anda mewarnai titik-titik sedemikian rupa sehingga 128 dadu dapat dihubungkan satu sama lain sesuai dengan aturan yang ditentukan? Dengan kata lain, apakah ada cara untuk menetapkan warna yang memungkinkan klik?

Rumus proposisional yang menangkap pertanyaan tentang klik ini cukup panjang, mengandung 39.000 variabel yang berbeda. Masing-masing dapat diberikan salah satu dari dua nilai (0 atau 1). Akibatnya, jumlah kemungkinan permutasi variabel, atau cara mengatur warna pada dadu, adalah 2 39.000 angka yang sangat, sangat besar.

Untuk menjawab dugaan Keller untuk dimensi tujuh, sebuah komputer harus memeriksa setiap kombinasi itu baik mengesampingkan semuanya (artinya tidak ada klik dengan ukuran 128, dan Keller benar di dimensi tujuh) atau menemukan hanya satu yang berfungsi (artinya Keller salah).

“Jika Anda memiliki komputer yang naif, periksa semua [konfigurasi] yang mungkin, itu akan menjadi jumlah kasus 324 digit ini,” kata Mackey. Diperlukan komputer tercepat di dunia sampai akhir zaman sebelum mereka kehabisan semua kemungkinan.

Tetapi penulis karya baru ini menemukan bagaimana komputer bisa sampai pada kesimpulan yang pasti tanpa benar-benar harus memeriksa setiap kemungkinan. Efisiensi adalah kuncinya.

Efisiensi Tersembunyi

Mackey ingat hari ketika, di matanya, proyek itu benar-benar datang bersama-sama. Dia berdiri di depan papan tulis di kantornya di Universitas Carnegie Mellon mendiskusikan masalah dengan dua rekan penulisnya, Heule dan Brakensiek, ketika Heule menyarankan cara untuk menyusun pencarian sehingga dapat diselesaikan dalam waktu yang wajar.

“Ada kejeniusan intelektual yang nyata bekerja di kantor saya hari itu,” kata Mackey. “Rasanya seperti menonton Wayne Gretzky, seperti menonton LeBron James di Final NBA. Saya merinding sekarang [hanya memikirkannya].”

Ada banyak cara untuk melumasi pencarian grafik Keller tertentu. Bayangkan Anda memiliki banyak dadu di atas meja dan Anda mencoba mengatur 128 dadu dengan cara yang memenuhi aturan grafik Keller. Mungkin Anda mengatur 12 di antaranya dengan benar, tetapi Anda tidak dapat menemukan cara untuk menambahkan dadu berikutnya. Pada saat itu, Anda dapat mengesampingkan semua konfigurasi 128 dadu yang melibatkan konfigurasi awal 12 ubin yang tidak dapat dijalankan.

“Jika Anda tahu lima hal pertama yang Anda tetapkan tidak cocok satu sama lain, Anda tidak perlu melihat variabel lain, dan itu umumnya memotong banyak pencarian,” kata Shor, yang sekarang di Institut Teknologi Massachusetts.

Bentuk lain dari efisiensi melibatkan simetri. Ketika objek simetris, kita menganggapnya dalam beberapa hal sama. Kesamaan ini memungkinkan Anda untuk memahami seluruh objek hanya dengan mempelajari sebagian darinya: Sekilas setengah wajah manusia dan Anda dapat merekonstruksi seluruh wajah.

Pintasan serupa berfungsi untuk grafik Keller. Bayangkan, sekali lagi, Anda sedang menyusun dadu di atas meja. Mungkin Anda mulai dari tengah tabel dan membuat konfigurasi ke kiri. Anda meletakkan empat dadu, lalu menabrak penghalang jalan. Sekarang Anda telah mengesampingkan satu konfigurasi awal dan semua konfigurasi berdasarkan itu. Tetapi Anda juga dapat mengesampingkan bayangan cermin dari konfigurasi awal itu susunan dadu yang Anda dapatkan saat memposisikan dadu dengan cara yang sama, tetapi sebaliknya membangun ke kanan.

“Jika Anda dapat menemukan cara untuk menyelesaikan masalah kepuasan yang memperhitungkan simetri dengan cara yang cerdas, maka Anda telah membuat masalah menjadi lebih mudah,” kata Hales.

Keempat kolaborator memanfaatkan jenis efisiensi pencarian ini dengan cara baru khususnya, mereka mengotomatiskan pertimbangan tentang simetri, di mana pekerjaan sebelumnya mengandalkan matematikawan yang bekerja secara praktis dengan tangan untuk menanganinya.

Mereka akhirnya menyederhanakan pencarian untuk klik berukuran 128 sehingga alih-alih memeriksa 2 39.000 konfigurasi, pemecah SAT mereka hanya perlu mencari sekitar 1 miliar (2 30 ). Ini mengubah pencarian yang mungkin memakan waktu ribuan tahun menjadi tugas pagi. Akhirnya, setelah hanya setengah jam perhitungan, mereka mendapat jawaban.

“Komputer mengatakan tidak, jadi kami tahu dugaan itu benar,” kata Heule. Tidak ada cara untuk mewarnai 128 dadu sehingga semuanya terhubung satu sama lain, jadi dugaan Keller benar dalam dimensi tujuh: Setiap susunan ubin yang menutupi ruang pasti mencakup setidaknya dua ubin yang berbagi wajah.

Komputer sebenarnya memberikan lebih dari sekadar jawaban satu kata. Mereka mendukungnya dengan bukti panjang—berukuran 200 gigabyte membenarkan kesimpulan mereka.

Buktinya lebih dari sekadar pembacaan semua konfigurasi variabel yang diperiksa komputer. Ini adalah argumen logis yang menetapkan bahwa klik yang diinginkan tidak mungkin ada. Keempat peneliti memasukkan bukti Keller ke dalam pemeriksa bukti formal program komputer yang menelusuri logika argumen dan memastikannya berhasil.

“Anda tidak hanya memeriksa semua kasus dan tidak menemukan apa pun, Anda memeriksa semua kasus dan Anda dapat menulis bukti bahwa hal ini tidak ada,” kata Mackey. “Anda dapat menulis bukti ketidakpuasaan.”

Leave a Reply

Your email address will not be published. Required fields are marked *