O problema do quadrado mágico meio cheio está NP-completo?

Aqui está o problema:

Temos um quadrado com alguns números de 1..N em algumas células. É necessário determinar se ele pode ser concluído em um quadrado mágico.

Exemplos:

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

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

Esse problema está completo? Se sim, como posso provar isso?

Crosspost em MS

O preenchimento de um quadrado latino parcialmente preenchido é NP-Complete. "A complexidade de completar quadrados latinos parciais" Charles J. Colbourn. Matemática Aplicada Discreta, Volume 8, Edição 1, Abril de 1984, Páginas 25-30 http://dx.doi.org/10.1016/0166-218X(84)90075-1

Um problema do quadrado latino pode ser transformado em um problema do quadrado mágico por aritmética modular? Minha intuição diz que sim, mas o resto do meu cérebro diz "Volte para a nota!"

Essa pergunta tem duas partes: primeiro, o problema está no NP e, segundo, é difícil no NP?

Para a primeira parte, tenho uma resposta positiva com uma prova não óbvia. (Agradecemos a Suresh por apontar um erro anterior.)

Considere a seguinte maneira de formalizar a pergunta como um problema de decisão:

UNRESTRICTED QUADRADO MÁGICO CONCLUSÃO
Entrada: inteiro positivo dada em unário, lista de números inteiros com suas posições em um n por n grade Pergunta: fazer existem inteiros para os cargos restantes no grid, de modo que as formas de arranjo um quadrado mágico ?$n$$n$$n$

Se adicionarmos a restrição de que cada um dos números inteiros deve ocorrer precisamente uma vez no quadrado mágico, o problema resultante da decisão MAGIC SQUARE COMPLETION resultante está obviamente em NP. A definição de um quadrado mágico na Encyclopædia Britannica de 1911 , seguindo Euler , tem essa restrição; por outro lado, o artigo da Wikipedia atualmente usa a terminologia "quadrado mágico normal" e reserva "quadrado mágico" para a versão irrestrita.$1,2,\dots,n^2$

Com um por n grid, pelo menos n números deve ser dada, caso contrário, a resposta é trivialmente "SIM" para a versão sem restrições. Portanto, o tamanho da entrada pode exigir mais de n bits neste caso. Para a versão normal, é possível que haja entradas que exijam poucos bits, mas que não tenham solução; para evitar tais complicações, especifiquei que n é dado em unário.$n$$n$$n$$n$$n$

O argumento usa um limite no tamanho possível de números inteiros que aparecem nas soluções. No caso normal, esse limite é obviamente , mas no caso geral, não é a priori óbvio que esse limite exista. Acontece que existe um limite exponencial.$n^2$

Teorema ( Tyszka, Teorema 12 ): Qualquer sistema de equações diofantinas envolvendo equações da forma e x i = x j + x k , para i , j , k ∈ { 1 , 2 , … , n } , também não tem solução inteira, ou tem uma solução na qual todo x i é um número inteiro e, no máximo, $x_i = 1$$x_i = x_j + x_k$$i,j,k \in \{1,2,\dots,n\}$$x_i$em valor absoluto.$\sqrt{5}^{n-1}$

Isso também apareceu como Teorema 4.7 em:

• Apoloniusz Tyszka, Duas conjecturas sobre a aritmética em R e C , Matemática. Registro. Quart. 56 175-184, 2010.

Cipu anunciou recentemente um limite assintoticamente melhor de . (Observe que o menor limite possível é 2 n - 1. ) O argumento se baseia em um limite no determinante de uma matriz, devido a Waldi.$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}$

Isso produz o seguinte:

$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$

Usando o Papadimitriou's vinculado às soluções de uma instância de INTEGER LINEAR PROGRAMMING, pode-se também mostrar que a versão em que todos os números devem ser não-negativos também está em 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, Sobre a complexidade da programação inteira , JACM 28 765–768, 1981. ( link )