Memecahkan persamaan linear diophantine sekitar

Pertimbangkan masalah berikut:

Input : hyperplane $H = \{ \mathbf{y} \in \mathbb{R}^n: \mathbf{a}^T\mathbf{y} = {b}\}$ , diberikan oleh vektor dan dalam representasi biner standar .$\mathbf{a} \in \mathbb{Z}^n$$b \in \mathbb{Z}$

Output :$\mathbf{x} \in \mathbb{Z}^n = \arg \min d( \mathbf{x}, H)$

Dalam notasi di atas untuk \ mathbf {x} \ in \ mathbb {R} ^ n dan S \ subseteq \ mathbb {R} ^ n didefinisikan sebagai d (\ mathbf {x} , S) = \ min _ {\ mathbf {y} \ dalam S} {\ | \ mathbf {x} - \ mathbf {y}} \ | _2 , yaitu jarak euclidean alami antara set titik dan satu titik .$d(\mathbf{x}, S)$$\mathbf{x} \in \mathbb{R}^n$$S \subseteq \mathbb{R}^n$$d(\mathbf{x}, S) = \min_{\mathbf{y} \in S}{\|\mathbf{x} - \mathbf{y}}\|_2$

Dengan kata lain, kami diberi hyperplane dan kami sedang mencari titik di kisi integer yang paling dekat dengan hyperplane.

Pertanyaannya adalah:

Apa kompleksitas masalah ini?

Perhatikan bahwa waktu polinomial di sini akan berarti polinomial dalam bitsize input. Sejauh yang saya bisa lihat masalah ini menarik bahkan dalam dua dimensi. Maka tidak sulit untuk melihat bahwa itu cukup untuk mempertimbangkan hanya solusi-solusi tersebut $(x_1, x_2)$ dengan $0\leq x_1 \leq |a_1|/\mathsf{gcd}(a_1, a_2)$ tetapi itu adalah banyak pilihan superpolynomially .

Masalah yang berkaitan erat adalah memecahkan persamaan linear diophantine, yaitu menemukan $\mathbf{x} \in \mathbb{Z}^n$ sedemikian rupa sehingga $\mathbf{a}^T\mathbf{x} = b$ atau menentukan bahwa tidak ada seperti itu $\mathbf{x}$ ada. Jadi, menyelesaikan persamaan linear diophantine setara dengan menentukan apakah ada solusi nilai 0 untuk masalah yang saya definisikan di atas. Persamaan diophantine linier dapat diselesaikan dalam waktu polinomial; bahkan sistem persamaan linear diophantine dapat diselesaikan dalam waktu polinomial dengan menghitung bentuk Smith normal dari matriks $\mathbf{A}$ memberikan sistem. Ada algoritma waktu polinomial yang menghitung bentuk normal Smith dari matriks integer, yang pertama diberikan olehKannan dan Bachem .

Untuk mendapatkan intuisi tentang persamaan linear diophantine kita dapat mempertimbangkan kasus dua dimensi lagi. Jelas, tidak ada solusi yang tepat jika tidak membagi . Jika memang membagi , maka Anda dapat menjalankan algoritme GCD yang diperluas untuk mendapatkan dua angka dan sehingga dan set dan . Sekarang Anda dapat melihat perbedaan versi perkiraan: ketika tidak membagi , bagaimana kita menemukan bilangan bulatg c d ( a 1 , a 2 ) b b s t a 1 s + a 2 t = g c d ( a 1 , a 2 ) x 1 = s b / g c d ( a 1 , a 2 ) x 2 = t b / g c d ( a 1$\mathsf{gcd}(a_1, a_2)$$b$$b$$s$$t$$a_1s + a_2t = \mathsf{gcd}(a_1, a_2)$$x_1 = sb/\mathsf{gcd}(a_1, a_2)$$x_2 = tb/\mathsf{gcd}(a_1, a_2)$$\mathsf{gcd}(a_1, a_2)$$b$$x_1, x_2$sedemikian rupa sehingga jarak antara dan garis diminimalkan?$(x_1, x_2)$$a_1x_1 + a_2x_2 =b$

Masalahnya bagi saya terdengar sedikit seperti masalah vektor terdekat dalam kisi-kisi, tapi saya tidak melihat pengurangan yang jelas dari salah satu masalah ke yang lain.

Baiklah, setelah memikirkannya lebih lanjut, saya yakin saya memiliki pengurangan eksplisit dari masalah ini menjadi GCD yang diperluas; Saya akan menjelaskannya dalam kasus , tapi saya percaya bahwa itu meluas ke arbitrary . Perhatikan bahwa temuan ini merupakan yang meminimalkan jarak ke hyperplane tersebut, tetapi belum tentu terkecil (sebenarnya ada jauh lebih banyak nilai-nilai yang mencapai jarak minimum yang sama) - Saya percaya masalah yang terakhir adalah juga layak, tetapi belum memberikan pemikiran nyata. Algoritma ini didasarkan pada beberapa prinsip sederhana:$n=2$$n$ $\mathbf{x}$$\mathbf{x}$

• Jika , maka himpunan nilai diambil oleh tepatnya ; lebih jauh, nilai dan dengan dapat ditemukan secara efisien (ini persis dengan algoritma Euclidean yang diperluas).$g=\mathrm{GCD}(a_1, a_2)$$\mathbf{a}\cdot\mathbf{x} = a_1 x_1 + a_2 x_2$$\left\{0, \pm g, \pm 2g, \pm 3g, \ldots\right\}$$x_1$$x_2$$a_1 x_1 + a_2 x_2 = g$
• Jarak minimum dari hyperplane ke titik pada kisi adalah jarak minimal dari titik pada kisi ke hyperplane (jelas, tetapi merupakan inversi masalah yang berguna).
• Jarak dari titik tertentu ke hyperplane sebanding dengan(khususnya kali nilai ini - tetapi karena mengalikan semua jarak dengan nilai ini tidak berpengaruh pada lokasi minimum, kita dapat mengabaikan faktor normalisasi).$\mathbf{x}$$\mathbf{a}\cdot\mathbf{y} = b$$\left|\mathbf{a}\cdot\mathbf{x}-b\right|$$1/|\mathbf{a}|$

Ini menyarankan prosedur berikut:

• Hitung , bersama dengan sedemikian rupa sehingga .$g=\mathrm{GCD}(a_1,a_2)$$x^0_1, x^0_2$$a_1x^0_1+a_2x^0_2 = g$
• Hitung dan hitung ; adalah jarak minimal (skala) dari kisi ke hyperplane. Mari kita berupa atau ( , kecuali merupakan kelipatan dari ) tergantung mana yang mencapai jarak minimal.$r = \left\lfloor{b\over g}\right\rfloor$$d =\min(b-rg, (r+1)g-b)$$d$$s$$r$$r+1$$=\left\lceil{b\over g}\right\rceil$$b$$g$
• Hitung dan ; maka adalah kelipatan terdekat dari ke , dan dengan demikianmencapai minimum jarak ini di atas semua titik kisi.$x_1 = sx^0_1$$x_2 = s x^0_2$$\mathbf{a}\cdot\mathbf{x} = sg$$g$$b$$\left|\mathbf{a}\cdot\mathbf{x}-b\right|$

Sejauh yang saya tahu, prosedur yang sama persis harus bekerja dengan benar dalam dimensi arbitrer; kuncinya adalah bahwa GCD dimensi masih memenuhi identitas Bezout, dan untuk menemukan jarak minimum ke titik kisi, Anda hanya perlu menemukan kelipatan terdekat hingga .$n$$g$$b$