8

Is there a database of known problems with information about their complexity and algorithms, related problems, references etc that is available to us? [If not, can we make one? I know this is off topic, but it would be SO useful]

Suresh Venkat
  • 32,071
  • 4
  • 95
  • 271
Ritwik Bose
  • 181
  • 1
  • 7
  • 2
    Usually I just go to Wikipedia - however, I think it would be a great idea to have a TCS Wiki, devoted entirely to topics in theoretical computer science. I'd definitely be interested in helping out with that, if someone was going to start one. – Gautam Kamath Jan 16 '11 at 05:20
  • 2
    (1) I am not sure about the decision that this is a duplicate of Major unsolved problems in theoretical computer science. I guess that the word “problem” in this question refers to a problem in complexity-theory sense, not to an open problem. (2) A compendium of NP optimization problems is a nice place to look at, but you are asking for something more general. (3) I doubt that such a wide-range list will be useful, but I am not really sure. – Tsuyoshi Ito Jan 16 '11 at 07:45
  • @Tsuyoshi Ito (2) is largely what I was looking for. Also was kind of hoping for a total algorithm encyclopedia kind of thing. There are several very good but disjoint sources for that, but lugging those across the world is not really an option. – Ritwik Bose Jan 16 '11 at 09:27
  • I had not realized the [open-problem] tag when I wrote my previous comment. Mechko, please clarify your opinion about Suresh’s decision that this question is a duplicate of the question 174 if you want to object it. – Tsuyoshi Ito Jan 16 '11 at 11:39
  • I just realized the tag is probably what put him off. I'm not looking for a list of OPEN problems, per se, while they may be included in the resource. I changed the tags a little. (In fact what I am looking for are SOLVED variations of known problems to compare my current work against. I'm stuck with a particular reduction and need some inspiration) – Ritwik Bose Jan 16 '11 at 11:43
  • 2
    reopened. I still think the question is very vague, but that's just my opinion as one person. – Suresh Venkat Jan 16 '11 at 11:51
  • 1
    I think that the question in some sense can be very useful, since we could gather here links on databases with problems and results on them. What concerns scheduling theory, there is at least one such database:The scheduling zoo(http://www.lix.polytechnique.fr/~durr/query/). Another well-known database concerning graphs is this:http://wwwteo.informatik.uni-rostock.de/isgci/index.html. Thus we could just compose the list with such databases as the answer to the above question. In this sense the question isn't a duplicate of any question on cstheory. – Oleksandr Bondarenko Jan 16 '11 at 12:13
  • 1
    @Suresh: In fact I may agree that this question is vague. But if that is the reason, the question should be closed as such, not as a duplicate. – Tsuyoshi Ito Jan 16 '11 at 12:47
  • 1
    Should we add the [big-list] tag? (as a sidenote I personally don't like this kind of general questions from new users, the question might be useful for researchers but the OP is not asking it for solving a problem related to her/his research so in my opinion it is not a real question.) – Kaveh Jan 16 '11 at 15:16
  • 2
    There is also the "Complexity Garden", related to the Complexity Zoo but dealing specifically with problems rather than complexity classes. It is a very tiny database, though: http://qwiki.stanford.edu/index.php/Complexity_Garden – Ryan Williams Jan 16 '11 at 20:13
  • @Ryan Williams that would be perfect, if it were comprehensive, or close to. – Ritwik Bose Jan 16 '11 at 21:16
  • 1
    Maybe this question should be made a community wiki question? – Oleksandr Bondarenko Jan 17 '11 at 14:40

2 Answers2

1

If you do not insist on a database, the Encyclopedia of algorithms By Ming-Yang Kao is very valuable reference. The above link is the entry for the minimum Bandwidth problem.

This is an encyclopedia of algorithms that sets out the solutions to important algorithmic problems. It aims to be a comprehensive collection and is designed to provide quick and easy access for both students and researchers.” (Kybernetes, Vol. 38 (1/2), 2009)

Mohammad Al-Turkistany
  • 20,928
  • 5
  • 63
  • 149
  • It looks good, but most useful is something I can have in electronic form and both search or skip through randomly. I'll have to get this, in any case. – Ritwik Bose Jan 16 '11 at 21:15
1

There is a large list of algorithms and data structures on the National Institute of Standards and Technology governmental website: http://xw2k.nist.gov/dads/

It's not complete and I don't know how new algorithms, problems, and data structures can be added, but it has a decently large list. Links to implementations of each description are included, if available.

There are also links to additional resources near the bottom of the page.

oosterwal
  • 131
  • 2