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
    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.2010-12-21
  • 0
    I thought about converting this problem to Hamiltonian circuit or TSP or Subset sum problems, but not too successfully.2010-12-21
  • 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.2010-12-21
  • 0
    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.2010-12-21
  • 0
    @Alex Bartel: yes, we need to build two-side reduction2010-12-21
  • 0
    Well, to show that the problem is in NP, you don't actually need any reductions. Just devise a polynomial time algorithm that verifies that a given solution is correct.2010-12-21
  • 0
    But I need to show that it is NP-complete.2010-12-21
  • 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.2010-12-21
  • 0
    Ok, so any ideas about this?2010-12-21
  • 0
    Your NP-complete list above suffices. Try to reduce one of the problems in the list to your problem.2010-12-21
  • 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).