Para resolver um problema por meios computacionais, é necessário codificá-lo numa dada linguagem e escrever um algoritmo (um programa, nessa mesma linguagem), isto é, um método para resolver o problema num número finito de passos. Um problema é ____ se existe um algoritmo polinomial que o resolva. Se todos os algoritmos conhecidos para resolver um problema forem exponenciais, o problema se diz ______. A alternativa que preenche as lacuna de forma correta é?

Em Teoria da Complexidade, diz-se que um problema é tratável quando existe um algoritmo que o resolva em tempo polinomial (por exemplo, $O(n)$, $O(n^2)$, $O(n^k)$ para algum $k$ constante). Isso significa que, à medida que o tamanho da entrada cresce, o tempo de execução cresce de forma “administrável”.

Por outro lado, quando todos os algoritmos conhecidos para resolver um problema têm tempo exponencial (por exemplo, $O(2^n)$, $O(3^n)$), costuma-se classificar o problema como intratável, pois o custo cresce muito rapidamente e, na prática, torna-se inviável para entradas grandes.

Logo, as lacunas são preenchidas por tratável e intratável.

Alternativa correta: (a).