Existe uma lista de problemas conhecidos?

Existe um banco de dados de problemas conhecidos com informações sobre sua complexidade e algoritmos, problemas relacionados, referências etc. que estão disponíveis para nós? [Se não, podemos fazer um? Eu sei que isso está fora de tópico, mas seria TÃO útil]

cc.complexity-theory reference-request survey Ritwik Bose
fonte

Normalmente, apenas vou à Wikipedia - no entanto, acho que seria uma ótima idéia ter um Wiki do TCS, dedicado inteiramente a tópicos da ciência da computação teórica. Eu definitivamente estaria interessado em ajudar com isso, se alguém iria começar um.

Gautam Kamath

(1) Não tenho certeza da decisão de que se trata de uma duplicata dos principais problemas não resolvidos da ciência da computação teórica . Eu acho que a palavra "problema" nesta questão se refere a um problema no sentido da teoria da complexidade, não a um problema em aberto. (2) Um compêndio de problemas de otimização de NP é um bom lugar para se olhar, mas você está pedindo algo mais geral. (3) Duvido que uma lista tão ampla seja útil, mas não tenho muita certeza.

Tsuyoshi Ito 16/01

reaberto. Ainda acho a pergunta muito vaga, mas essa é apenas a minha opinião como pessoa.

Suresh Venkat

Penso que a questão, em certo sentido, pode ser muito útil, pois poderíamos reunir aqui links em bancos de dados com problemas e resultados neles. No que diz respeito à teoria do agendamento, existe pelo menos um desses bancos de dados: O zoológico de agendamento ( lix.polytechnique.fr/~durr/query ). Outro banco de dados conhecido sobre gráficos é este: wwwteo.informatik.uni-rostock.de/isgci/index.html . Assim, poderíamos apenas compor a lista com bancos de dados como a resposta à pergunta acima. Nesse sentido, a questão não é uma duplicata de nenhuma questão sobre a história.

Oleksandr Bondarenko

Há também o "Jardim da Complexidade", relacionado ao Zoológico da Complexidade, mas que trata especificamente de problemas e não de classes de complexidade. É um muito pequeno banco de dados, no entanto: qwiki.stanford.edu/index.php/Complexity_Garden

Ryan Williams

Respostas:

Se você não insiste em um banco de dados, a Enciclopédia de algoritmos By Ming-Yang Kao é uma referência muito valiosa. O link acima é a entrada para o problema mínimo de largura de banda.

Esta é uma enciclopédia de algoritmos que define as soluções para problemas algorítmicos importantes. O objetivo é ser uma coleção abrangente e foi projetado para fornecer acesso rápido e fácil para estudantes e pesquisadores. ” (Kybernetes, Vol. 38 (1/2), 2009)

Mohammad Al-Turkistany
fonte

Parece bom, mas o mais útil é algo que posso ter em formato eletrônico e pesquisar ou pular aleatoriamente. Eu vou ter que conseguir isso, em qualquer caso.

Ritwik Bose

Há uma grande lista de algoritmos e estruturas de dados no site governamental do Instituto Nacional de Padrões e Tecnologia: http://xw2k.nist.gov/dads/

Não está completo e não sei como novos algoritmos, problemas e estruturas de dados podem ser adicionados, mas possui uma lista decentemente grande. Links para implementações de cada descrição estão incluídos, se disponíveis.

Também há links para recursos adicionais na parte inferior da página.

oosterwal
fonte