Apakah masalah magic square yang setengah terisi NP-complete?

Inilah masalahnya:

Kami memiliki kotak dengan beberapa angka dari 1..N di beberapa sel. Itu diperlukan untuk menentukan apakah itu bisa diselesaikan ke kotak ajaib.

Contoh:

2 _ 6       2 7 6
_ 5 1  >>>  9 5 1
4 3 _       4 3 8

7 _ _ 
9 _ _  >>>  NO SOLUTION 
8 _ _

Apakah ini masalah NP-complete? Jika ya, bagaimana saya bisa membuktikannya?

Crosspost di MS

Mengisi kotak Latin yang terisi sebagian adalah NP-Complete. "Kompleksitas menyelesaikan kotak Latin parsial" Charles J. Colbourn. Matematika Terapan Diskrit, Volume 8, Edisi 1, April 1984, Halaman 25-30 http://dx.doi.org/10.1016/0166-218X(84)90075-1

Bisakah masalah kotak Latin diubah menjadi masalah kotak ajaib melalui aritmatika modular? Intuisi saya mengatakan ya, tetapi sisa otak saya mengatakan, "Kembalilah ke penilaian!"

Pertanyaan ini memiliki dua bagian: pertama, apakah masalah dalam NP, dan kedua, apakah NP-keras?

Untuk bagian pertama, saya punya jawaban positif dengan bukti yang tidak jelas. (Terima kasih kepada Suresh karena menunjukkan kesalahan sebelumnya.)

Pertimbangkan cara berikut untuk memformalkan pertanyaan sebagai masalah keputusan:

TERIKAT MAGIC KOTAK PENYELESAIAN
Input: bilangan bulat positif diberikan dalam unary, daftar bilangan bulat dengan posisi mereka dalam n oleh n jaringan Pertanyaan: lakukan di sana ada bilangan bulat untuk posisi yang tersisa di grid, sehingga bentuk-bentuk pengaturan sebuah sihir persegi ?$n$$n$$n$

Jika kita menambahkan batasan bahwa masing-masing bilangan bulat harus terjadi tepat sekali di kotak ajaib, maka masalah keputusan penyelesaian MAGIC SQUARE COMPLETION jelas dalam NP. The definisi sihir persegi di 1911 Encyclopædia Britannica , berikut Euler$1,2,\dots,n^2$ , memiliki pembatasan ini; Sebaliknya, artikel Wikipedia saat ini menggunakan terminologi "kotak ajaib normal" dan cadangan "kotak ajaib" untuk versi tidak terbatas.

Dengan oleh n grid, setidaknya n nomor harus diberikan, jika jawabannya adalah sepele "YES" untuk versi terbatas. Karena itu ukuran input dapat diasumsikan membutuhkan lebih dari n bit dalam kasus ini. Untuk versi normal, ada kemungkinan bahwa ada input yang memerlukan beberapa bit tetapi tidak memiliki solusi; untuk menghindari komplikasi seperti itu saya telah menetapkan bahwa n diberikan dalam unary.$n$$n$$n$$n$$n$

Argumen ini menggunakan batasan pada kemungkinan ukuran bilangan bulat yang muncul dalam solusi. Dalam kasus normal, ikatan ini jelas , tetapi dalam kasus umum tidak jelas apriori bahwa ikatan seperti itu ada. Ternyata ada ikatan eksponensial.$n^2$

Teorema ( Tyszka, Teorema 12 ): Setiap sistem persamaan Diophantine yang melibatkan persamaan bentuk dan x i = x j + x k , untuk i , j , k ∈ { 1 , 2 , … , n } , baik tidak memiliki solusi integer, atau memiliki solusi di mana setiap x i adalah integer dan paling banyak $x_i = 1$$x_i = x_j + x_k$$i,j,k \in \{1,2,\dots,n\}$$x_i$dalam nilai absolut.$\sqrt{5}^{n-1}$

Ini juga muncul sebagai Teorema 4.7 dalam:

• Apoloniusz Tyszka, Dua dugaan tentang aritmatika dalam R dan C , Matematika. Catatan. Kuart. 56 175–184, 2010.

$2^n$$2^{n-1}$

$x_i = 1$$x_i = x_j + x_k$$i,j,k \in \{1,2,\dots,n\}$$x_i$$2^n$

$2^{n-1}$

Ini menghasilkan sebagai berikut:

$N$$2^{O(N^2)}$

$O(N^4)$$O(N^8)$$n^2 + 2(n+1)(n-2)+1 = 3n^2-2n-3$$n-2$ variables for partial sums for each row, column, and diagonal and a grand total variable linking these together. Beyond the magic square itself, a further polynomial number of variables is required for the numbers in the square: a number requiring $m$ bits can be represented by using $O(m^2)$ intermediate variables.

For the second part of the question, as far as I can tell either version of MAGIC SQUARE COMPLETION should be NP-hard, but I do not have reductions. It is worth noting that there are procedures to construct normal magic squares of arbitrarily large size; moreover, the number of normal magic squares seems to grow superpolynomially with $n$ (see OEIS A006052) so the underlying language does not seem to be sparse.

Using Papadimitriou's bound on the solutions of an instance of INTEGER LINEAR PROGRAMMING, one can also show that the version where the numbers must all be non-negative is also in NP.

Theorem (Papadimitriou): Let $A$ be an $r \times s$ matrix and $b$ an $r$-vector, both with entries from $\{-a, -a+1, \dots, a-1, a\}$. Then if $Ax = b$ has a solution in non-negative integers, it also has one where every component is in $\{0,1,\dots,s(ra)^{2r+1}\}$.

The constraints forming the magic square can be expressed as a linear program using $a=1$, with $s=n^2+1$ variables and $r=2n+2$ inequalities. This yields a somewhat larger bound than the bound above where negative numbers are allowed, but the certificate is still of polynomial size. (Thanks to Tony Tan for pointing out the result of Papadimitriou.)

• Christos H. Papadimitriou, On the complexity of integer programming, JACM 28 765–768, 1981. (link)