Masalah algoritmik yang kelihatannya dipermudah oleh teorema

Saya mencari contoh yang bagus, di mana fenomena berikut terjadi: (1) Masalah algoritmik terlihat sulit, jika Anda ingin menyelesaikannya bekerja dari definisi dan hanya menggunakan hasil standar. (2) Di sisi lain, itu menjadi mudah, jika Anda tahu beberapa teorema (tidak begitu standar).

Tujuan dari ini adalah untuk menggambarkan bagi siswa bahwa belajar lebih banyak teorema dapat berguna, bahkan bagi mereka yang berada di luar bidang teori (seperti insinyur perangkat lunak, insinyur komputer dll). Berikut ini sebuah contoh:

Pertanyaan: Diberikan bilangan bulat , apakah ada grafik -vertex (dan jika demikian, temukan satu), sehingga konektivitas verteksnya adalah , konektivitas tepinya adalah , dan derajat minimumnya adalah ?n k l $n, k, l, d$$n$$k$$l$$d$

Perhatikan bahwa kami mengharuskan parameter sama persis dengan angka yang diberikan, mereka bukan hanya batas. Jika Anda ingin menyelesaikan ini dari awal, ini mungkin terlihat agak sulit. Di sisi lain, jika Anda terbiasa dengan teorema berikut (lihat Teori Grafik Ekstrimal oleh B. Bollobas), situasinya menjadi sangat berbeda.

Teorema: Biarkan menjadi bilangan bulat. Ada grafik -vertex dengan konektivitas vertex , konektivitas edge , dan derajat minimum , jika dan hanya jika salah satu dari kondisi berikut dipenuhi:n k l $n, k, l, d$$n$$k$$l$$d$

• $0\leq k\leq l \leq d <\lfloor n/2 \rfloor$ ,
• $1\leq 2d+2-n\leq k\leq l = d< n-1$
• $k=l=d=n-1.$

Kondisi ini sangat mudah untuk diperiksa, karena merupakan ketidaksetaraan sederhana di antara parameter input, sehingga pertanyaan keberadaan dapat dijawab dengan mudah. Lebih jauh, bukti teorema itu konstruktif, juga menyelesaikan masalah konstruksi. Di sisi lain, hasil ini tampaknya tidak cukup standar, sehingga Anda dapat mengharapkan semua orang mengetahuinya.

Bisakah Anda memberikan contoh lebih lanjut dalam semangat ini, di mana mengetahui teorema (yang tidak terlalu standar) sangat menyederhanakan tugas?

Memutuskan isomorfisma kelompok sederhana , yang diberikan oleh tabel perkaliannya. Fakta bahwa ini dapat dilakukan dalam waktu polinomial mengikuti langsung dari kenyataan bahwa semua grup sederhana hingga dapat dihasilkan oleh paling banyak 2 elemen, dan saat ini satu-satunya bukti fakta yang diketahui menggunakan Klasifikasi Grup Sederhana Hingga (mungkin teorema terbesar) - dalam hal penulis, makalah, dan halaman - pernah terbukti).

Jika saya memahami pertanyaan Anda dengan benar, contoh kanonik akan memutuskan apakah grafik memiliki sirkuit Euler: setara dengan memeriksa bahwa terhubung dan setiap simpul memiliki derajat genap.$G$$G$

Sore ini saya membaca Stringology - teori string "Nyata" .

Masalah: Jika dan adalah dua string lebih dari beberapa alfabet ketika ada beberapa bilangan bulat positif sehingga .$x$$y$$m, n$$x^m = y^n$

Teorema: Ada bilangan bulat positif sehingga jika dan hanya jika .$m,n$$x^m = y^n$$xy = yx$

Menemukan jumlah akar nyata (berbeda) dari polinomial nyata, baik dalam semua ℝ atau dalam interval yang diberikan. Teorema Sturm memberi tahu Anda bahwa urutan polinomial yang memenuhi sejumlah kecil persyaratan dapat digunakan untuk menghitung jumlah akar polinomial nyata dengan koefisien nyata.

Kemudian, yang harus Anda lakukan adalah membangun urutan seperti itu (yang tidak terlalu sulit, tetapi memerlukan beberapa kasus tepi dan penanganan kasus polinomial yang tidak dapat dipisahkan), dan Bob adalah paman Anda.

