11
$\begingroup$

One of the things that regularly prompts me to refresh this stackexchange is the promise of interesting open problems (and not "wide" open problems like major complexity class separations or the complexity of factoring/matrix multiplication/etc).

Encoded in this are three qualities I am looking for. Each are mildly subjective but I hope the general idea is communicated:

  • Open/important (to somebody).
  • Natural/interesting.
  • Not "wide" open. By "wide" I mean the problem is probably not solvable with current techniques.

There have been some seriously cool open problems posted. There is in fact even a tag 'open-problem' used to demarcate questions involving open problems. (The two "seriously cool" examples I linked to are both on this list.)

However, I am worried that the list of questions tagged with 'open-problem' is not complete. For example, here is a question that is open, not demarcated with the 'open-problem' tag but that meets the criteria I listed above. This seems to happen with regular frequency: a question is posted, it is resolved soon thereafter that the question has been open in the literature for some time, yet the question is not then given the 'open-problem' tag.

I was wondering if we could compile and keep updated (an ultimately subjective) list of open problems meeting the above criteria which are not given the 'open-problem' tag. A list like this is interesting to me, and I am sure will be interesting to other members. It will be easier to justify the site to newcomers and can help compile some of the most intriguing question for pursuits like the poster for STOC.

$\endgroup$
8
  • 1
    $\begingroup$ Of course, one solution is to be more vigilant about giving the 'open-problem' tag in the first place. Still, many questions with the 'open-problem' tag do not meet the bullet-pointed criteria above. I feel like this solution would be mixing two different kinds of open problems in one list. $\endgroup$
    – Ross Snider
    Nov 28, 2010 at 3:50
  • $\begingroup$ why not just tag these with open-problem ? $\endgroup$
    – Suresh Venkat
    Nov 28, 2010 at 5:49
  • $\begingroup$ Jeff's innocent open problem is an amazingly simple and potentially has far reaching consequences (as far as $P \ne NP$). $\endgroup$
    – Mohammad Al-Turkistany
    Nov 28, 2010 at 11:30
  • 1
    $\begingroup$ @Suresh This does seem like a solution, but because open-problem includes questions/answers which do not necessarily meet the bullet-pointed criteria we might consider keeping a separate list. Then again, the work of maintaining a list here might outweigh the benefits. $\endgroup$
    – Ross Snider
    Nov 28, 2010 at 16:46
  • $\begingroup$ Does anyone know how MathOverflow handles such problems? If they have a good way to organize new open problems posted there, we can probably just do the same thing. $\endgroup$
    – Tsuyoshi Ito
    Nov 28, 2010 at 19:17
  • 2
    $\begingroup$ I think [open-problem] is exactly for wide open questions which are known to be so in the literature (or questions which are equivalent to them). MO's FAQ about open-problem is here. Note that we already have a page for unanswered questions. $\endgroup$
    – Kaveh
    Nov 29, 2010 at 5:32
  • 3
    $\begingroup$ I guess it would be best to not try to solve this with tags. What if you simply write a CW post here on meta, and encourage people to edit it (or answer it) whenever they encounter open problems that match your criteria? $\endgroup$
    – Jukka Suomela
    Nov 29, 2010 at 9:37
  • 2
    $\begingroup$ @Jukka This is a good idea, I think. It potentially requires a larger expenditure of work, but I believe the payoff of having such a list is high so I am willing to try it. Still, the 'open-problem' tag is somewhat ambiguous and if I adopt this plan we'll still have to hash out that discussion. $\endgroup$
    – Ross Snider
    Nov 29, 2010 at 18:08

3 Answers 3

Reset to default
2
$\begingroup$

Maybe the best solution is to leave the 18 questions tagged as they are, but start using the above suggested list as a criterion for new open problems. In addition, if a problem stated as open turns out not to be, or is resolved, we remove the tag. If there's general agreement we can add an FAQ entry to this effect.

