Skip to main content

Problems known to be open in the literature and any problem that, after being posed, is decided to be open by the community.

Use this tag if:

  • well-known open problems: the problem is equivalent to a well-known open problem in the literature
  • community open problems: the question is not answered after considerable time and the community decides that the question is an open problem (meta can be used for discussions)

cstheory is not the right place to ask well-known open problems. You should post questions you're actually seriously thinking about. If you're thinking about a well-known open problem, provide some background and ask about something specific related to the problem, like "Such and such is a well-known open problem. So-and-so proposed this and that approach. Does anybody know if this aspect of their proposal can be made to work under these circumstances?" If you want to contribute to (or view) a list of open problems, visit the Open Problem Garden.

If it turns out that a problem is equivalent to a well-known open problem, then the tag is added. After that, the question essentially becomes, "What is known about this problem? What are some possible ways to approach this problem? What are some ways that people have tried to attack it before, and with what results?" That way, the cstheory thread for the problem becomes a repository of resources related to the problem. Perhaps the answers could be organized by approach, with an outline of the basic approach, followed by a horizontal rule and a summary of what is promising about the approach and why it doesn't give a complete solution.

To join the discussion about how cstheory should deal with open problems, go to this meta cstheory thread.