12
$\begingroup$

It was bound to happen and thankfully, it did now rather than later: we received the first question about a claim regarding P?=NP.

Some topics, in particular this, attract lots of public attention and laymen research. I do not want to belittle such efforts, but according to experts (i.e. complexity theory researchers) most of them are no good at all and in total, the signal to noise ratio is small.

How do we deal with such questions? As we generally allow questions of the form "Please help me understand X!" (or so I believe) this can not be the angle. Should we discourage people to ask questions about stuff that is likely to be cranky, or do we rather take the opportunity to educate people about how to tell "good" from "bad" work?

$\endgroup$
  • 1
    $\begingroup$ am in favor of intelligent discussion of CS topics. P=?NP is a core/premiere CS topic. suggest a flexible policy here that allows a case-by-case examination rather than a strict, general policy. moreover there is no reference to explain to beginners why it is so hard, what has been tried and failed, & an online reference (of failed approaches) would be a real service. $\endgroup$ – vzn Sep 13 '13 at 1:06
  • 1
    $\begingroup$ @vzn 1) This thread is old and has a highly upvoted answer. If you think something changed and we should discuss anew, open a new meta question. 2) Nobody has anything against intelligent discussion, but SE does not work well for discussion. 3) Facts are fine, we already have e.g. this one. 4) Note that Gilles does only apply the usual guidelines to "crank" questions, nothing else. 5) You have been warned to stop judgemental bickering, harping on the same themes over and over again. I'm editing your comment to remove more of the same. $\endgroup$ – Raphael Sep 13 '13 at 6:20
  • 1
    $\begingroup$ @vzn Oh, and how you think (again) that some post on Theoretical Computer Science is relevant to a discussion here is beyond me. The sites are not the same. It's time you accept that. $\endgroup$ – Raphael Sep 13 '13 at 6:23
  • 1
    $\begingroup$ re P=?NP in particular see also math monster, many links to learn about P vs NP and large collection/compilation of existing stackexchange questions on subj, also is there any way to make a P=?NP proof question on topic $\endgroup$ – vzn Oct 12 '13 at 18:55
12
$\begingroup$

Here's the policy I would favor. I'm open to being contradicted if you've had experiences on other sites (Theoretical Computer Science, Math, Physics, …) that show that this policy is not viable.

Questions like “Is this proof correct?” or “I'm sure this proof is wrong but what's the fallacy?” or similar variants should be closed as “not a real question”, because they are overly broad (or worse, rhetorical like “I challenge you to find a fallacy”). You can't expect a review of a proof of anything more than a few clearly written lines in a Stack Exchange answer. Favorite crank topics can be held to a particularly high standard.

Unclear problems should be closed as “not a real question” too (ambiguous, vague, incomplete). If someone who's reasonably versed in the domain of the question cannot determine the precise statement of the problem from the question, close. Again, favorite crank topics can be held to a particularly high standard.

On the other hands, questions like “Is [clearly stated problem] in P” are valid questions. I don't see any grounds to refuse them. Again, the more the topic attracts cranks, the more precision and clarity should be required. If that problem is a variation on some well-known NP-complete problem, the answer “here is why this problem is NP-complete, and it is a well-known open problem whether it is in P” is a perfectly acceptable answer. If the question calls for more than that, close as “not a real question” (overly broad).

Furthermore, we need to be careful not to encourage copycats. This means quickly closing “dodgy” questions, and subsequently deleting them unless salvaged. Also, borderline questions should be edited to deemphasize the crank relationship.

With regards to https://cs.stackexchange.com/questions/305/whats-wrong-in-this-article-claming-p-np, I have voted to close as “not a real question”. I left the following comment:

You are claiming that some variation of a well-known NP-complete problem is in P. This is an extraordinary claim requiring extraordinary evidence. Some random article found on the web does not constitute extraordinary evidence. Therefore I am voting to close this question as overly broad; it is not our goal here to make broad advances to science in a single post.

Thanks to Artem Kaznatcheev for setting me straight in chat about what the question was really asking.

$\endgroup$
  • 1
    $\begingroup$ I agree on your policy proposal. Regarding the specific question, I am not so sure. The OP very clearly wanted to have the cited article refereed. I do not know wether they are interested in the proposed problem per se. And, as I said there, if the proposed problem is really NPC we can not expect a good answer (because there is none to date, and answers are arguably hard to find). $\endgroup$ – Raphael Mar 13 '12 at 13:33
  • 2
    $\begingroup$ I'm not sure what the asker wanted, but there's a point where this stops mattering: if what the asker wants is not suitable for the site, then the question must be closed or edited. If there is an interesting subquestion in there, it is better to edit. $\endgroup$ – Gilles 'SO- stop being evil' Mar 13 '12 at 13:49
  • 1
    $\begingroup$ The policy on Math.se and CSTheory is similar. If there is a specific technical question, it can be answered. The question which prompted this certainly does (but the title does not do it justice). I have just upvoted it and suggested a new title. $\endgroup$ – Aryabhata Mar 13 '12 at 17:39
  • 2
    $\begingroup$ I agree with the three bullets at the end, but I voted to close the question in its present form. $\endgroup$ – Carl Mummert Mar 13 '12 at 17:47
  • 1
    $\begingroup$ I want to +1 this answer (due to the suggest of closing questions as NARQ; although I voted close as off-topic just by cstheory-instinct), but I can't because I disagree with the comments about the specific P v NP question. $\endgroup$ – Artem Kaznatcheev Mar 13 '12 at 19:07
  • $\begingroup$ If someone can make a reasonable attempt at proving P = NP, I'm sure they would also know that the TCS SE is a better place to post their proof, wouldn't they? $\endgroup$ – xuq01 Nov 24 '18 at 23:07
8
$\begingroup$

I don’t think that in-depth reviews of whole articles (10 pages in this case) are in the scope of CS.SE. If the author submits his work the usual publishing routine will perhaps produce some reviews.

Now, if a third person has a question about such an article it should be specific and narrow. For example something along the lines: “The author has defined X, but in his first lemma where he uses X, I think he is not following his own definition?” The question should show that the inquirer has at least made some effort himself towards answering the question. Asking for the typical gaps (“it is easily verified that Y holds.”) in a proof are valid questions, however the inquirer should include what he himself got so far. On TeX.SE people are usually asked to provide a “minimum failing example” so the community has a quick starting point for examining the problem at hand.

Just pointing to a result an asking whether it is true or not is simply to broad. Something like “Maybe here is a problem?” is incomplete as the inquirer should at least state where his suspicion comes from.

For example in question it is not clear what has been tried so far by the inquirer. For my taste just stating “I was unable to find a proof of the fact.” could at least include where he has looked at so far (Hopcroft & Ullman?, Harrison?, Salomaa?). (Then I don’t have to go through this again. It’s a courtsey towards the person taking their time to provide an answer.)

$\endgroup$

You must log in to answer this question.

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