6
$\begingroup$

Here is the problem:

We have a square with some numbers from 1..N in some cells. It's needed to determine if it can be completed to a magic square.

Examples:

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

Is this problem NP-complete? If yes, how can I prove it?

P.S.:
I know that I should reduce one of the known NP-complete problems to this one to prove its NP-completeness. The main question is which NP-complete probleme to choose and how to buld polynomial reduction algorithm. Any ideas?

  • 0
    I know **what** to do. I do not know how exactly. I thought about reducing one of the listed problems to this one, but haven't achieved any satisfying results.2010-12-21

1 Answers 1

1

One has to show both membership in NP, and NP-hardness.

For NP-hardness, perhaps one of the people commenting on the question could provide a hint for which NP-complete problem one should reduce from. (I do not have a suitable reduction to solve this part of the question.)

For membership of NP, it is enough to show that if there is a solution, then there is some solution of polynomial size in the input. Such a solution can then be guessed in polynomial space and checked in polynomial time, so the problem is in NP. Establishing this is not as immediately obvious as it might appear at first glance.

To avoid pathological cases, it is common to require that the input specifies the size of the $n \times n$ grid in unary. The input then has at least $n$ bits.

If the grid contains each number $1,2,\dots,n^2$ then a solution can be regarded as a permutation of these numbers, which requires at most $n^2\, \lceil \log\, n \rceil = O(n^3)$ bits to list. This is clearly then polynomial in the input size.

If the grid is allowed to contain any non-negative integers, or even integers in general, then a bit more work seems to be required (see my answer at CSTheory, where this question was crossposted).