4
$\begingroup$

Here we have a problem about NP-hardness for magic squares, posted by @levanovd. At first I do consider it as a home-work level question, and suggest the OP to wait for answers on Math SE. But after trying to solve the problem for a while, although there is a solution to the problem, I found it non-trivial. So I flipped my opinion and suggested to keep to question open.

It is my fault to give suggestions before having a clear thoughts on the level of the question, and I feel sorry to @levanovd.

In order to prevent the same thing happened again, here I want to ask:

What kind of NP-hardness problems are considered on/off-topic?

The judge may be depended on each user, and by the number of closing votes we should solve this problem with no difficulties; but currently there aren't too many users have the power to give the vote, so maybe some rules will help us to decide what kind of suggestions should be given to the OP.

$\endgroup$
4
  • $\begingroup$ Concerning the question by levanovd: I think (s)he could have started with Colbourn's "The complexity of completing partial Latin squares", which was not that hard to google. Which does not imply either that the question was trivial, of course. $\endgroup$
    – Anthony Labarre
    Dec 21, 2010 at 12:27
  • 10
    $\begingroup$ I don't see why NP-hard questions should be treated any different from any other questions. That is, close if it's easily googlable, or if it seems like homework. Otherwise, leave it open. $\endgroup$
    – Peter Shor
    Dec 21, 2010 at 17:02
  • 1
    $\begingroup$ I'm with Peter on this one. $\endgroup$
    – Suresh Venkat
    Dec 21, 2010 at 17:19
  • $\begingroup$ @Peter: Since NP-hard question is one of the topics being taught in undergrads, so it is more likely to have a chance being a homework, or somehow easy googlable. (is that a word?) But here I agree with you, maybe applying the same rules as other question works. And we need experts on the site to help us recognize the level of the problems. Thank you for the comment! $\endgroup$
    – Hsien-Chih Chang 張顯之
    Dec 22, 2010 at 1:28

1 Answer 1

Reset to default
6
$\begingroup$

I guess the same rules that are in use for other questions would apply in this particular case: questions about well-known results (hardness of SAT, 3DM, PARTITION, ...) that can be found in any relevant textbook should be closed with a reference to such a textbook.

For those problems that do not seem so "trivial", or are at least less well known, I remember (feel free to edit this answer and link to the relevant question if that rings a bell, I cannot remember its title, and I think it was answered by Tsuyoshi Ito) seeing at least one question asked by a user who admitted being no expert in complexity theory, who was asking if the problem he was considering was hard. There are indeed cases where the person asking such a question is merely trying to justify his approach to the problem (e.g. using heuristics if the problem is "easy" would be stupid, but is justified if the problem is difficult), and is not only interested in having you do the dirty work for him.

At the risk of sounding obvious, even though the question seems trivial to many, those people have no idea how hard it actually is ;-) I have also asked a few complexity-related questions because I had exhausted all my ideas and had been stuck for a while; it turns out that they were not so easy to answer after all, but I could very well have made a fool of myself -- complexity can be surprising sometimes, at least to me.

We have enough experts and seasoned researchers here who are probably better than I am at deciding which questions in what fields are trivial or not. Their opinion should help, and I'm sure they'll come up with better answers than the present one. I would also think that asking for more motivation, as we do when in doubt that the question might be homework, should help.

$\endgroup$
3
  • 1
    $\begingroup$ Thanks for replying and sharing your experiences, like you and @Peter said, we would better apply the same rules as other questions. I'll accept you answer. $\endgroup$
    – Hsien-Chih Chang 張顯之
    Dec 22, 2010 at 1:32
  • 1
    $\begingroup$ You probably meant this question: Is the following problem NP-Hard? $\endgroup$
    – Tsuyoshi Ito
    Dec 22, 2010 at 2:27
  • $\begingroup$ Yes I did, thank you! $\endgroup$
    – Anthony Labarre
    Dec 22, 2010 at 6:57

You must log in to answer this question.

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