Resumo
Quando tratamos de problemas computacionais, buscamos sempre desenvolver algoritmos eficientes que os resolvam, para todas as instâncias possíveis. O conceito de eficiência de um algoritmo normalmente refere-se à sua complexidade de tempo ser polinomial no tamanho da entrada. Porém, existem muitos problemas relevantes para os quais não há esperança de que existem algoritmos eficientes que…