Anehnya, sedikit orang yang tahu tentang hasil ini, meskipun sudah cukup tua (1829). Ini digunakan di banyak Sistem Aljabar Komputer, tetapi semua profesor matematika di universitas saya yang saya tanyakan tidak tahu Teorema Sturm sama sekali atau mereka hanya tahu namanya dan itu ada hubungannya dengan akar polinomial.

Sebagian besar orang cukup terkejut ketika Anda memberi tahu mereka bahwa menghitung akar sebenarnya adalah mudah dan tidak memerlukan pendekatan apa pun, mengingat menemukan akar jauh lebih sulit. (Ingat bahwa untuk polinomial derajat ≥ 5, bahkan tidak ada formula yang “tepat” untuk akar)

Teorema: Setiap grafik planar memiliki simpul dengan derajat paling banyak 5.

Masalah: Desain representasi dari grafik planar di mana kita dapat memeriksa apakah merupakan keunggulan dalam waktu .$O(n)$$(u, v)$$O(1)$

Kita dapat menghapus simpul dengan derajat paling banyak 5, dan menambahkannya ke daftar sebagai kunci dan tetangganya sebagai nilai. Grafik yang tersisa juga planar dan memiliki simpul dengan derajat paling banyak 5. Jadi ruang yang dikonsumsi paling banyak . Kita dapat memeriksa apakah ada dalam daftar adjacency dari ; jika tidak kita dapat memeriksa apakah ada dalam daftar adjacency . Ini membutuhkan paling banyak langkah.$5n$$u$$v$$v$$u$$10$

Saya pikir anak posterch untuk kategori ini, setidaknya sejauh menyangkut kesulitan asimetri, adalah masalah berikut:

Diberikan grafik planar , apakah 4-colourable?$G$$G$

The Four warna Teorema menyederhanakan algoritma untuk return true.

Apakah polinomial nyata (multivariat) dapat dinyatakan sebagai jumlah kuadrat dari polinomial nyata dapat diselesaikan dengan mereduksi ke pemrograman semi-pasti. Perlu tahu SDP dan SDP itu bisa diselesaikan secara efisien.$p$

Contoh lain: diberi grafik tidak terarah, apakah ada pemotongan minimum di mana semua ujungnya terpisah? Jika demikian, temukan satu.

Pada pandangan pertama ini mungkin tampak sulit. Namun, menjadi mudah jika Anda mengetahui hasil bahwa grafik -vertex yang tidak terarah dapat memiliki paling banyak pemotongan minimum , dan semuanya dapat dicantumkan dalam waktu polinomial.$n$$n(n-1)/2$

Hal ini dapat diperluas ke hampir pemotongan minimum, yang lebih besar dari pemotongan minimum, tetapi paling banyak dengan faktor konstan. Jumlah mereka masih terikat oleh polinomial.

(Saya tidak mencari referensi, ingatan saya adalah bahwa hasil ini karena D. Karger.)

Masalah: Satifsiabilitas formula MSO (logika orde dua monadik) atas kata-kata hingga.

Teorema: MSO setara dengan automata terbatas atas kata-kata terbatas.

Di atas dapat diangkat ke kata-kata tak terbatas, pohon terbatas, pohon tak terbatas.

Contoh yang sedikit lebih rumit: faktorisasi matriks nonnegatif , ketika peringkat nonnegatif konstan.

Katakanlah saya memberi Anda matriks bersama dengan janji bahwa ada negatif , sedemikian rupa sehingga . Masalahnya adalah untuk menemukan faktorisasi tersebut untuk .$A \in M_{m \times n}$$U \in M_{m \times k}$$V \in M_{k \times n}$$A = UV$$A$

Dengan beberapa baris aljabar linier elementer, Anda dapat mengurangi masalah untuk menyelesaikan sistem ketidaksetaraan polinomial dalam variabel , di mana adalah peringkat non negatif dari matriks yang ingin Anda faktor.$O(r^2)$$r$

Menggunakan algoritma Renegar ini sebagai palu, maka Anda dapat memecahkan masalah ini dalam waktu dan karenanya memulihkan dan . Ini tidak jauh dari optimalitas, karena sangat sulit untuk menyelesaikan NMF dalam waktu .$(mn)^{O(r^2)}$$U$$V$$(mn)^{o(r)}$

Decisional Diffie Hellman

Ini menyatakan: diberikan mana adalah beberapa generator dari grup siklik , verifikasi jika$(g, g^a, g^b, g^c)$$g$$\mathbb{G}$$g^c = g^{ab}$

