¿Hay una lista de problemas conocidos?

8

¿Existe una base de datos de problemas conocidos con información sobre su complejidad y algoritmos, problemas relacionados, referencias, etc. que está disponible para nosotros? [Si no, ¿podemos hacer uno? Sé que esto está fuera de tema, pero sería TAN útil]

cc.complexity-theory reference-request survey Ritwik Bose
fuente
2
Por lo general, solo voy a Wikipedia; sin embargo, creo que sería una gran idea tener un TCS Wiki, dedicado por completo a temas de informática teórica. Definitivamente estaría interesado en ayudar con eso, si alguien fuera a comenzar uno.
Gautam Kamath
2
(1) No estoy seguro acerca de la decisión de que este es un duplicado de los principales problemas no resueltos en informática teórica . Supongo que la palabra "problema" en esta pregunta se refiere a un problema en el sentido de la teoría de la complejidad, no a un problema abierto. (2) Un compendio de problemas de optimización de NP es un buen lugar para mirar, pero está pidiendo algo más general. (3) Dudo que una lista tan amplia sea útil, pero no estoy realmente seguro.
Tsuyoshi Ito
2
reabierto. Todavía creo que la pregunta es muy vaga, pero esa es solo mi opinión como una sola persona.
Suresh Venkat
1
Creo que la pregunta en algún sentido puede ser muy útil, ya que podríamos reunir aquí enlaces en bases de datos con problemas y resultados sobre ellos. En lo que respecta a la teoría de la programación, existe al menos una de esas bases de datos: el zoológico de programación ( lix.polytechnique.fr/~durr/query ). Otra base de datos conocida sobre gráficos es la siguiente: wwwteo.informatik.uni-rostock.de/isgci/index.html . Por lo tanto, podríamos componer la lista con bases de datos como la respuesta a la pregunta anterior. En este sentido, la pregunta no es un duplicado de ninguna pregunta sobre teoría.
Oleksandr Bondarenko
2
También está el "Complexity Garden", relacionado con el Complexity Zoo, pero que se ocupa específicamente de problemas en lugar de clases de complejidad. Sin embargo, es una base de datos muy pequeña: qwiki.stanford.edu/index.php/Complexity_Garden
Ryan Williams

Respuestas:

1

Si no insiste en una base de datos, la Enciclopedia de algoritmos de Ming-Yang Kao es una referencia muy valiosa. El enlace anterior es la entrada para el problema de ancho de banda mínimo.

Esta es una enciclopedia de algoritmos que establece las soluciones a problemas algorítmicos importantes. Su objetivo es ser una colección completa y está diseñado para proporcionar un acceso rápido y fácil tanto para estudiantes como para investigadores ". (Kybernetes, Vol. 38 (1/2), 2009)

Mohammad Al-Turkistany
fuente
Se ve bien, pero lo más útil es algo que puedo tener en forma electrónica y buscar o saltar al azar. Tendré que conseguir esto, en cualquier caso.
Ritwik Bose
1

Hay una gran lista de algoritmos y estructuras de datos en el sitio web gubernamental del Instituto Nacional de Estándares y Tecnología: http://xw2k.nist.gov/dads/

No está completo y no sé cómo se pueden agregar nuevos algoritmos, problemas y estructuras de datos, pero tiene una lista bastante grande. Se incluyen enlaces a implementaciones de cada descripción, si están disponibles.

También hay enlaces a recursos adicionales cerca de la parte inferior de la página.

oosterwal
fuente