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?
cc.complexity-theory
np-hardness
np
puzzles
levanovd
fuente
fuente
Respuestas:
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!"
fuente
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:
Esto también apareció como Teorema 4.7 en:
Esto produce lo siguiente:
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.
fuente