Di bawah asumsi standar kekerasan dari masalah log diskrit, masalah ini mungkin juga tampak sulit.

Namun, dengan peta bilinear masalah ini mudah dan dapat diverifikasi sebagai

di mana$e: \mathbb{G} \times \mathbb{G} \rightarrow \mathbb{G}_T$

Lebih lanjut tentang ini dapat dibaca pada Masalah diffie-hellman decisional , Boneh'98 atau pencarian google pada Pairings

(Sepele) keberadaan Ekuilibrium Nash dalam permainan terbatas, angka genap Hamiltonian Paths dalam grafik kubik, berbagai jenis titik tetap, perbandingan seimbang dalam pesanan parsial, dan banyak masalah PPAD lainnya.

Menemukan potongan kecil. Dengan diberi grafik berbobot dan dua simpul , cari sedemikian sehingga dan tidak terhubung di , sehingga berat total adalah dimaksimalkan.$((V, E), s, t)$$E' \subset E$$s$$t$$(V, E')$$E'$

Dengan teorema max-flow / min-cut, ini mengurangi untuk menemukan aliran maksimum dari ke in . Masalah ini tidak sepele, tetapi ide yang cukup sederhana berhasil: jika kita dapat meningkatkan aliran di sepanjang beberapa jalur - , lakukanlah. Bagian yang sulit adalah memilih jalur mana yang akan ditambah dengan cara yang menemukan aliran maksimum dengan cepat.$s$$t$$(V, E)$$s$$t$

Berikut adalah contoh lain: diberi grafik sederhana yang tidak terarah, putuskan apakah ia memiliki dua sirkuit titik-terputus-putus.

Seseorang dapat secara alami mencoba membangun algoritma rekursif, dengan mengurangi grafik menjadi lebih kecil. Ini dapat dilakukan dengan mudah, selama grafik memiliki simpul dengan derajat . Namun, jika grafik dicapai dengan derajat minimum , maka tampaknya sulit untuk mengetahui bagaimana melanjutkan, kecuali Anda tahu teorema berikut (yang berasal dari dua makalah, yang diterbitkan secara independen oleh L. Lovasz dan G. Dirac di 1965):$\leq 2$$\geq 3$

Dalil. Jika grafik sederhana dengan derajat minimum tidak memiliki dua sirkuit titik-disjoint, maka grafik hanya dapat menjadi salah satu dari tiga jenis berikut: (1) , (2) grafik roda, (3) , dengan kemungkinan semua tepi ditambahkan ke kelas 3-simpul.K 5 K 3 , n - $\geq 3$$K_5$$K_{3,n-3}$

Karena mudah untuk memeriksa apakah grafik adalah salah satu grafik yang diizinkan oleh Teorema, ini memberi kita algoritma waktu polinomial untuk masalah keputusan.

Catatan: (1) Bukti teorema sama sekali tidak mudah. (2) Setelah kami memutuskan bahwa ada dua sirkuit terpisah, tampaknya kurang jelas bagaimana menyelesaikan masalah pencarian yang terkait , yaitu, bagaimana sebenarnya menemukan sirkuit tersebut. Teorema tidak memberikan saran langsung untuk itu.

contoh yang kurang rumit: ada beberapa sifat seperti teorema yang menunjukkan bahwa algoritma serakah untuk beberapa masalah adalah optimal. itu tidak begitu jelas bagi yang belum tahu pohon spanning minimum dapat ditemukan oleh algoritma serakah. agak mirip secara konseptual adalah algoritma Dijkstra untuk menemukan jalur terpendek dalam grafik. sebenarnya dalam kedua kasus "teorema" yang terkait hampir sama dengan algoritma.

Temukan urutan angka Fibonacci yang merupakan produk dari angka Fibonacci lainnya. Sebagai contoh, angka Fibonacci 8 berada dalam urutan karena 8 = 2 * 2 * 2, dan 2 adalah angka Fibonacci yang tidak sama dengan 8. Angka Fibonacci 144 ada dalam urutan karena 144 = 3 * 3 * 2 * 2 * 2 * 2, dan keduanya 2 dan 3 adalah angka Fibonacci yang tidak sama dengan 144.

Teorema Carmichael menyiratkan bahwa 8 dan 144 adalah satu-satunya istilah dari urutan ini.