I have seen (and I have also used myself) the phrase “research-level questions in theoretical computer science” to describe the scope of cstheory.stackexchange.com.

However, thinking about it, I believe that the word “research-level” in this context means something like “which arise or can arise in research in TCS”. In other words, if a TCS question arises in research in an applied field and it is too easy for TCS research, I do not think that it is usually called a “research-level question in TCS”.

This seems too restrictive given that the consensus, though still being developed, seems to be to allow easy questions in TCS as long as they are not something like homework or typical exercises in textbooks and the asker has done reasonable due diligence (see the discussion “On the feasibility of homework questions” started by Raphael and the comments on the question “Is the following problem NP-Hard?”).

Therefore, I want a better description of the scope. What is your take?


1 Answer 1


Tsuyoshi, I think you're being too narrow when you conceive of research level questions in TCS. A fair bit of TCS research is modelling=type work where you take problems from applied domains and model them as theory problems (sometimes leading to new questions, and sometimes not). In that case, the current description suffices.

  • $\begingroup$ I see your point. Your answer has reminded me of Scott’s answer to another question of mine. At that time I thought I understood that view, but I am afraid that I have not digested it yet. Let me think about it. $\endgroup$ Commented Nov 12, 2010 at 19:16

You must log in to answer this question.

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