I think we can be fairly relaxed about this instance. Here I intended to reformulate a few things said in this thread, to bring together some strands and maybe add some clarity, and then I suggest a rule which is not far, I think, from what we have been doing.
Observe that we might mean two different things by "research-level". Consider three kinds of question:
- Questions that every self-respecting, theoretically oriented comp-sci graduate student should be able to answer;
- Questions many TCSers whose expertise lies elsewhere will have difficulty with, but which yield easily to insights that are well-established in some domain of expertise;
- Questions that are open problems; original, worthy research problems; or previously solved problems whose solution is not widely known even among domain experts.
Level 1 is not appropriate here, level 3 is research level by any reasonable reckoning. But what about level 2? As Radu noted, questions of this sort are quite often interesting in the context of a problem in one TCS domain, but demand expert knowledge from another domain for their solution; these are clearly research-motivated questions, and the site would be poorer to reject these. So if we might mean just level 3 counts as research level, we might alternately say that levels 2 and 3 are appropriate to the site.
But level 2 will also include some grad school problems and puzzles like the question that led to this thread. Several people suggested that the motivation for a question might be used as a criteria to divide these level into worthy and unworthy. The issue here is that we do not demand that the motivation be provided for questions, so we have to decide on the basis of what we see. Thus as Marcus and others have said, judging motivation is problematic. It is not clear that there are other useful, principled criteria for dividing level 2 into good and bad.
There isn't much sign that level 2 questions have been a significant nuisance —here Tsuyoshi's concern seems to be to do with consistency— but in the long run they could be. I suggest we work according to the following criterion: level 2 questions situated in the context of any research interest are on topic. Level 2 questions that lack such motivation are in a grey area: we should encourage motivation, and we promise no consistency in the way we handle them. These questions will be closed if there are five people with close powers who are bothered by the question. It might be good to have a thread listing such closures.
Large grey areas are not good, but I think it would be worse to bar good questions or stipulate the unworkable as criteria. Can we do better?