Vamos analisar cada uma das afirmações: I. De acordo com o tamanho de entrada, podemos distinguir os algoritmos em função de complexidade polinomial, os quais são chamados de eficientes. Verdadeiro, algoritmos com complexidade polinomial são geralmente considerados eficientes, pois seu tempo de execução cresce de forma controlada com o aumento do tamanho da entrada. II. Existem muitos problemas computacionais impossíveis de serem resolvidos em tempo polinomial; eles são chamados de NP ou Não-Polinomial. Falso, a classe NP (Nondeterministic Polynomial time) inclui problemas que podem ser verificados em tempo polinomial, mas não necessariamente são impossíveis de serem resolvidos em tempo polinomial. A afirmação correta seria que existem problemas NP-completos que não se sabe se podem ser resolvidos em tempo polinomial. III. Alguns problemas computacionais estão na classe NP-Hard e esses são classificados como pelo menos tão difíceis quanto os problemas mais difíceis em NP. Verdadeiro, a definição de NP-Hard é exatamente essa, referindo-se a problemas que são, no mínimo, tão difíceis quanto os problemas mais difíceis em NP. Com base nas análises: - A afirmação I é verdadeira. - A afirmação II é falsa. - A afirmação III é verdadeira. Portanto, a alternativa correta que contém todas as afirmações verdadeiras é: I e III, apenas.