$\endgroup$
16
  • 1
    $\begingroup$ How do we handle the case when the problem seems to be answerable, but after a while (or some clever observations) it becomes more and more intractable, but still it is not known to be opened? $\endgroup$
    – Hsien-Chih Chang 張顯之
    Nov 29, 2010 at 1:52
  • $\begingroup$ but isn't it still open in that case ? $\endgroup$
    – Suresh Venkat
    Nov 29, 2010 at 2:31
  • $\begingroup$ I like this idea. Specifically, it allows us to keep a list of "interesting" open problems and at the same time it minimizes extra work. It clarifies a potentially ambiguous tag. Interested parties can also get updates on open problems with the RSS features provided by the site. $\endgroup$
    – Ross Snider
    Nov 29, 2010 at 2:40
  • $\begingroup$ Right. and we can also update the tag wiki for open-problems to do this. Ross, can you add an FAQ entry ? $\endgroup$
    – Suresh Venkat
    Nov 29, 2010 at 4:26
  • $\begingroup$ I don't see the need, there is already a page for unanswered questions. I think we should keep [open-problem] for questions which are equivalent to known to be open-problems in the literature. $\endgroup$
    – Kaveh
    Nov 29, 2010 at 5:17
  • $\begingroup$ @Suresh: My definition of an "open" problem is near the one of Kaveh's, that is, open in the literature. However, this method should be good for those problems not well-known to be opened and hanging for a while in our lists, and I give it +1. Maybe a time-expired machinery will help? Say, for a week the problem has not been solved, we retag it with [open-problem]. Since the unanswered questions lists will become much and much longer, searching for nice less-known open problems will become harder. Or can we have another tag, say [major-open-problem] or something like that for the well-knowns? $\endgroup$
    – Hsien-Chih Chang 張顯之
    Nov 29, 2010 at 5:33
  • $\begingroup$ @Hsien-Chih Chang: I think that would be a meta-tag and SE advises against using them, the list of unanswered question becoming long is not a good reason for creating a new meta-tag, the interesting unanswered questions are exactly those on the top of the unanswered questions page, the more interesting ones have more votes. The same problem of becoming much much longer will also eventually apply to the tag if we create one so it is not going to solve a problem. $\endgroup$
    – Kaveh
    Nov 29, 2010 at 5:45
  • $\begingroup$ Kaveh, Hsien-Chih Chang: a question is deemed 'unanswered' if there's no upvoted answer for it. Neither of the two questions listed satisfy this criterion, and are therefore not listed on the 'unanswered questions' page. Further, lots of unanswered questions are just uninteresting. So the two notions are quite different. While I understand the SE suggestion not to use meta tags, I think that for our needs, an 'open problem' tag is useful for the reasons Ross outlined. $\endgroup$
    – Suresh Venkat
    Nov 29, 2010 at 6:55
  • $\begingroup$ @Suresh, it is also possible to search exactly for questions without accepted answers. Interesting/uninteresting is a subjective issue, I think most users think their questions are interesting, and can't think of a way to decide which question is interesting and which one is not other than votes by users. My opinion is that the current [open-problem] tag serves another purpose (similar to its purpose on MO), so if the opinion is that we want a tag for [interesting-unanswered-questions] we should create a new one (although I still don't see the need for such a tag). $\endgroup$
    – Kaveh
    Nov 29, 2010 at 7:03
  • $\begingroup$ I'm a little confused about the direction this discussion is taking. Ross's original question was about open problems in the research sense. I think this side discussion on unanswered questions is irrelevant to that point. The proposal is to have a clear policy on what merits the 'open problem' tag and use that consistently from now on. $\endgroup$
    – Suresh Venkat
    Nov 29, 2010 at 7:06
  • $\begingroup$ @Suresh: sorry, the discussion and what we were considering to tag with [open-problem] (like tagging a question which is not answered after a week) suggested otherwise to me. I think we were using the [open-problem] tag in a similar way to MO up till now (i.e. known to be wide-open in the literature). It may help to have a more clear picture on what is going to be tagged [open-problem] and the process. To me being cool and unanswered for a while and not wide-open does not seem to be a good criteria. $\endgroup$
    – Kaveh
    Nov 29, 2010 at 7:15
  • $\begingroup$ Let me clarify my opinion about the items listed by Ross: I assume that every question posted on cstheory is important and interesting for the person asking it (otherwise what is the point of posting it?) so the first two items from the list will apply to every question, and the third one is exactly the opposite of the current use of [open-problem]. $\endgroup$
    – Kaveh
    Nov 29, 2010 at 7:21
  • $\begingroup$ @Kaveh: While the MO model is a useful guide, I wonder if it's right for us. TCS is a MUCH younger discipline than math, and I think it's common in our discipline to "discover" problems that we didn't realize were open but actually are (eg the interactive proofs question). In such cases, tagging with 'open-problem' is an act of recognition, that these problems are actually open, rather than an act of classification (that this problem is equivalent to a known open problem). Note again (I repeat) that no one is suggesting that an unanswered question should by default be labelled open. $\endgroup$
    – Suresh Venkat
    Nov 29, 2010 at 7:22
  • $\begingroup$ An open problem is in some way important. I can't quantify this, but we do this all the time in research, so it's doable. $\endgroup$
    – Suresh Venkat
    Nov 29, 2010 at 7:23
  • $\begingroup$ @Suresh: I am not against tagging questions that we recognize are wide open as [open-problem] like the interactive proofs case (maybe I misunderstood but my understanding was that Ross is asking for tagging interesting answerable unanswered questions as [open-problem]). As I said, I would like to see more clarification on what is going to be tagged [open-problem] and the process. $\endgroup$
    – Kaveh
    Nov 29, 2010 at 7:37
