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