Es la mitad llenos de magia problema NP-completo cuadrada?

Question

Aquí está el problema:

Tenemos una plaza con algunos números de 1..N en algunas células. Es necesario para determinar si puede ser completado a un cuadrado mágico.

Ejemplos:

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

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

Es este problema NP-completo? Si sí, ¿cómo puedo demostrarlo?

P. S.:
Sé que debería reducir uno de los conocidos NP-completo los problemas de éste para demostrar su NP-completitud. La principal cuestión que se plantea es NP-completo probleme para elegir y cómo bulbo polinomio algoritmo de reducción. Alguna idea?

Answer 1

Uno tiene que mostrar a su membresía en NP y NP-dureza.

Para NP-dureza, quizás una de las personas comentando sobre la pregunta podría proporcionar una sugerencia para que NP-completos problema uno debe reducir. (No tengo adecuados de reducción para resolver esta parte de la pregunta.)

Para ser miembro de NP, es suficiente para demostrar que si hay una solución, entonces hay algunas soluciones del polinomio tamaño en la entrada. Tal solución, entonces se puede adivinar en el polinomio espacio y comprobado en el polinomio de tiempo, así que el problema está en NP. El establecimiento de este no es tan obvio como podría parecer a primera vista.

Para evitar los casos patológicos, es común que requieren que la entrada especifica el tamaño de la $n \times n$ cuadrícula en unario. La entrada, a continuación, tiene al menos $n$ bits.

Si la cuadrícula contiene cada número$1,2,\dots,n^2$, a continuación, una solución puede ser considerado como una permutación de estos números, que requiere en la mayoría de las $n^2\, \lceil \log\, n \rceil = O(n^3)$ bits a la lista. Esto es claramente polinomial en el tamaño de entrada.

Si la cuadrícula se pueden contener cualquier enteros no negativos, o incluso enteros en general, a continuación, un poco más de trabajo parece ser necesario (ver mi respuesta en CSTheory, donde esta cuestión se crossposted).