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?

$\endgroup$
11
  • $\begingroup$ If this is homework, you might try listing the NP-complete problems you know and seeing if you can think of a reduction to one of these. $\endgroup$ Dec 21, 2010 at 8:27
  • $\begingroup$ I thought about converting this problem to Hamiltonian circuit or TSP or Subset sum problems, but not too successfully. $\endgroup$
    – levanovd
    Dec 21, 2010 at 8:40
  • 3
    $\begingroup$ @Qiaochu A minor addition: what you are saying would prove that the problem is in NP. To prove that it is NP-complete, you need to reduce an NP-complete problem to this one. $\endgroup$
    – Alex B.
    Dec 21, 2010 at 8:43
  • $\begingroup$ I'm familiar with Clique, Minimal Vertex cover, Knapsack problem, 3SAT and some others. However, conversion to any known NP-complete problem is welcome since if I even don't know such NP-complete problem, I can read about it. $\endgroup$
    – levanovd
    Dec 21, 2010 at 8:43
  • 1
    $\begingroup$ Yes, that's a different story. For that you need a reduction from a known NP-complete problem to this one - so only one reduction. $\endgroup$
    – Alex B.
    Dec 21, 2010 at 8:59

1 Answer 1

1
$\begingroup$

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).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .