Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  Qiaochu Yuan Dec 21 '10 at 8:27
    
I thought about converting this problem to Hamiltonian circuit or TSP or Subset sum problems, but not too successfully. –  levanovd Dec 21 '10 at 8:40
3  
@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. –  Alex B. Dec 21 '10 at 8:43
    
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. –  levanovd Dec 21 '10 at 8:43
1  
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. –  Alex B. Dec 21 '10 at 8:59

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.