Ilmuwan Komputer Sedikit Mendekati Sasaran Algoritma Utama | Majalah Quanta

Jika seseorang meminta Anda untuk menentukan apakah dua objek itu sama, itu mungkin tampak seperti permintaan yang sepele. Dalam kebanyakan kasus sehari-hari, pandangan sekilas sudah cukup bagi Anda untuk memberikan penilaian yang akurat.

Namun dalam ilmu komputer, ini adalah pertanyaan yang jauh lebih rumit. Nyatanya, itu adalah salah satu yang memotong inti yang belum terselesaikan dari apa yang mampu dilakukan oleh komputer. Bergantung pada apa objeknya, dan bagaimana Anda mendefinisikan kesamaan, kami masih belum tahu apakah komputer dapat menjawab pertanyaan dengan cepat, atau apakah pendekatan yang lambat dan melelahkan pada dasarnya adalah yang terbaik yang dapat mereka kelola.

Selama dekade terakhir, ada beberapa hasil penting yang menunjukkan bahwa komputer setidaknya dapat melakukan sedikit lebih baik dari itu. Salah satu dari hasil terbaru terbesar dalam ilmu komputer adalah algoritma yang lebih cepat untuk menentukan kapan dua grafik sama. Karya tahun 2015, oleh Laszló Babai dari University of Chicago, mematahkan satu penghalang kecepatan komputasional yang penting tetapi tidak memenuhi yang lain.

Sekarang, makalah oleh Xiao Rui Sun dari University of Illinois, Chicago telah mempresentasikan algoritma baru yang lebih cepat untuk pertanyaan terkait yang disebut masalah isomorfisme grup, yaitu mengetahui kapan dua objek matematika yang disebut grup adalah sama. Pekerjaan, diposting online Maret lalu, mengambil langkah kecil untuk mengklarifikasi kompleksitas komputasi yang mendasari yang terlibat dalam membandingkan objek.

Pekerjaan Sun mematahkan batas kecepatan lama untuk kelas grup tertentu — yang dianggap sebagai contoh tersulit dari masalah isomorfisme grup untuk dipecahkan. Jika suatu algoritme dapat dengan cepat membandingkan grup semacam ini, harapannya adalah algoritme dapat dengan cepat membandingkan grup dari jenis apa pun.

"Kami tidak tahu teorema seperti itu, tapi kami memiliki alasan untuk percaya bahwa sesuatu seperti itu seharusnya benar," kata Josh Grochow dari Universitas Colorado, Boulder.

Membandingkan Perbandingan

Untuk menentukan apakah dua hal itu sama persis, pertama-tama Anda perlu mendefinisikan "sama". Dua rangkaian angka dapat dianggap sama jika hanya berisi digit yang sama, atau mungkin perlu memiliki digit yang sama dalam urutan yang sama.

Isomorfisme adalah jenis kesamaan tertentu yang banyak muncul dalam matematika. Ketika dua objek isomorfik satu sama lain, itu secara kasar berarti bahwa mereka mengandung elemen yang sama, dan elemen-elemen tersebut berada dalam hubungan yang sama satu sama lain.

Grafik - kumpulan simpul (titik) yang dihubungkan oleh tepi (garis) - menyediakan cara visual yang dapat diakses untuk melihat seperti apa bentuk isomorfisme. Dua graf adalah isomorfik jika Anda dapat mencocokkan simpul dalam satu graf dengan simpul pada graf lainnya, sehingga simpul yang dihubungkan oleh sisi pada graf pertama dihubungkan oleh sisi pada graf kedua. Grafik isomorfik dapat terlihat berbeda di permukaan, tetapi memiliki struktur dasar yang sama.

Grup lebih abstrak daripada grafik, tetapi masih dapat dibandingkan dengan isomorfisme. Grup adalah kumpulan elemen — seperti angka — yang dapat digabungkan satu sama lain menurut beberapa operasi sehingga hasilnya juga ada dalam kumpulan tersebut. Misalnya, Anda dapat memiliki grup yang elemennya adalah bilangan bulat — semua bilangan bulat positif dan negatif, ditambah nol — dan operasinya adalah penjumlahan: Tambahkan dua bilangan bulat apa saja, dan hasilnya selalu bilangan bulat lain.

Dua grup isomorfik jika Anda dapat memasangkan setiap elemen dalam satu grup dengan elemen di grup lain, sehingga hasil operasi pada dua elemen di grup pertama konsisten dengan hasil operasi pada nilai ekuivalen dari elemen tersebut di grup kedua. kelompok.

Berikut adalah contoh sederhana dari dua grup, masing-masing dengan dua elemen, yang isomorfik satu sama lain. Kelompok pertama terdiri dari angka 0 dan 1, dan kelompok kedua terdiri dari huruf a dan b. Kedua grup berisi operasi untuk menggabungkan elemen grup dengan cara tertentu, dengan hasil yang ditampilkan dalam tabel di bawah ini.

Grup isomorfik karena 0 berpasangan dengan a, 1 pasang dengan b, dan hubungan struktural yang dihasilkan dengan menggabungkan elemen adalah sama di kedua grup.

“Kami mengatakan dua kelompok isomorfik jika pada dasarnya setara,” kata Sun.

Kemajuan yang Tidak Seimbang

Isomorfisme adalah konsep penting dalam matematika — di mana grafik dan grup ditampilkan secara ekstensif — karena memungkinkan matematikawan untuk melihat melewati perbedaan yang dangkal dan fokus pada cara di mana objek terkait mungkin benar-benar sama. Tapi itu juga fundamental dalam ilmu komputer; peneliti tidak hanya mencari algoritme yang menentukan apakah dua objek isomorfik, tetapi juga mengukur seberapa cepat algoritme tersebut dapat berjalan.

Pengukuran itu bisa rumit. Kecepatan algoritme didasarkan pada bagaimana waktu prosesnya berubah dengan ukuran objek yang dikerjakannya. Bayangkan, misalnya, Anda memiliki dua pasang grup. Dalam satu pasangan, setiap kelompok berisi lima elemen. Di sisi lain, setiap grup berisi 10 elemen.

Anda akan mengharapkan algoritme membutuhkan lebih banyak waktu untuk menentukan apakah grup dengan lebih banyak elemen adalah isomorfik. Tapi berapa banyak waktu lagi? Apakah akan memakan waktu dua kali lebih lama? 5² lebih lama? 2⁵ lebih lama? Pertanyaan-pertanyaan itu sesuai dengan klasifikasi luas yang penting dari kecepatan algoritmik: Mereka dapat berjalan dalam waktu linier (yang berarti dalam hal ini membutuhkan waktu dua kali lebih lama), waktu polinomial (5² lebih lama) dan waktu eksponensial (2⁵ lebih lama).

Ilmuwan komputer mengetahui kategori kecepatan mana yang termasuk dalam sebagian besar pertanyaan komputasi, tetapi tidak semuanya.

“Sebagian besar [jenis pertanyaan] yang paling mudah atau paling sulit, tetapi masih ada beberapa pengecualian yang tidak diketahui,” kata Sun. Graf dan isomorfisme grup termasuk di antara pengecualian tersebut, yang membuatnya sangat menarik untuk dipelajari.

Dalam 1970s, Robert Tarjan dari Princeton University menyadari bahwa ada sebuah algoritma yang dapat menentukan apakah ada dua grup yang isomorfis dengan runtime $latex n^{{(log,n)}}$, di mana n adalah jumlah elemen dalam setiap grup. Ini disebut algoritma kuasi-polinomial-waktu, dan dalam hierarki runtime lebih baik daripada waktu eksponensial (2ⁿ) tetapi lebih buruk dari waktu polinomial (n²). Kecepatan ini kira-kira sama dengan algoritme isomorfisme graf Babai, dan ini masih yang terbaik yang dapat kami lakukan untuk grup hampir 50 tahun kemudian.

“Secara kasar berarti tidak ada kemajuan selama setengah abad,” kata Sun.

Pada saat hasil Tarjan, masalah isomorfisme grup lebih banyak dipelajari daripada versi graf. Itu terbalik hari ini, sebagian karena isomorfisme grafik telah mendorong inovasi yang menarik sementara isomorfisme grup terhenti.

“Semua alat kami sangat lambat selama bertahun-tahun, dan sulit untuk mengeksploitasi apa yang kami ketahui tentang aljabar [kelompok],” kata James Wilson dari Universitas Negeri Colorado.

Tetapi meskipun perbedaan ini sedang berlangsung, kedua masalah tersebut memiliki hubungan yang lebih dalam daripada kesamaan nama mereka: Masalah isomorfisme grup (setidaknya dalam formulasi ini) direduksi menjadi masalah isomorfisme graf. Ini berarti bahwa setiap algoritma yang dapat menyelesaikan masalah graf juga dapat menyelesaikan masalah grup dalam waktu yang sama. Kebalikannya tidak benar — kemajuan pada grup tidak menyiratkan kemajuan pada grafik. Tapi kurangnya kemajuan pada masalah grup telah membebani matematikawan yang mencari keuntungan yang sepadan pada masalah grafik. Bagaimana Anda dapat mencapai hal yang lebih sulit jika Anda tidak dapat terlebih dahulu mencapai sesuatu yang berkaitan erat dan tampaknya lebih mudah?

"Dengan kata lain," kata Sun, "untuk lebih meningkatkan isomorfisme graf, isomorfisme grup adalah hambatan besar."

Sebuah Masalah Berubah

Ketika kemajuan pada masalah macet selama itu terjadi untuk isomorfisme grup, penemuan biasanya diperlukan untuk melepaskan diri. "Bila Anda memiliki kemajuan besar, itu harus menjadi indikasi bahwa ada ide baru," kata Grochow.

Karya Sun berisi beberapa ide yang melibatkan penargetan jenis kelompok yang penting dan menemukan cara cerdas untuk memecah kelompok tersebut menjadi beberapa bagian untuk membandingkannya.