2
$\begingroup$

I would like to ask for clarification on what is going to be tagged as [open-problem] to make sure I was misunderstanding the question (in which case I would also drop my previous position and support the idea).

I think [open-problem] means that no one knows an answer to the question and we don't think that it can be answered by an expert in the area even if she/he spends some (short) time to think/work on it, but rather needs serious research and spending considerable time to be solved. I.e. it is not the kind of question that can be answered in a coffee-break or by spending a few hours.

And the proposal is to use [open-problem] tag for such questions.

$\endgroup$
7
  • $\begingroup$ Kaveh, as you know there are many sorts of open problems. Some open problems are like the Riemann Zeta Function hypothesis, P versus NP, or whether BPP has complete problems. These sorts of problems are important but are pursuits that essentially constitute pipe dreams. These problems are "wide" open. They are certainly important to catalog! However, they are not problems we would want to put on a poster for STOC or FOCS, and they do not constitute a list of problems that would inspire... $\endgroup$
    – Ross Snider
    Nov 29, 2010 at 17:36
  • $\begingroup$ ...a passerby to spend more time on the stackexchange. Instead, open problems just "below" this calibur qualify for these ends. So, I am trying to ask if we can get, or if we already have, a compendium of problems that could qualify as a decent PhD thesis or reasonable publication - problems that are open because they are hard but not open because they are undesirably hard. This was my purpose. In asking this question, there was another question that was asked implicitly - specifically what 'open-problem' $\endgroup$
    – Ross Snider
    Nov 29, 2010 at 17:47
  • $\begingroup$ means for this stackexchange. I think its reasonable to tag P versus NP and fast factoring algorithms as open problems, because they are. However, I would like to have more; a list of problems that will contribute in smaller ways, are "cool" (subjective, yes), but which are not trivial and require creative insights and mastery of material. $\endgroup$
    – Ross Snider
    Nov 29, 2010 at 17:50
  • $\begingroup$ @Ross: sorry, but I still have trouble in understanding what is going to be tagged with [open-problem]. Can you be more specific about the differences between what I have said above and what you are saying? Can you state examples of questions on cstheory that would satisfy what I said above but don't satisfy what you have in mind and vice versa? $\endgroup$
    – Kaveh
    Nov 29, 2010 at 21:57
  • $\begingroup$ I think you both are agreeing :) $\endgroup$
    – Suresh Venkat
    Nov 29, 2010 at 23:13
  • $\begingroup$ I think we are agreeing on many levels. However, I'm specifically trying to exclude problems that experts won't be able to solve for a long time to come (and particularly those that are "popular" - that many experts have looked at with serious research efforts). The request is a way to maintain some sort of separation between the easier side of hard and the harder side of hard. $\endgroup$
    – Ross Snider
    Nov 30, 2010 at 0:10
  • $\begingroup$ @Ross: :) but I want to keep tagging those known wide open problems with [open-problem] tag. Here is an alternative suggestion: post a CW soft question on the main site and ask for interesting questions asked on cstheory that turned out to be open but seem approachable. (I have seen people asking similar questions on MO.) $\endgroup$
    – Kaveh
    Dec 1, 2010 at 0:11
1
$\begingroup$

Here is a suggestion for effective simple mechanism:

A moderator or a high-reputation member nominate a candidate open problem (which is not known to be open in the literature) in the comment section. Then others vote on that comment and when the votes reach some value (for example 30), we add the open problem tag.

$\endgroup$

You must log in to answer this question.