When I ask questions of the form "what is the complexity of problem BLAH", then there is an ambiguity (to me) about whether an accepted answer should simply give the best known bounds according to current literature, or whether I shouldn't accept an answer until the exact complexity has been nailed (which may require an original proof).

In particular I am not sure what to do about answers that say that the problem is open. In a sense, these answers solve my problem, as they tell me that the question is already known to be tricky and is not so likely to be answered in the near future. On the other hand, they do not give the answer that I am interested in, and could be ultimately replaced by a more definitive answer. Should such answers be accepted?

Here are some examples:

  • In this question, I asked about the complexity of a problem, and an author of the most relevant paper on the topic answered that he did not know. This answer is of course very useful, but I do not know whether I should accept it. (Update: meanwhile, a new answer has been posted, so the description here no longer makes sense)

  • In that question, I accepted an answer saying that the problem was still open. I guess this is reasonable as my question was asking "is the problem still open".

(Sorry if this isn't the right kind of questions for meta.CS.SE. I'm not familiar with the meta sites.)


2 Answers 2


I think that it is fine to accept those answers (since they answer your question). Hopefully if the open problem becomes resolved then the person that resolved it (or somebody else) will post a new answer that shows the resolution. When that happens, you can unaccept the "open problem" answer and accept the "here's the solution" answer.


I usually act depending on how much information I've gained from the answer. If I didn't know the bounds given/the latest paper, then I would accept. If I was aware of the best bounds (in which case I try to mention this in my question), then I don't accept. So according to this, in your first example I would not accept, although the fact that the author of the latest paper replied does make things a bit different. Artem's solution of accepting and later unaccepting also sounds quite reasonable.


You must log in to answer this question.

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