<p>There is a large list of algorithms and data structures on the National Institute of Standards and Technology governmental website:  <a href="http://xw2k.nist.gov/dads/" rel="nofollow">http://xw2k.nist.gov/dads/</a></p>

<p>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.</p>

<p>There are also links to additional resources near the bottom of the page.</p>

CC BY-SA 2.5
2011-01-18T22:31:30.950Z
2011-01-18T22:31:30.950Z
oosterwal
<p>If you do not insist on a database, the <a href="http://books.google.com/books?id=i3S9_GnHZwYC&amp;pg=PA366&amp;lpg=PA366&amp;dq=Encyclopedia+of+Algorithms+bandwidth&amp;source=bl&amp;ots=nBppleEpLu&amp;sig=pL8po9dD0y5tl4i91YFNSxdoCeM&amp;hl=en&amp;ei=NxkzTbyVAYLDswa67biCCg&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=1&amp;ved=0CBcQ6AEwAA&amp;safe=active#v=onepage&amp;q&amp;f=false" rel="nofollow">Encyclopedia of algorithms</a> By Ming-Yang Kao is very valuable reference. The above link is the entry for the minimum Bandwidth problem.</p>

<blockquote>
  <p>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)</p>
</blockquote>

CC BY-SA 2.5
2011-01-16T21:15:39.270Z
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
CC BY-SA 2.5
2011-01-16T16:23:00.413Z
2011-01-16T16:23:00.413Z
Mohammad Al-Turkistany
<p>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]</p>

CC BY-SA 2.5
2011-01-16T05:20:49.077Z
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
CC BY-SA 2.5
2011-01-16T07:45:35.133Z
(1) I am not sure about the decision that this is a duplicate of [Major unsolved problems in theoretical computer science](http://cstheory.stackexchange.com/questions/174/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](http://www.csc.kth.se/~viggo/wwwcompendium/) 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
CC BY-SA 2.5
2011-01-16T09:27:16.633Z
@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
CC BY-SA 2.5
2011-01-16T11:39:46.787Z
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
CC BY-SA 2.5
2011-01-16T11:43:39.633Z
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
CC BY-SA 2.5
2011-01-16T11:51:06.673Z
reopened. I still think the question is very vague, but that's just my opinion as one person.
Suresh Venkat
CC BY-SA 2.5
2011-01-16T12:13:37.880Z
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
CC BY-SA 2.5
2011-01-16T12:47:09.177Z
@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
CC BY-SA 2.5
2011-01-16T15:16:50.387Z
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
CC BY-SA 2.5
2011-01-16T20:13:17.807Z
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
CC BY-SA 2.5
2011-01-16T21:16:58.940Z
@Ryan Williams that would be perfect, if it were comprehensive, or close to.
Ritwik Bose
CC BY-SA 2.5
2011-01-17T14:40:21.070Z
Maybe this question should be made a community wiki question?
Oleksandr Bondarenko
<cc.complexity-theory><reference-request><survey>
Is there a list of known problems?
Ritwik Bose
# Is there a list of known problems?

(Asked by: username_0 on 2011-01-16)

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]

**Tags:** cc.complexity-theory, reference-request, survey
> **Comments:**
> **username_1**: 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.  
> **username_2**: (1) I am not sure about the decision that this is a duplicate of [Major unsolved problems in theoretical computer science](http://cstheory.stackexchange.com/questions/174/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](http://www.csc.kth.se/~viggo/wwwcompendium/) 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.  
> **username_0**: @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.  
> **username_2**: 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.  
> **username_0**: 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)  
> **username_3**: reopened. I still think the question is very vague, but that's just my opinion as one person.  
> **username_4**: 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.  
> **username_2**: @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.  
> **username_5**: 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.)  
> **username_6**: 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  
> **username_0**: @Ryan Williams that would be perfect, if it were comprehensive, or close to.  
> **username_4**: Maybe this question should be made a community wiki question?  

---

## 2 answers

### Answer by username_7 on 2011-01-18. Score: 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.


---

### Answer by username_8 on 2011-01-16. Score: 1

If you do not insist on a database, the [Encyclopedia of algorithms](http://books.google.com/books?id=i3S9_GnHZwYC&pg=PA366&lpg=PA366&dq=Encyclopedia+of+Algorithms+bandwidth&source=bl&ots=nBppleEpLu&sig=pL8po9dD0y5tl4i91YFNSxdoCeM&hl=en&ei=NxkzTbyVAYLDswa67biCCg&sa=X&oi=book_result&ct=result&resnum=1&ved=0CBcQ6AEwAA&safe=active#v=onepage&q&f=false) 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)

> **Comments:**
> **username_0**: 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.  

---

