Segundo Sipser (2007, p. 3), as teorias da computabilidade e da complexidade estão intimamente relacionadas. Essa relação fundamentou a teoria da complexidade computacional que, desde seu aparecimento, vem firmando-se como uma das mais importantes áreas de pesquisa dentro da Ciência da Computação. Nesse contexto, avalie as seguintes asserções:
I – A teoria da complexidade computacional é uma área em rápido desenvolvimento da ciência da computação teórica e abrange tanto questões puramente teóricas quanto questões diretamente relacionadas à prática.
II – Entre as aplicações mais importantes dessa teoria, estão métodos para construir e analisar algoritmos eficientes, bem como métodos criptográficos modernos.
III – Na teoria da complexidade, o objetivo é classificar os problemas como fáceis e difíceis, enquanto na teoria da computabilidade a classificação dos problemas é feita por meio da separação entre os que são solúveis e os que não o são. A teoria da computabilidade introduz vários dos conceitos usados na teoria da complexidade.
Sobre as informações das asserções acima, é CORRETO afirmar que:
a.
Apenas II e III estão corretas.
b.
Todas estão erradas.
c.
Todas estão corretas.
d.
Apenas I e III estão corretas.
e.
Apenas I e II estão corretas.