Algoritma grup Sun bekerja untuk dipanggil p-kelompok kelas 2 dan eksponen p. Mereka mirip dengan grup di mana produk dari dua elemen adalah elemen lain dan produknya tetap sama terlepas dari urutan perkaliannya. Tapi yang paling penting adalah apa yang mereka wakili untuk masalah isomorfisme grup secara keseluruhan. Grup-grup ini memiliki struktur yang sangat sederhana, artinya mereka harus mudah dibandingkan. Namun terlepas dari kesederhanaan ini, para peneliti belum menemukan cara untuk mempercepat algoritme. Sampai mereka bisa, rasanya tidak ada harapan untuk memperbaiki pertanyaan umum tentang isomorfisme grup.

Sun memulai dengan mengalihkan pengaturan dari grup ke matriks, susunan angka yang berfungsi sebagai objek dasar dalam aljabar linier. Ini dimungkinkan karena teorema dari tahun 1930-an yang disebut korespondensi Baer, ​​yang mengubah versi pertanyaan isomorfisme grup ini menjadi masalah analog yang sempurna tentang matriks. Secara khusus, Sun bekerja dengan ruang matriks, yang merupakan kumpulan matriks dengan sifat khusus: Kombinasi (linier) dari dua matriks dalam ruang sama dengan matriks lain dalam ruang.

Dengan kata lain, ruang-ruang ini sangat terstruktur seperti grup. Jadi, alih-alih mencoba memahami ketika dua kelompok isomorfik, Sun dapat mencoba memahami ketika dua ruang matriks isometrik — gagasan isomorfisme ruang matriks yang sesuai dengan kelompok.

Sun bukanlah peneliti pertama yang mengadopsi pendekatan ini, tetapi dia adalah orang pertama yang memperkenalkan langkah tambahan: membagi ruang matriks menjadi dua bagian. Satu bagian adalah inti dari ruang, di mana semua matriksnya sederhana. Bagian lainnya adalah ruang yang mengelilingi inti itu, di mana semua matriksnya sangat kompleks. Langkah ini sesuai dengan pemisahan grup menjadi subgrup yang hanya berisi sebagian dari total elemen.

Sun kemudian menerapkan metode algoritmik yang berbeda untuk masing-masing bagian ini. Inti memiliki struktur yang sederhana, jadi dia menggunakan karakterisasi struktur untuk merepresentasikannya dengan cara yang lebih terorganisir. Lapisan luar lebih kompleks, jadi tidak ada cara cepat untuk membandingkannya dengan yang lain. Alih-alih, metode Sun mengambil pendekatan yang disebut individualisasi dan penyempurnaan untuk mengesampingkan sebagian besar cara yang mungkin untuk memetakan satu lapisan luar ke lapisan lain dan kemudian menggunakan komputer untuk bekerja melalui semua cara yang tersisa untuk menentukan apakah ada pencocokan isomorfik.

Metode ini serupa dengan cara Anda memecahkan teka-teki sudoku. Ada beberapa kotak yang nilai potensialnya dibatasi oleh apa yang sudah Anda ketahui (inti dari ruang matriks), memungkinkan Anda untuk mengisinya dengan cepat. Lalu ada yang lain (lapisan luar) yang memiliki kendala lebih sedikit, tetapi Anda dapat mencari tahu hanya dengan mencoba semua nilai yang mungkin — dan selama tidak terlalu banyak kotak semacam ini, Anda masih dapat memecahkan teka-teki di jumlah waktu yang wajar.

“Saya mengisi semua hal yang dengan cepat saya katakan dapat dibatasi, dan sekarang saya mungkin akan kembali dan mencoba hati saya pada kotak yang hilang,” kata Wilson. “Jika Anda mempersempit ruang lingkup, sekarang saat yang tepat untuk mengganti persneling dan menggunakan komputer untuk mencari nilai yang tepat.”

Terobosan Sun menunjukkan bahwa selalu mungkin untuk melakukan pemisahan ini untuk ruang matriks yang sesuai p-kelompok kelas 2 dan eksponen p. Dia kemudian membuktikan bahwa setelah pemisahan seperti itu, kombinasi teknik algoritme memungkinkan untuk menentukan apakah dua ruang isomorfik dalam $lateks n^{{(log,n)}^{5/6}}$ waktu, nilai yang sedikit lebih rendah dari metode $latex n^{{(log,n)}}$ Tarjan. (Kedua algoritme juga menyertakan istilah konstanta, yang tidak berpengaruh besar pada runtime, dan yang kami tinggalkan untuk kejelasan.)

Hasilnya tidak menentukan isomorfisme kelompok kategori kecepatan mana yang termasuk; itu masih di suatu tempat antara waktu eksponensial dan polinomial. Tapi Sun telah mendorongnya sedikit lebih dekat ke sisi polinomial, dan ada alasan untuk percaya lebih dari itu seharusnya mungkin. Lagi pula, karyanya memberi para ilmuwan komputer algoritme isomorfisme grup yang lebih cepat untuk jenis grup yang paling sulit, meningkatkan kemungkinan bahwa percepatan serupa dapat dijangkau oleh semua jenis grup.

“Jika kamu bisa menyelesaikannya p-groups, mungkin Anda bisa menyelesaikan semuanya, ”kata Grochow. "Mungkin."