¿Está el problema del cuadrado mágico medio lleno NP-completo?

13

Aquí está el problema:

Tenemos un cuadrado con algunos números de 1..N en algunas celdas. Es necesario para determinar si se puede completar en 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? En caso afirmativo, ¿cómo puedo probarlo?

Crosspost en MS

levanovd
fuente
2
No, pedir ayuda no es algo malo. Pero su pregunta tiene que estar dentro del alcance del sitio que solicitó. Creo que Math SE es apropiado para esta pregunta, y TCS SE no lo es.
Hsien-Chih Chang 張顯 之
55
Aceptamos preguntas sobre cómo probar la dureza NP, especialmente cuando el problema es difícil. Por ejemplo, considere los tres ejemplos enumerados como respuestas aquí: meta.cstheory.stackexchange.com/questions/784/…
Suresh Venkat
66
Si es tarea, no lo permitimos, sea o no ético.
Peter Shor
13
@levanovd: Esto no es stackoverflow. Esta comunidad tiene una política explícita que prohíbe las preguntas de tarea. El hecho de que stackoverflow tenga una política diferente no importa aquí.
Jeffε
3
No conozco una solución y no creo que esté al nivel de tarea. Sin embargo, podría estar perdiendo algo simple. Por lo tanto, si alguien conoce una solución completa y cree que esta pregunta es a nivel de tarea, solo dígalo. Mientras tanto, supondré que esta pregunta no es tarea y que la etiqueta [tarea] utilizada en Math SE y el comentario anterior de levanovd fueron simplemente errores.
Tsuyoshi Ito

Respuestas:

18

Llenar un cuadrado latino parcialmente lleno es NP-Complete. "La complejidad de completar cuadrados latinos parciales" Charles J. Colbourn. Matemáticas Aplicadas Discretas, Volumen 8, Número 1, Abril 1984, Páginas 25-30 http://dx.doi.org/10.1016/0166-218X(84)90075-1

¿Se puede convertir un problema cuadrado latino en un problema cuadrado mágico a través de la aritmética modular? Mi intuición dice que sí, pero el resto de mi cerebro dice "¡Vuelva a calificar!"

Peter Boothe
fuente
2
Sería bueno convertir esto en un argumento riguroso. No tengo nada claro para mí cómo la aritmética modular realmente ayudaría a reducir la TERMINACIÓN CUADRADA LATINA a la TERMINACIÓN CUADRADA MÁGICA, o viceversa. Sería bastante bonito si pudiera hacerse funcionar.
András Salamon
9

Esta pregunta tiene dos partes: primero, ¿es el problema en NP, y segundo, es NP-difícil?

Para la primera parte, tengo una respuesta positiva con una prueba no obvia. (Gracias a Suresh por señalar un error anterior).


Considere la siguiente forma de formalizar la pregunta como un problema de decisión:


nortenortenorte
?

1,2,...,norte2 , tiene esta restricción; en contraste, el artículo de Wikipedia actualmente usa la terminología "cuadrado mágico normal" y reserva "cuadrado mágico" para la versión sin restricciones.

nortenortenortenortenorte

norte2

xi=1xi=xj+xki,j,k{1,2,,n}xi5n1

Esto también apareció como Teorema 4.7 en:

2n2n1

xi=1xi=xj+xki,j,k{1,2,,n}xi2n

2n1 límite mantiene, como corolario de su Teorema 1.1 más general.

Esto produce lo siguiente:

N2O(N2)

O(N4)O(N8)n2+2(n+1)(n2)+1=3n22n3n2metroO(metro2)

norte


Usando el límite de Papadimitriou en las soluciones de una instancia de PROGRAMACIÓN LINEAL INTEGRAL, también se puede mostrar que la versión donde todos los números deben ser no negativos también está en NP.

UNr×ssir{-un,-un+1,...,un-1,un}UNX=si{0 0,1,...,s(run)2r+1}

un=1s=norte2+1r=2norte+2

  • Christos H. Papadimitriou, Sobre la complejidad de la programación de enteros , JACM 28 765–768, 1981. ( enlace )
András Salamon
fuente
Supongo que estoy confundido. Si hay un límite de polivinilo en el tamaño de las respuestas, entonces tenemos la garantía de tener una conjetura que puede leerse y verificarse en tiempo polinómico.
Suresh Venkat
@Suresh: Disculpas por los errores, esta respuesta resultó un poco más difícil de escribir de lo que esperaba.
András Salamon