Le problème du carré magique à moitié rempli est-il complet?

Voici le problème:

Nous avons un carré avec des nombres de 1..N dans certaines cellules. Il est nécessaire de déterminer s'il peut être complété par un carré magique.

Exemples:

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

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

Ce problème est-il NP-complet? Si oui, comment puis-je le prouver?

Crosspost sur MS

Remplir un carré latin partiellement rempli est NP-Complete. "La complexité de compléter des carrés latins partiels" Charles J. Colbourn. Mathématiques appliquées discrètes, volume 8, numéro 1, avril 1984, pages 25-30 http://dx.doi.org/10.1016/0166-218X(84)90075-1

Un problème de carré latin peut-il être transformé en problème de carré magique via une arithmétique modulaire? Mon intuition dit oui, mais le reste de mon cerveau dit "Reviens au classement!"

Cette question comporte deux parties: premièrement, le problème est-il dans NP, et deuxièmement, est-il NP-difficile?

Pour la première partie, j'ai une réponse positive avec une preuve non évidente. (Merci à Suresh d'avoir signalé une erreur antérieure.)

Considérez la manière suivante pour formaliser la question en tant que problème de décision:

ACHÈVEMENT DE CARRÉ MAGIQUE SANS RESTRICTION
Entrée: entier positif donné en unaire, liste des nombres entiers avec leurs positions dans une grille n par n Question: existe-t-il des nombres entiers pour les positions restantes dans la grille, de sorte que l'agencement forme un carré magique ?$n$$n$$n$

$1,2,\dots,n^2$

$n$$n$$n$$n$$n$

$n^2$

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

Cela est également apparu comme Théorème 4.7 dans:

• Apoloniusz Tyszka, Deux conjectures sur l'arithmétique en R et C , Math. Journal. Litre. 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}$

Cela donne les résultats suivants:

$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$$m$$O(m^2)$

$n$

En utilisant la limite de Papadimitriou sur les solutions d'une instance de PROGRAMMATION LINÉAIRE ENTIÈRE, on peut également montrer que la version où les nombres doivent tous être non négatifs est également en NP.

$A$$r \times s$$b$$r$$\{-a, -a+1, \dots, a-1, a\}$$Ax = b$$\{0,1,\dots,s(ra)^{2r+1}\}$

$a=1$$s=n^2+1$$r=2n+2$

• Christos H. Papadimitriou, Sur la complexité de la programmation entière , JACM 28 765–768, 1981. ( lien )