A solução para dado problema pode ser obtida por meio da descrição de um algoritmo que o resolva. Para isso, no entanto, é fundamental que se analise a computabilidade do problema. Sobre o conceito de computabilidade, leia as assertivas a seguir. I. Se um problema em um cenário prático é dito computável, então qualquer algoritmo que o resolva pode ser empregado. II. Um algoritmo de complexidade O(cn) é dito intratável, já que o seu tempo de resposta é inviável para um problema prático. III. Algoritmos que resolvem problemas incomputáveis têm complexidade de tempo inviável para situações práticas. IV. Um algoritmo com complexidade O(n!) é menos eficiente do que qualquer algoritmo para problemas tratáveis. Quais estão corretas?

Vamos avaliar cada assertiva.

I. “Se um problema em um cenário prático é dito computável, então qualquer algoritmo que o resolva pode ser empregado.”
Falsa. Ser computável significa que existe algum algoritmo que resolve o problema (isto é, termina e produz a resposta correta). Mas nem todo algoritmo que “resolve” o problema é necessariamente adequado ao cenário prático: pode haver algoritmos corretos porém com tempo/memória inviáveis, ou com requisitos que não se encaixam (por exemplo, precisar de mais recursos do que os disponíveis). Computabilidade não garante viabilidade prática.

II. “Um algoritmo de complexidade $O(c^n)$ é dito intratável...”
Verdadeira. Complexidades exponenciais do tipo $O(c^n)$ (com $c>1$) crescem muito rapidamente, e são tipicamente classificadas como intratáveis para tamanhos moderados/grandes de entrada em aplicações reais.

III. “Algoritmos que resolvem problemas incomputáveis têm complexidade de tempo inviável...”
Falsa. Problemas incomputáveis (não decidíveis) não possuem algoritmo que os resolva para todas as entradas (isto é, não existe procedimento geral que sempre termine com a resposta correta). Logo, não faz sentido dizer que “os algoritmos que resolvem” tais problemas têm tempo inviável—o ponto é mais forte: não há algoritmo geral que resolva.

IV. “Um algoritmo com complexidade $O(n!)$ é menos eficiente do que qualquer algoritmo para problemas tratáveis.”
Verdadeira no contexto usual da classificação tratável vs. intratável: problemas tratáveis são, em geral, os que admitem algoritmos em tempo polinomial ($O(n^k)$). Já $O(n!)$ é superpolinomial e cresce muito mais rápido do que qualquer polinômio; portanto, é considerado pior (menos eficiente) do que algoritmos de problemas tratáveis (polinomiais).

Corretas: II e IV.

Alternativa correta: (b).